Problem:
 Score : 400 points    Problem Statement There are N islands lining up from west to east, connected by N-1 bridges.  The i -th bridge connects the i -th island from the west and the (i+1) -th island from the west.  One day, disputes took place between some islands, and there were M requests from the inhabitants of the islands:  Request i : A dispute took place between the a_i -th island from the west and the b_i -th island from the west. Please make traveling between these islands with bridges impossible.  You decided to remove some bridges to meet all these M requests.  Find the minimum number of bridges that must be removed.      Constraints  All values in input are integers.  2 \leq N \leq 10^5  1 \leq M \leq 10^5  1 \leq a_i < b_i \leq N  All pairs (a_i, b_i) are distinct.         Input Input is given from Standard Input in the following format:  N  M  a_1  b_1  a_2  b_2  :  a_M  b_M       Output Print the minimum number of bridges that must be removed.        Sample Input 1 5 2
1 4
2 5      Sample Output 1 1  The requests can be met by removing the bridge connecting the second and third islands from the west.       Sample Input 2 9 5
1 8
2 7
3 5
4 6
7 9      Sample Output 2 2       Sample Input 3 5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5      Sample Output 3 4

Solution (Python):
def main():
    in1 = input().split(" ")
    n, m = [int(c) for c in in1]

    arr = []
    for i in range(m):
        _in = input().split(" ")
        a, b = [int(c) for c in _in]
        arr.append((a, b))

    sorted_arr = sorted(arr, key=lambda x: x[0])

    n = 1

    mi, ma = sorted_arr[0]
    mi, ma = (mi, ma) if mi < ma else (ma, mi)
    for a, b in sorted_arr[1:]:
        a, b = (a, b) if a < b else (b, a)
        if ma <= a:
            n += 1
            mi, ma = a, b
        if mi < a:
            mi = a
        if ma > b:
            ma = b
    print(n)

if __name__ == "__main__":
    main()

Solution (Python):
n, m = list(map(int, input().split()))
l = [200000 for i in range(0, n-1)]

for i in range(0, m):
    a, b = list(map(int, input().split()))
    l[a-1] = min([l[a-1], b-2])

right = -1
count = 0

for i in range(0, n-1):
    if i > right and not l[i] == 200000:
        count += 1
        right = l[i]
    elif i <= right and not l[i] == 200000:
        right = min([l[i], right])

print(count)

Solution (Python):
import bisect

n,m = map(int,input().split())	
aaa = [list(map(int,input().split())) for i in range(m)]
ab = sorted(aaa)


l = []
l.append(ab[0][0]-1)
l.append(ab[0][1]-1)

p = 1

if m != 1:
    

    for i in range(1,m):
        a = ab[i][0]-1
        b = ab[i][1]-1
        if a != l[len(l)-2]:
            if a < l[len(l)-1]:
                l[len(l)-2] = a
                if b < l[len(l)-1]:
                    l[len(l)-1] = b
            else:
                l.append(a)
                l.append(b)
                p += 1
print(p)

Solution (Python):


N,M = map(int, input().split())
abM = [list(map(int, input().split())) for i in range(M)]

abM.sort()

tmp_e = abM[0][1]
cnt = 1

for i in range(1,M):
    if tmp_e > abM[i][0]:
        tmp_e = min(abM[i][1], tmp_e)
    else:
        cnt += 1
        tmp_e = abM[i][1]
print(cnt)

Solution (Python):
import collections

n,m= map(int, input().split())


requests = []
for i in range(m):
    a,b = map(int, input().split())
    requests.append((b-1,-a+1))
requests.sort()
cnt = 0
lb = -1
for b,a in requests:
    if lb < -a or b<= lb:
        cnt += 1
        lb = b-1
print(cnt)

Solution (Python):
from operator import itemgetter


n,m = map(int,input().split())

tasks = []
for i in range(m):
    a,b = map(int,input().split())
    tasks.append([b,a])



tasks = sorted(tasks, key=lambda x: x[0])
end = 0
start = 0
ans = 0
for task in tasks:
    if task[1]<start: continue
    end = task[0]
    ans += 1
    start = end

print(ans)

Solution (Python):
n, m = map(int, input().split())

s = [n for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    if s[a - 1] > b - 1:
        s[a - 1] = b - 1

result = 0
i = 0
while i < n - 1:
    hoge = min(s[i:])
    if hoge == n:
        break
    i = hoge
    result += 1

print(result)

Solution (Python):

import sys
from collections import deque
import copy

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] =  [int(input_raw[0]), int(input_raw[1])]
    sep= []
    for i in range(M):
        input_raw = read_func().strip().split()
        [a, b] =  [int(input_raw[0]), int(input_raw[1])]
        sep.append((a, b))

    sep.sort()

    count = 1
    is_search = False
    i = 0
    while i < M:
        if is_search == False:
            ai = sep[i][0]
            bi = sep[i][1]
            is_search = True
            i += 1
        else:
            aj = sep[i][0]
            bj = sep[i][1]
            if ((ai <= aj and aj < bi)) == False :
                count += 1
                is_search = False
            else:
                ai = max(ai, aj)
                bi = min(bi, bj)
                i += 1

    print count



if __name__ == '__main__':
    main()

Solution (Python):
N,M=list(map(int,input().split()))

bridge=[None]*M

for i in range(M):
    bridge[i]=tuple(map(int,input().split()))


bridge.sort()

brilist=[0]*(10**5)
brilist[bridge[0][0]]=bridge[0][1]

for i in range(1,M):
    if bridge[i][0]==bridge[i-1][0]:
        brilist[bridge[i][0]]=min(bridge[i][1],brilist[bridge[i][0]])

    elif bridge[i][0]<brilist[bridge[i-1][0]]:

        brilist[bridge[i][0]]=min(bridge[i][1],brilist[bridge[i-1][0]])
        brilist[bridge[i-1][0]]=0
        

    else:

        brilist[bridge[i][0]]=bridge[i][1]

    


ANS=0
for i in range(10**5):
    if brilist[i]!=0:
        ANS+=1

print(ANS)

Solution (Python):
from operator import itemgetter
N, M = map(int, raw_input().split())
a = []
b = []
for i in range(M):
	_a, _b = map(int, raw_input().split())
	a.append(_a)
	b.append(_b)

c = zip(a, b)
c.sort(key=itemgetter(0))
a, b = zip(*c)

c = 0
min_b = 0
for i in range(M):
	min_b = min(min_b, b[i])
	if a[i] < min_b:
		continue
	else:
		c += 1
		min_b = b[i]
print(c)

Solution (Python):
n, m = map(int, input().split())
lrs = [[int(x) for x in input().split()] for _ in range(m)]
lrs.sort()

ans = 0
m = -1
for l, r in lrs:
    if r < m:
        m = r
    if l >= m:
        ans += 1
        m = r

print(ans)

Solution (Python):
N, M = map(int, (input().split()))

ab = [[0 for i in range(2)] for j in range(M)]

for i in range(M):
    ab[i] = list(map(int, input().split()))


ab2 = sorted(ab, key=lambda x:(x[0], x[1]), reverse=False)


count = 0

def func(ablist):
    mi = 0
    ma = float('inf')
    for i in range(len(ablist)):
        mi = max(mi, ablist[i][0])
        ma = min(ma, ablist[i][1] - 1)

        if mi > ma:
            return func(ablist[i:]) + 1
    return 1

print(func(ab2))

Solution (Python):
N,M=map(int,input().split())
request=[]
for _ in range(M):
    request.append(list(map(int,input().split())))
request.sort(key=lambda x: x[0])
    
memory=request[0][1]
head = request[0][0]
index = 0
ans = 0

def equal():
    if index == M-1: return False
    else: return head == request[index+1][0]

while head <= N:
    if head == memory:
        ans +=1
        memory = N+1
    elif equal():
        index +=1
        memory=min(request[index][1],memory)
    else: head +=1
        
print(ans)

Solution (Python):
N, M = [int(t) for t in input().split()]
R = []
for i in range(M):
    a, b = [int(t) for t in input().split()]
    R.append((a, b))

R.sort()

inf = float('inf')
Ra = [inf for a in range(N + 1)]
for a, b in R:
    Ra[a] = min(Ra[a], b)
R = [(a, Ra[a]) for a in range(1, N+1) if Ra[a] != inf]

R.sort(key=lambda r: r[1])

bridge = [True] * (N)

last = None
for a, b in R:
    if last == None or last < a:
        bridge[b-1] = False
        last = b-1
print(sum(1 for b in bridge if not b))

Solution (Python):


N,M = map(int, input().split())
abM = [list(map(int, input().split())) for i in range(M)]

abM.sort(key = lambda x: (x[0], x[1]))

tmp_e = abM[0][1]
cnt = 1

for i in range(1,M):
    if tmp_e > abM[i][0]:
        tmp_e = min(abM[i][1], tmp_e)
    else:
        cnt += 1
        tmp_e = abM[i][1]
print(cnt)

Solution (Python):
import bisect
N,M = map(int,input().split())
l = [0]*M
for i in range(M):
     l[i] = list(map(int,input().split()))
l.sort()
a = [0]*M
b = [0]*M
for i in range(M):
    a[i] = l[i][0]
    b[i] = -l[i][1]
ans = 0
while len(a)>0:
    min = -max(b)
    i = bisect.bisect(a,min-1)
    a = a[i:]
    b = b[i:]
    ans += 1
print(ans)

Solution (Python):
from operator import itemgetter


def main():
    n, m = map(int, input().split())
    li = []
    for i in range(m):
        a, b = map(int,input().split())
        li.append([a,b])
    li = sorted(li,reverse = True)
    count = 1
    mark = 0
    i = 0
    j = 0
    while m > 1:
        check = li[j][0]
        i = i + 1
        if check < li[i][1]:
            m = m - 1
        else:
            count = count + 1
            m = m - 1
            j = i
    print (count)

if __name__ == "__main__":
    main()

Solution (Python):
N,M=map( int, raw_input().split() ) 
A= [ map( int, raw_input().split() )  for i in range(M) ]

A.sort(key=lambda x:(x[0],-x[1]))

ans=0
for i  in range(M):
	x=A[i][0]
	y=A[i][1]
	if i==0:
		l=x
		r=y
		ans+=1
	else:
		if l<=x and x<r:
			
			l=max(l,x)
			r=min(r,y)
		else:
			ans+=1
			l=x
			r=y
print ans

Solution (Python):
def spaceinput():
    return list(map(int,input().split(" ")))


N,M=spaceinput()

sima=[]
for i in range(M):
    sima.append(spaceinput())


sima=sorted(sima,key=lambda x:x[0])



blr=[0,0]

count=0
for i in range(M):
    if sima[i][0]>=blr[1]:
        count+=1
        blr=sima[i][:]
    elif blr[1]>=sima[i][1]:
        blr[0]=sima[i][0]
        blr[1]=sima[i][1]

    else:
        blr[0]=sima[i][0]


print(count)

Solution (Python):
N, M = map(int, input().split())
E = []
for i in range(M):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    E.append([a, b])

E.sort()
l, r = 0, float('inf')
ans = 0
for a, b in E:
    if b <= l or a >= r:
        ans += 1
        l, r = a, b
    else:
        l = max(a, l)
        r = min(b, r)

print(ans + 1)

Solution (Python):
n, m = map(int, input().split())
store = []
for _ in range(m):
    a, b = map(int, input().split())
    store.append([a, b])
store.sort(key = lambda x:x[0])
count = 0
ans = 0
while count < m:
    index = 1
    t = store[0][1]
    while index < len(store) and store[index][0] < t:
        t = min(t, store[index][1])
        index += 1
    count += index
    store = store[index:]
    ans += 1
print(ans)

Solution (Python):


if __name__ == '__main__':
    N, M = map(int, input().split())
    cut_list = []
    demand_list = [list(map(int, input().split())) for i in range(M)]
    demand_list.sort()

    
    previous_demand = demand_list[0]
    demand_list = demand_list[1:]
    counter = 1

    if M == 1:
        print(counter)
    else:
        for demand in demand_list:
            if previous_demand[0] == demand[0]:
                pass
            elif previous_demand[1] <= demand[0]:
                previous_demand = demand
                counter += 1
            else:
                previous_demand = [demand[0], min(previous_demand[1], demand[1])]

        print(counter)

Solution (Python):

N,M = map(int,input().split())
query = [list(map(int,input().split())) for i in range(M)]

query.sort()

left = 0
right = N+1
ans = 1
for q in query:
	if (left <= q[0] and q[0] < right) or (left < q[1] and right >= q[1]):
		left = max(left,q[0])
		right = min(right,q[1])
	else:
		ans += 1
		left = q[0]
		right = q[1]
print(ans)

Solution (Python):
n, m = map(int, input().split())
com = []
for i in range(m):
    c = list(map(int, input().split()))
    com.append(c)

com.sort(key=lambda x:x[1])

count = 1
start = com[0][0]
end = com[0][1]

for i in range(m):
    if com[i][0]>= end:
        end = com[i][1]
        count += 1

print(count)

Solution (Python):
n,m=[int(i) for i in input().split()]
x=[10**5+1 for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  x[a-1]=min([x[a-1],b-1])


y=0
t=10**5+1
r=0
for i,j in enumerate(x):
  if j !=10**5+1:
    if i >= t or r==0:
      y+=1
      r=1
      t=j
    elif t>j:
      t=j

print(y)

Solution (Python):
N, M = map(int, input().split())
AB = []
for i in range(M):
    AB.append([int(i) for i in input().split()])
AB.sort()

MinBar = 1
abar = AB[0][0]
bbar = AB[0][1]
for i in range(1, M):
    if AB[i][0] < bbar:
        bbar = min(bbar, AB[i][1])
    else:
        MinBar += 1
        abar = AB[i][0]
        bbar = AB[i][1]
print(MinBar)

Solution (Python):
n,m=map(int,input().split())
reqs = [list(map(int,input().split())) for _ in range(m)]

reqs.sort(key=lambda x:(x[0],x[1]))
query = []
tmp = 0
for req in reqs:
  if tmp == req[0]:
    continue
  else:
    query.append(req)
    tmp = req[0]
    
left = 0
right = n
count = 1
for q in query:
  if left <= q[0] and q[1]-1 <= right:
    left = q[0]
    right = q[1]-1
  elif left <= q[0] <= right:
    left = q[0]
  else:
    count += 1
    left = q[0]
    right = q[1]-1
print(count)

Solution (Python):
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,m]=i2()
c=[[] for i in range(n)]
for i in range(m):
 [a,b]=i2()
 c[a-1].append(b-1)
d=[]
e=0
for i in range(n):
 if i in d:
   e+=1
   d=[]
 if len(c[i]):
  d.append(min(c[i]))
print(e)

Solution (Python):
n,m = map(int,input().split())
ab = []
for i in range(m):
    a,b = map(int,input().split())
    ab.append((a,b))
ab = sorted(ab,key=lambda x:x[1])
count = 0
while len(ab) != 0:
    x = ab.pop(0)
    cut = x[1]-1
    count += 1
    while len(ab) != 0:
        if ab[0][0] <= cut <= ab[0][1]:
            ab.pop(0)
        else:
            break
print(count)

Solution (Python):
from operator import itemgetter
n,m = map(int,input().split())
ab = []
for i in range(0,m):
    aa,bb = map(int,input().split())
    ab.append((aa,bb))
ab.sort(key=itemgetter(1))
ans = 0
last = 0
for i in range(0,m):
    s,t = ab[i]
    if last <= s:
        ans += 1
        last = t
print(ans)

Solution (Python):
N, M = map(int, input().split())
ABs = [tuple(map(int, input().split())) for i in range(M)]

ABs.sort()

ans = 0
minB = N+1
for A, B in ABs + [(N+1, N+1)]:
    if minB <= A:
        ans += 1
        minB = B
    minB = min(minB, B)

print(ans)

Solution (Python):
n,m=map(int, input().split())
ab=[list(map(int, input().split())) for _ in range(m)]
ab.sort()
xy=[[ab[0][0], ab[0][1]]]
for i in range(1,m):
    if ab[i][0]<xy[-1][1]:
        xy[-1][0],xy[-1][1]=ab[i][0],min(xy[-1][1],ab[i][1])
    else:
        xy.append([ab[i][0], ab[i][1]])
print(len(xy))

Solution (Python):
n, m = map(int, input().split())
m_list = []
for i in range(m):
    m_list.append(list(map(int, input().split())))
m_list = sorted(m_list)
b_s = 0
b_e = n
cnt = 1
for i in range(m):
    a, b = m_list[i][0], m_list[i][1]
    if b_s <= a < b_e:
        if b_s < a:
            b_s = a
        if b < b_e:
            b_e = b
    else:
        cnt += 1
        b_s = a
        b_e = b
print(cnt)

Solution (Python):
from operator import itemgetter

N, M = map(int, input().split())
ab = [[int(x) for x in input().split()] for _ in range(M)]

ab = sorted(ab, key=itemgetter(0, 1))
ans = 1
x, y = ab[0]
for i in range(1, M):
    a, b = ab[i]
    if b <= x or y <= a:
        ans += 1
        x, y = a, b
    else:
        x = max(x, a)
        y = min(y, b)
print(ans)

Solution (Python):
n,m=map(int,input().split())
ng=[set() for _ in range(n)]

for i in range(m):
    A,B=map(int,input().split())
    ng[A].add(B)
    
now=[]
danger=set()
cu=0
for i in range(1,n):
    now.append(i)
    for j in ng[i]:
        danger.add(j)
    if(i+1 in danger):
        cu+=1
        danger.clear()
            
print(cu)

Solution (Python):
N, M = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(M)]
ab = sorted(ab, key=lambda x:x[1])

cut_set = set()

for t in ab:
    todo = 1
    for s in cut_set:
        if t[0] <= s <= t[1]:
            todo = 0
            break
    if todo:
        cut_set.add(t[1] - 1)
print(len(cut_set))

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

N, M  = getNM()
req = [N for i in range(N)]
for i in range(M):
    l,r = getNM()
    if req[l] > r-1:
        req[l] = r-1
ans = 0
tar = 0

req2 = []
cut = N
for i in range(N):
    if (req[N-i-1]) < cut:
        cut = N-i-1
        ans += 1
    else:
        pass


print(ans)

Solution (Python):
N, M = list(map(int, input().split()))
a = []
for i in range(M):
    a.append(list(map(int, input().split())))
a.sort()
ans = 0

l, r = a[0][0], a[0][1]

for i in range(len(a)):
    if a[i][0] < r:
        if a[i][1] < r:
            l, r = a[i][0], a[i][1]
        else:
            l = a[i][0]
    else:
        ans += 1
        l, r = a[i][0], a[i][1]

ans += 1
print(ans)

Solution (Python):
n,m=map(int, input().split())
ab=[list(map(int, input().split())) for _ in range(m)]
ab.sort()
a=[ab[i][0] for i in range(m)]
b=[ab[i][1] for i in range(m)]
xy=[[a[0], b[0]]]
for i in range(1,m):
    if a[i]<xy[-1][1]:
        xy[-1][0],xy[-1][1]=a[i],min(xy[-1][1],b[i])
    else:
        xy.append([a[i], b[i]])
print(len(xy))

Solution (Python):
N, M = map(int, input().split())

count = 1
ab = []

for i in range(M):
    ab.append(list(map(int, input().split())))
ab.sort()

a, b = ab[0]

for i in range(1, M):
    a_new, b_new = ab[i]

    if b <= a_new:
        a, b = a_new, b_new
        count += 1

    elif  b_new <= b:
        a, b = a_new, b_new

    else:
        a = a_new

print(count)

Solution (Python):
def main():
    n, m = map(int, input().split())

    pairs = []
    for i in range(m):
        a, b = map(int, input().split())
        pairs.append((a, b))

    pairs.sort(key=lambda tup: tup[0])

    cnt = 1
    left, right = -1, 100001
    for i in range(m):
        if right <= pairs[i][0]:
            cnt += 1
            left, right = pairs[i][0], pairs[i][1]
        else:
            if left < pairs[i][0]:
                left = pairs[i][0]
            if pairs[i][1] < right:
                right = pairs[i][1]

    print(cnt)


if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())

arr = []
for i in range(M):
  a, b = map(int, input().split())
  arr.append((b, a))

arr.sort()

prev = 0
ans = 0
for b, a in arr:
  if prev <= a:
    ans += 1
    prev = b

print(ans)

Solution (Python):
n, m = [int(i) for i in input().split()]
a = [0 for i in range(m)]
b = [0 for i in range(m)]

s = [[0, 0] for i in range(m)]
for i in range(m):
    a[i], b[i] = [int(i) for i in input().split()]
    s[i] = [b[i], a[i]]
count = 0
s = sorted(s)

i = 0
pivot = -1

for i in range(m):
    if s[i][1] >= pivot:
        count += 1
        pivot = s[i][0]
        

"""
    count += 1
    pivot = s[i][0]
    print("i :{} piv:{}".format(i, pivot))
    i += 1
    if i < m:
        while s[i][1] < pivot:
            i += 1
            print("i2:{} piv:{}".format(i, pivot))
"""
print(count)

Solution (Python):
n, m = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(m)]
lst.sort()
lst = [[lst[i][0] - 1, lst[i][1] - 1, i] for i in range(m)]
dic = {}
for a, b, i in lst:
  if b in dic:
    dic[b].append(i)
  else:
    dic[b] = [i]

used = [False] * m
ans = 0
right = -1
for i in range(m):
  a, b, _ = lst[i]
  if used[i]:
    continue
  if right >= a:
    used[i] = True
    continue
  used[i] = True
  ans += 1
  for p in range(a, b):
    flag = False
    if p in dic:
      for j in dic[p]:
        if not used[j]:
          used[j] = True
          right = p - 1
          flag = True
    if flag:
      break
  else:
    right = p
print(ans)

Solution (Python):
N,M=map(int,input().split())
table=[]
for i in range(M):
    a,b=map(int,input().split())
    table.append((a-1,b-2))
table.sort()
s=0
t=N
ans=0
for a,b in table:
    if t<a:
        ans+=1
        s=a
        t=b
    else:
        s=a
        t=min(t,b)
        
print(ans+1)

Solution (Python):
N, M = list(map(int, input().split()))
L = []
for i in range(N):
	L.append(100001)
for i in range(M):
	ab = list(map(int, input().split()))
	ab.sort()
	if L[ab[0] - 1] > ab[1] - 1:
		L[ab[0] - 1] = ab[1] - 1 

c = 0
x = 100001
for i in range(N - 1):
	if L[i] == 100001:
		if i == x:
			c += 1
			x = 100001
	else:
		if i == x:
			c += 1
			x = 100001

		if L[i] < x:
				x = L[i]
	
if x == 100001:
	print(c)
else:
	print(c + 1)

Solution (Python):
n,m=map(int,input().split())
c=[]
for i in range(m):
  a,b=map(int,input().split())
  c.append([a,b])
c.sort()
bridge=0
key=1
for i in range(m):
  if c[i][1]<=key:
    key=c[i][1]
  if c[i][0]>=key:
    bridge+=1
    key=c[i][1]
print(bridge)

Solution (Python):
def solve(xys):
    count = 0
    right = 0
    xys.sort(key=lambda x: x[0])
    for a, b in xys:
        if right <= a:
            count += 1
            right = b
        elif b < right:
            right = b
    return count

if __name__ == "__main__":
    n, m = map(int, input().split())
    xys = [[int(s) for s in input().split()] for _ in range(m)]
    print(solve(xys))

Solution (Python):
n, m = map(int, input().split())
v = [0 for i in range(n+1)]
path = [0 for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    if v[b] < a:
        v[b] = a

last = 0

for i in range(n+1):
    if v[i] == 0:
        continue
    m = v[i]

    if last < m:
        path[i - 1] = 1
        last = i - 1


s = 0
for p in path:
    s += p
print(s)

Solution (Python):
N,M=map(int, input().split())
G=[list() for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
ans=0
index=-1
for i in range(1,N):
    for p in G[i]:
        if index<p<i:
            ans+=1
            index=i-1
print(ans)

Solution (Python):
N, M = map(int, input().split())
B = []
for i in range(M):
    (a, b) = map(int, input().split())
    B.append((a, b))
B = sorted(B, key=lambda x: x[0])


def update(x, y):
    if x[0] == y[0]:
        return (x[0], min(x[1], y[1]))
    if x[1] <= y[0]:
        return False
    else:
        return (y[0], min(x[1], y[1]))


now = B[0]
count = 0
for i in range(1, M):
    ans = update(now, B[i])
    
    if ans:
        now = ans
    else:
        count += 1
        now = B[i]
count += 1
print(count)

Solution (Python):
n,m=map(int,input().split())
mx =[-1 for i in range(0,n)]
for z in range(0,m):
  a,b=map(int,input().split())
  mx[b-1]=max(mx[b-1],a-1)
cut=-1
cn=0
for z in range(0,n):
	if cut<mx[z]:
		cut=z-1
		cn=cn+1
print(cn)

Solution (Python):
n,m=map(int,input().split())
list=[]
for i in range(m):
    a,b=map(int,input().split())
    list.append([max(a,b),min(a,b)])
list.sort()
a=1
b=0
k=0
while list!=[]:
    j=list[0]
    if k>j[1]:
        list.remove(j)
    elif j[0]<a:
        list.remove(j)
    else:
        list.remove(j)
        b+=1
        a=j[0]+1
        k=j[0]
print(b)

Solution (Python):
N, M = [int(elem) for elem in input().split(' ')]
request_list = [[int(elem) for elem in input().split(' ')] for _ in range(M)]
assert len(request_list) == M
assert len(request_list[0]) == 2


request_list.sort(key=lambda x: x[0])

def is_overlap(a, b):
    if max(a) <= min(b) or max(b) <= min(a):
        return False
    else:
        return True


count = 1
current_list = request_list[0]
for i in range(1, M):
    if is_overlap(current_list, request_list[i]):
        current_list = [max(current_list[0], request_list[i][0]), \
                        min(current_list[1], request_list[i][1])]
    else:
        count += 1
        current_list = request_list[i]

print(count)

Solution (Python):
N, M = map(int, input().split())

Query = []
for _ in range(M):
    Query.append(list(map(int, input().split())))


Query.sort(key = lambda x : x[1])

count = 1
last = Query[0][1]
for i in range(1, M):
    if Query[i][0] >= last:
        count += 1
        last = Query[i][1]
print(count)

Solution (Python):
N, M = map(int, input().split())
br = []
for i in range(M):
    a, b = map(int, input().split())
    br.append([a, b])
br.sort()


br_ = []
q = 0

for i in br:
    a = i[0]
    if q == a:
        continue
    else:
        br_.append(i)
    q = a

ans = []
w = br_[0]
for i in br_[1:]:
    if i[0] < w[1]:
        w = [i[0], min(i[1], w[1])]
    else:
        ans.append(w)
        w = i

print(len(ans)+1)

Solution (Python):
N, M = map(int, input().split())
ab = sorted(set(map(lambda x: (x[0], x[1]) if x[0] < x[1] else (x[1],x[0]), [list(map(int, input().split())) for _ in range(M)])))

ans = 0
e = 10**6
for m in ab:
    a, b = m
    if e <= a:
        ans += 1
        e = b
    if b < e:
        e = b
print(ans + 1)

Solution (Python):
def merge(arr, l, m, r):
    n1 = m - l + 1
    n2 = r- m
 
    
    L = [0,0] * (n1)
    R = [0,0] * (n2)
 
    
    for i in range(0 , n1):
        L[i] = arr[l + i]
 
    for j in range(0 , n2):
        R[j] = arr[m + 1 + j]
 
    
    i = 0     
    j = 0     
    k = l     
 
    while i < n1 and j < n2 :
        if L[i][0] <= R[j][0]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1
 
    
    
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1
 
    
    
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1
 


def mergeSort(arr,l,r):
    if l < r:
 
        
        
        m = (l+(r-1))//2
 
        
        mergeSort(arr, l, m)
        mergeSort(arr, m+1, r)
        merge(arr, l, m, r)
n,m=map(int,input().split())
arr=[]
for i in range(m):
    arrx=list(map(int,input().split()))
    arr.append(arrx)
mergeSort(arr,0,m-1)
ans=0
x1=arr[0][0]
y1=arr[0][1]
for i in range(m):
    if(arr[i][0]>=y1):
        ans+=1
        x1=arr[i][0]
        y1=arr[i][1]
    else:
        x1=max(x1,arr[i][0])
        y1=min(y1,arr[i][1])
ans+=1
print(ans)

Solution (Python):


n,m = list(map(int,input().split()))

k = []
for _ in range(m):
    k.append(list(map(int,input().split())))

k.sort(key=lambda x:x[1])


l=0
ans = 0
for i in range(m):

    if l <= k[i][0]:
        ans += 1
        l = k[i][1]
    
    
print(ans)

Solution (Python):
N, M = [int(s) for s in input().split()]
L = [[int(s) for s in input().split()] for _ in range(M)]

L.sort()

c = 0
pa, pb = 0, 0
for a, b in L:
    if pb <= a:
        c += 1
        pa, pb = a, b
    else:
        pa, pb = max(pa, a), min(pb, b)

print(c)

Solution (Python):
from operator import itemgetter

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]

ab = sorted(ab, key=itemgetter(1))

ans = 1
limit = ab[0][1]

for i in range(1, m):
	if ab[i][0] >= limit:
		ans += 1
		limit = ab[i][1]

print(ans)

Solution (Python):
from collections import defaultdict
N,M = map(int,input().split())

D = defaultdict(lambda: N+1)
for i in range(M):
    a,b = map(int,input().split())
    if b<D[a]:D[a]=b
        
side_b_min = N+1
ans = 0
for i in range(1,N+1):
    if i == side_b_min:
        side_b_min = N+1
        ans += 1
    if D[i] < side_b_min: side_b_min = D[i]
    
    
print(ans)

Solution (Python):

def inpl(): return list(map(int, input().split()))
N, M = inpl()

E = []
for _ in range(M):
    E.append(inpl())

E = sorted(E, key=lambda x: [x[1], x[0]])

ans = 0
c = 0
for a, b in E:
    if a < c:
        continue
    else:
        ans += 1
        c = b
print(ans)

Solution (Python):


n, m = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(m)]
A.sort(key=lambda x: x[1])

count = 0
start = -1
for a in A:
    if a[0] >= start:
        count += 1
        start = a[1]
print(count)

Solution (Python):
N, M = map( int, input().split())
Q = []
for i in range(M):
    a,b = map(int,input().split())
    Q.append([a,b])
Q = sorted(Q)
ans = 1
LQ = len(Q)
while LQ != 0:
    stan = Q[0][1]
    k = 1
    while LQ != 0:
        if Q[0][0] < stan:
            stan = min(stan,Q.pop(0)[1])
            LQ -= 1
        else:
            ans += 1
            break
print(ans)

Solution (Python):
N, M = [int(_) for _ in input().split()]
AB = [tuple(int(_) for _ in input().split()) for i in range(M)]

AB.sort()

result = 1

x1, x2 = 1, N
for a, b in AB:
    
    if x2 <= a:
        
        result += 1
        x1, x2 = a, b
    else:
        x1 = max(x1, a)
        x2 = min(x2, b)

print(result)

Solution (Python):
import sys

N, M = map(int, sys.stdin.readline().split())
ab = sorted([list(map(int, sys.stdin.readline().split()))
             for _ in range(M)])

left, right = None, None
cnt = 0

for a, b in ab:
    a, b = min(a, b), max(a, b)
    if left is None:
        left, right = a, b
        continue
    if a < right and b > left:
        left = max(left, a)
        right = min(right, b)
    else:
        cnt += 1
        left, right = a, b

print(cnt + 1)

Solution (Python):
n, m = list(map(int, input().split()))

demands = []
for i in range(m):
    a, b = list(map(int, input().split()))
    demands.append((b, a))

demands = sorted(demands)
last_splited = -1
splited = 0

for end, start in demands:
    if last_splited < end and start >= last_splited:
        last_splited = end
        splited += 1

print(splited)

Solution (Python):
n,m = (int(i) for i in input().split())
x = [[int(i) for i in input().split()] for i in range(m)]
x,a,b,ans = sorted(x),0,n+1,0
for i,j in x:
	if i>=a and j<=b: a,b = i,j
	elif b>i>=a: a = i
	elif j<=b: b = j
	else: ans,a,b = ans+1,i,j
print(ans+1)

Solution (Python):
N,M = map(int, input().split())
AB = []
for _ in range(M):
    AB.append(list(map(int,input().split())))

AB.sort(key=lambda x:x[1])

cur = 0
ans = 0
for a,b in AB:
    if cur > a:
        continue
    
    ans += 1
    cur = b

print(ans)

Solution (Python):
import sys
N, M = map(int, sys.stdin.readline().split())
lst = []
for i in range(M):
    a, b = map(int, sys.stdin.readline().split())
    lst.append((a, 1, i))
    lst.append((b, 0, i))
lst.sort()
open_set = set()
cnt = 0
for pos, t, idx in lst:
    if t == 0:
        if idx in open_set:
            cnt += 1
            open_set = set()
    else:
        open_set.add(idx)
print(cnt)

Solution (Python):
N,M = map(int,input().split())
src = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]
src.sort()

ans = 0
minb = N
for a,b in src:
    if a >= minb:
        ans += 1
        minb = b
    else:
        minb = min(minb,b)
if src[-1][0] < minb:
    ans += 1
print(ans)

Solution (Python):
n, m = map(int, input().split())
e = []
for i in range(m):
  e.append(list(map(int, input().split())))

e.sort(key=lambda x:x[1])
ret = 0

l = 0
for i in range(m):
  if e[i][0] < l:
    continue
  else:
    l = e[i][1]
    ret += 1
    
print(ret)

Solution (Python):
n,m=map(int,input().split())
s=[[0]*m for _ in range(2)]
for k in range(m):
	i,j=map(int,input().split())
	s[1][k]=i
	s[0][k]=j

u=sorted([list(x) for x in list(zip(*s))])

s0=0
ans=0
for i in range(m):
	if s0<=u[i][1]:
		s0=u[i][0]
		ans+=1
print(ans)

Solution (Python):
N, M = map(int, input().split())
A = []
for i in range(M):
  a, b = map(int, input().split())
  A.append([a - 1, b - 1])
A = sorted(A, key=lambda a: a[0])
cut = 1
b_min = N
for a in A:
  if a[0] >= b_min:
    cut += 1
    b_min = N
  b_min = min(b_min, a[1])
print(cut)