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):
import sys
input = sys.stdin.readline

def main():
    N, M = map(int, input().split())
    a_b = sorted([list(map(int, input().split())) for _ in range(M)])
    used = [0] * M
    ans = 0
    for i in range(M):
        k = M - i - 1
        if used[k]:
            continue
        used[k], c = 1, a_b[k][0]
        for j in range(k):
            if a_b[j][0] <= c < a_b[j][1]:
                used[j] = 1
        ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
def main():
    N, M = map(int, input().split())
    a_b = sorted([list(map(int, input().split())) for _ in range(M)])
    used = [0] * M
    ans = 0
    for i in range(M):
        k = M - i - 1
        if used[k]:
            continue
        used[k], c = 1, a_b[k][0]
        for j in range(k):
            if a_b[j][0] <= c < a_b[j][1]:
                used[j] = 1
        ans += 1
    print(ans)

if __name__ == "__main__":
    main()

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

cnt = 1
posi = AB[0][1]
for i in range(1, M):
    if AB[i][0] >= posi:
        cnt += 1
        posi = AB[i][1]

print(cnt)

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

data = [map(int,raw_input().split()) for i in xrange(M)]

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

ans = [data[0][1]-1]
cnt = 0

for i in xrange(M):
    if data[i][0] <= ans[cnt] and ans[cnt] < data[i][1]:
        continue
    else:
        cnt += 1
        ans.append(data[i][1]-1)

print cnt+1

Solution (Python):
n,m=map(int,input().split());x=y=0
for(a,b)in sorted([list(map(int,input().split()))for i in range(m)],key=lambda x:x[1]):
 if a>x:
  x=b-1
  y+=1
print(y)

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

q = sorted(q, key=lambda k: k[0])
q.append((10**5+1, 10**5+1))

t_min = 10**5 + 1
l = 0
r = 1
c = 0
for i in range(1, m + 1):
    if q[i][1] < t_min:
        t_min = q[i][1]
        
    if q[i][0] != q[i + 1][0]:
        if r <= q[i][0]:
            c += 1
            r = t_min
            
        else:
            if t_min < r:
                r = t_min
        l = q[i][0]
        t_min = 10**5 + 1
        
print(c)

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

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

count = 0
left = 0
for a in Ai:
    if a[0] >= left:
        left = a[1]
        count += 1
print(count)

Solution (Python):
n,m = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(m)]
a = sorted(a,key=lambda x:x[1])
ans = [0]
for a_ in a:
    if not a_[0] < ans[-1] <= a_[1]:
        ans.append(a_[1])
print(len(ans)-1)

Solution (Python):
n,m = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(m)]
a = sorted(a,key=lambda x:x[1])
ans = [0]
for a_ in a:
    for i,k in enumerate(ans):
        if a_[0]<k and a_[1]>=k:
            break
        elif i==len(ans)-1:
            ans.append(a_[1])
            break
print(len(ans)-1)

Solution (Python):

N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
AB=sorted(AB, key=lambda x: x[1])
bridges=[]
for i in range(M):
    if len(bridges) == 0:
        bridges.append(AB[i][1]-1)
    elif max(bridges)>=AB[i][0]:
        pass
    else:
        bridges.append(AB[i][1]-1)
print(len(bridges))

Solution (Python):
import bisect

n, m = map(int, input().split())
l = []

for _ in range(m):
  a, b = map(int, input().split())
  l.append((a,b))
  
l_ = sorted(l, key=lambda x:x[1])

ans = 0
rb = 0

for d in l_:
  if not d[0] <= rb < d[1]:
    rb = d[1]-1
    ans += 1
    
print(ans)

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


ans, r = 0, 0
for a, b in Data:
    if a >= r:
        ans += 1
        r = b

print(ans)

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

l = []

for i in range(m):
    a,b = map(int,input().split())
    l.append((a,b))
l.sort(reverse=True)

res = 0
while l:
    start,end = l.pop()
    while end > start and l:
        s,t = l[-1]
        start = max(s,start)
        end = min(t,end)
        if end >start:
            l.pop()
    res += 1

print(res)

Solution (Python):
a,b=(int(x)-1 for x in input().split())
L=[]
for i in range(b+1):
    L.append(list(map(int,input().split())))
L.sort(key=lambda x:x[1]) 
ans=0
bridge_right=-1


for l in L:
    if not l[0]<=bridge_right<l[1]:
        bridge_right=l[1]-1
        ans+=1
print(ans)

Solution (Python):
a,b=(int(x)-1 for x in input().split())
L=[]
for i in range(b+1):
    L.append(list(map(int,input().split())))
L.sort(key=lambda x:x[1]) 
ans=0
bridge_right=-1
for l in L:
    if not l[0]<=bridge_right<l[1]:
        bridge_right=l[1]-1
        ans+=1
print(ans)

Solution (Python):
from sys import stdin
N, M = map(int, input().split())
A = []
for _ in range(M):
    A.append([int(x) for x in stdin.readline().rstrip().split()])

A.sort(key=lambda x: x[1])
l = 0
ans = 0
for i in range(M):
    if l < A[i][0]:
        ans += 1
        l = A[i][1] - 1
    else:
        pass
print(ans)

Solution (Python):
def islands_war(N: int, M: int, AB: list)->int:
    latest_remvoed = 0
    removed_num = 0
    for a, b in sorted(AB, key=lambda x: x[1]):
        if a <= latest_remvoed:
            continue
        latest_remvoed = b - 1
        removed_num += 1
    return removed_num


if __name__ == "__main__":
    M = 0
    N, M = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in range(M)]
    ans = islands_war(N, M, AB)
    print(ans)

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

from operator import itemgetter
AB.sort(key=itemgetter(1))

ans = 0
lastcut = 0
for a, b in AB:
    if a < lastcut <= b:
        continue
    lastcut = b
    ans += 1

print(ans)

Solution (Python):
from collections import deque
N,M=map(int,input().split())
ab=[]
for i in range(M):
    a,b=map(int,input().split())
    ab.append([a,b])

ab.sort(key=lambda x :x[1])
ans=deque()
for i in ab:
    if len(ans)>0:
        if i[0]<ans[-1] :
            continue
    ans.append(i[1])
print(len(ans))

Solution (Python):
N, M = map(int, input().split())
lst = [tuple(map(int, input().split())) for _ in range(M)]
lst.sort(key=lambda x: x[1])
bridge = []
for war in lst:
    if bridge and war[0] <= bridge[-1]:
        continue
    bridge.append(war[1] - 1)
print(len(bridge))

Solution (Python):
N, M = map(int, input().split())
lst = [tuple(map(int, input().split())) for _ in range(M)]
lst.sort(key=lambda x: x[1])
bridge = []
for war in lst:
    if bridge and war[0] <= bridge[-1]:
        continue
    bridge.append(war[1] - 1)
print(len(bridge))

Solution (Python):
N,M=map(int,input().split())
requests=[]
ans=[]
for i in range(M):
    a,b=map(int,input().split())
    requests.append((a,b))
requests = sorted(requests, key=lambda t:t[1])
for req in requests:
    if len(ans) > 0:
        if req[0] <= ans[-1] and ans[-1] < req[1]:
            continue
    ans.append(req[1]-1)
print(len(ans))

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

ends = [[[], []] for _ in range(n+1)]
for i, (a, b) in enumerate(ab, start = 1):
    ends[a][0].append(i)
    ends[b][1].append(i)


ans = 0
orders = set([])
for start, end in ends:
    if len(end) > 0:
        rm_bridge = False
        for e in end:
            if e in orders:
                orders.remove(e)
                rm_bridge = True
        if rm_bridge:
            orders = set([])
        ans += int(rm_bridge)
    if len(start) > 0:
        for s in start:
            orders.add(s)
    
print(ans)

Solution (Python):


import sys


n,m = map(int, sys.stdin.readline().rstrip().split())
ab = [[0 for j in range(2)] for i in range(m)]
for i in range(m):
  ab[i] = list(map(int, sys.stdin.readline().rstrip().split()))
ab.sort(key=lambda x:x[1])

ans, last = [0, -1]
for a, b in ab:
  if a < last:
    continue
  else:
    ans += 1
    last = b

print(ans)

Solution (Python):
import heapq


def solve(N, M, a, b):
    q = []
    ret = 0
    conditions = sorted([(b[i], a[i]) for i in range(M)], key = lambda x: x[1])
    ci = 0
    for i in range(N+1):
        while ci < len(conditions) and i == conditions[ci][1]:
            heapq.heappush(q, conditions[ci])
            ci += 1
        if len(q) > 0 and i == q[0][0]-1:
            ret += 1
            q = []
    return ret





def main():
    N, M = list(map(int, input().split(' ')))
    a = []
    b = []
    for i in range(M):
        ai, bi = list(map(int, input().split(' ')))
        a.append(ai)
        b.append(bi)

    print(solve(N, M, a, b))



if __name__ == '__main__':
    main()

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

inf = 10**9
lefts = [inf for _ in range(n+1)]
for a, b in ab:
    lefts[a] = min(lefts[a], b-1)

right = -1
ans = 0
for i in range(1, n+1):
    if lefts[i] == inf:
        continue
    if i > right:
        ans += 1
        right = lefts[i]
    else:
        right = min(lefts[i], right)
print(ans)

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

ab = sorted(ab, key = lambda x: x[1])
a_cur = -1
ans = 0
for a, b in ab:
    if a_cur < a:
        ans += 1
        a_cur = b-1
    else:
        pass
print(ans)

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

ab=[]

for i in range(m):
    a=[int(j) for j in input().split()]
    ab.append(a)

from operator import itemgetter
ab.sort(key=itemgetter(1))

ans=1
b=[ab[0][1]-1]
for i in range(m):
    if not b[-1]>=ab[i][0] and b[-1]<ab[i][1]:
        b.append(ab[i][1]-1)
        ans+=1

print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
A=[]
for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    A.append([a,b])
A=sorted(A,key=lambda x:x[0],reverse=True)
cnt,b=0,n-1
for i in range(m):
    if A[i][1]<=b:
        cnt+=1
        b=A[i][0]
print(cnt)

Solution (Python):
from operator import itemgetter

n, m = map(int, input().split())
ab = sorted([tuple(map(int, input().split())) for i in range(m)], key=itemgetter(1))
removed = -1
ans = 0
for a, b in ab:
    if a > removed:
        removed = b - 1
        ans += 1
print(ans)

Solution (Python):
from operator import itemgetter

n, m = map(int, input().split())
ab = sorted([list(map(int, input().split())) for i in range(m)], key=itemgetter(1))
removed = -1
ans = 0
for a, b in ab:
    if a > removed:
        removed = b - 1
        ans += 1
print(ans)

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

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

removed = []

for a,b in _input:
    flag = False
    for i in removed:
        if a <= i < b:
            flag = True
            break
    if not flag:
        removed.append(b-1)

print(len(removed))

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

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

removed = []

for a,b in _input:
    flag = False
    for i in removed:
        if a <= i < b:
            flag = True
            break
    if not flag:
        removed.append(b-1)

print(len(removed))

Solution (Python):
N,M=map(int,input().split())
ab=[[0,0] for i in range(M)]
for i in range(M):
    ab[i][0],ab[i][1]=map(int,input().split())
r=0
ans=0
ab.sort()
for i in range(M):
    a=ab[i][0]
    b=ab[i][1]
    if a>=r:
        ans+=1
        r=b
    else:
        if b<r:
            r=b
print(ans)

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

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

ans = 0
start, end = 0, 0

for x in ls:
    if x[0] < end:
        continue
    else:
        ans += 1
        start = x[0]
        end = x[1]
print(ans)

Solution (Python):
def island_war():
    N, M = [int(i) for i in input().split()]
    data_ls = list()
    for i in range(M):
        data_ls.append([int(i) for i in input().split()])
    data_ls = sorted(data_ls, key=lambda x: x[1])
    drop_ls = list()
    cnt = 0
    while True:
        bridge = data_ls[0][1] - 1
        drop_ls.append(bridge)
        cnt += 1
        for ind, i in enumerate(data_ls):
            if i[0] <= bridge < i[1]:
                pass
            else:
                break
            if ind == len(data_ls) - 1:
                return cnt
        data_ls = data_ls[ind:]


print(island_war())

Solution (Python):
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
ab.sort(key = lambda x:x[1]);check = -1;count = 0
for i in range(m):
    if check >= ab[i][0]:continue
    check = ab[i][1]-1
    count += 1
print(count)

Solution (Python):

import sys
N,M  = map(int, input().split())

REQ  = [ [int(j) for j in line.split()] for line in sys.stdin.readlines()]
REQ = sorted(REQ, key=lambda x: x[1])

ans = 0
end  = -1
for i in range(M):
    r = REQ[i]

    if r[0] < end <= r[1]:
        continue
    else:
        end = r[1]
        ans += 1
print(ans)

Solution (Python):
n,m = [int(i) for i in input().split()]
e = [[int(j) for j in input().split()] for i in range(m)]
new_e =sorted(e,key= lambda x : x[1])
s=[]
for i in new_e:
  if s!= [] and i[0]<=s[-1]:
    pass
  else:
    s.append(i[1]-1)

print(len(s))

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

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

count = 0
last_removed = 0
for tpl in tpl_lst:
    if tpl[0] > last_removed:
        last_removed = tpl[1] - 1
        count += 1
print(count)

Solution (Python):
N,M=map(int,input().split())
bridges = [1]*N
islandswar = [[] for _ in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    islandswar[b].append(a)
count = 0
currightest = 0

def check(a,b):
    for i in range(a,b):
        if bridges[i] == 0:
            return False
    return True
    

for i in range(2,N+1):
    for j in range(0,len(islandswar[i])):
        if islandswar[i][j] >= currightest:
            if check(islandswar[i][j],i):
                bridges[i-1] = 0
                currightest = i
                count += 1

print(count)

Solution (Python):
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab.sort(key = lambda x:x[1])
i = 0
ans = 0
while i < m:
    right = ab[i][1] - 1
    ans += 1
    while ab[i][0] <= right < ab[i][1]:
        i += 1
        if i >= m:
            break
print(ans)

Solution (Python):
N, M = map(int, input().split())
ba = []
for i in range(M):
    a, b = map(int, input().split())
    ba.append((b, a))
ba.sort()
ans = 0
last = 0
for b, a in ba:
    if a >= last:
        ans += 1
        last = b
print(ans)

Solution (Python):
N,M=map(int,input().split())
L=[]
for i in range(M):
    a,b=map(int,input().split())
    L.append([b,a])
L.sort(reverse=True)
    
ans=1
P=L[0][1]
for i in range(M-1):
    if L[1+i][0]>P:
        P=max(P,L[1+i][1])
    else:
        ans+=1
        P=L[1+i][1]
print(ans)

Solution (Python):
from functools import reduce
from operator import itemgetter

N, M = map(int, input().split())
a, b = zip(*(map(int, input().split()) for _ in range(M)))
ts = sorted(zip(a, b), key=itemgetter(1))
ans = reduce(
    lambda acc, t: acc if t[0] < acc[1] else (acc[0] + 1, t[1]),
    ts,
    (0, 0)
)[0]
print(ans)

Solution (Python):
n, m = map(int, input().split())
ab = []
for i in range(m):
  ab.append(list(map(int, input().split())))
count = 0
while len(ab) > 0:
  c = float('inf')
  for i in range(len(ab)):
    if ab[i][1] < c:
      c = ab[i][1]
  count += 1
  tmp = []
  for i in range(len(ab)):
    if ab[i][0] >= c:
      tmp.append(ab[i])
  ab = tmp
print(count)

Solution (Python):

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

if M==0:
    print(0)
else:
    c=B[0][1]
    B.pop(0)
    count=1
    while B!=[]:
        if B[0][0]>=c:
            count=count+1
            c=B[0][1]
        B.pop(0)
        
        
    print(count)

Solution (Python):
n, m = map(int, input().split())
A = sorted([[int(i) for i in input().split()] for i in range(m)], key = lambda x: x[1])

cnt = 0
posi = 0
for s, g in A:
    if s >= posi:
        posi = g
        cnt += 1
        
print(cnt)

Solution (Python):
n, m = map(int, input().split())
SG = sorted([[int(i) for i in input().split()] for i in range(m)], key = lambda x: x[1])

cnt = 1
b = SG[0][1]
for s, g in SG:
    if s >= b:
        b = g
        cnt += 1
        
print(cnt)

Solution (Python):

from operator import itemgetter
from heapq import heappush, heappop

a,b = map(int, input().split())
li=[]
for i in range(b):
    s,f = map(int, input().split())
    li.append((s,f))

li = sorted(li, key=itemgetter(1), reverse=False)

ans = 1
t = li[0][1]

for i in range(1,b):
    if t <= li[i][0]:
        ans+=1
        t = li[i][1]
print(ans)

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

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

left = 0
cnt = 0
for i in range(M):
  if left <= req[i][0]:
    cnt += 1
    left = req[i][1]
    
print(cnt)

Solution (Python):
n, m = map(int, input().split())
ab = [list(map(int, input().split())) + [True] for _ in range(m)]
ab2 = sorted(ab, key=lambda x: x[1])
ab.sort()
count = 0
j = 0
for i in range(m):
    if not (ab2[i][2]):
        continue
    while j < m:
        if ab2[i][1] <= ab[j][0]:
            count += 1
            break
        else:
            ab[j][2] = False
        j += 1
print(count + 1)

Solution (Python):

n,m=map(int,input().split())
from collections import deque
branch=[]
for i in range(m):
    s,e=map(int,input().split())
    branch.append((s,e))
branch.sort(key=lambda x:x[1],reverse=True)
ans=0
before=0
while len(branch)>0:
    check=branch.pop()
    if before>=check[0]:continue
    else:
        before=check[1]-1
        ans+=1
print(ans)

Solution (Python):

n,m = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(m)]
rest = sorted(lst, key=lambda x:x[1], reverse=False)
ans = 1
et = rest[0][1] 
for i in range(len(rest)):
    if rest[i][0]>=et:
        et=rest[i][1]
        ans+=1
print(ans)

Solution (Python):


N,M =map(int,input().split(" "))

num =[]
for i in range(M):
    l,m =map(int,input().split(" "))
    x =[m,l]
    num.append(x)
num.sort()

t = num[0][0]
ans =1
for i in range(1,M):
    k =num[i][1]
    if t<=k:
        t = num[i][0]
        ans +=1
        
print(ans)

Solution (Python):
n,m = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(m)]
a = sorted(a, key=lambda x: x[1])

br = a[0][1]
cnt = 1
for i in range(m-1):
    if a[i+1][0] >= br:
        br = a[i+1][1]
        cnt += 1
print(cnt)

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

d.sort(key=lambda x:x[1])
ans=0
c=0
for i in range(M):
    a,b=d[i]
    if a>=c:
        ans+=1
        c=b
print(ans)

Solution (Python):


N, M = map(int, input().split())
R = []
for _ in range(M):
    a, b = map(int, input().split())
    R.append((a, b))

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

end, ans = 0, 0
for i in range(M):
    if R[i][0] >= end:
        end = R[i][1]
        ans += 1

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

g = 0
for p in a:
    if g <= p[0]:
        count += 1
        g = p[1]
        

print(count)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M = map(int, input().split())
cut = []
for _ in range(M):
    a, b = map(int, input().split())
    cut.append([a, b])

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

ans = 1
ind = 0


s = cut[ind][0]
e = cut[ind][1]
while ind < M:
    n_s, n_e = cut[ind]
    if n_s < e:
        e = min(e, n_e)
    else:
        s = n_s
        e = n_e
        ans += 1
    ind += 1


print(ans)

Solution (Python):
N,M = map(int,input().split())
demand = [list(map(int,input().split())) for _ in range(M)]
demand = sorted(demand,key=lambda x:(x[0],x[1]))
ans = M
for i in range(M):
    a = demand[i][0]; b = demand[i][1]
    if i == 0:
        l = a; r = b
        continue
    if a < r:
        l = a
        if b < r:
            r = b
        ans -= 1
    else:
        l = a; r = b
print(ans)

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

requests.sort(key=lambda x: x[1])
count = 0
end = 0
for r in requests:
    if r[0] >= end:
        count += 1
        end = r[1]
        
print(count)

Solution (Python):
def main():
    N, M = map(int, input().split())
    ab = [[int(i) for i in input().split()] for _ in range(M)]
    ab = sorted(ab, key=lambda x: x[1])
    last = ab[0][1] - 1
    ans = 1
    for a, b in ab[1:]:
        if last >= a:
            continue
        ans += 1
        last = b - 1
    print(ans)


main()

Solution (Python):
N,M = list(map(int,input().split()))
data = [list(map(int,input().split())) for j in range(M)]
data.sort(key = lambda x:x[1])
last = 0
cnt = 0
for i,j in data:
    if cnt == 0:
        last = j-1
        cnt += 1
    elif i <= last:
        continue
    else:
        last = j-1
        cnt += 1

print(cnt)

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

r = a_b[0][1]
ans = 1
for a, b in a_b[1:]:
    if a >= r:
        r = b
        ans += 1
        continue
    if b < r:
        r = b
print(ans)

Solution (Python):
import sys
from operator import itemgetter
input = sys.stdin.readline

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
AB.sort(key=itemgetter(1))
ans, right = 1, 10 ** 5 + 1
for a, b in AB:
    if a < right:
        right = min(b, right)
    else:
        ans += 1
        right = b
print(ans)

Solution (Python):


def main():
    na = list(map(int, input().split()))
    N, M = na[0], na[1]
    ab_list = []
    for i in range(M):
        na = list(map(int, input().split()))
        ab_list.append(na)

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

    pb = N + 1
    for i in range(M - 1, -1, -1):
        b = ab_list[i][1]
        if pb <= b:
            ab_list.pop(i)
        else:
            pb = b

    pb = 1
    count = 0
    for ab in ab_list:
        if pb <= ab[0]:
            pb = ab[1]
            count += 1


    print(count)


if __name__ == '__main__':
    main()

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
            break
print(ans)

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

L = [list(map(int,input().split())) for i in range(M)]
L = sorted(L, key=lambda x: x[1])

a = -1
ans = 0
for i in range(M) :
    if L[i][0] <= a :
        continue
    else :
        ans += 1
        a = L[i][1] - 1
print(ans)

Solution (Python):
import sys
from operator import itemgetter
input = sys.stdin.readline

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

AB.sort(key=itemgetter(1, 0))

ans = 1
tmp = AB[0][1]-1
for i in range(1, M):
    if AB[i][0] > tmp:
        ans += 1
        tmp = AB[i][1]-1

print(ans)

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

koe=[]

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

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


right=0
answer=0
for l,r in koe:
  if l>=right:
    right=r
    answer+=1

print(answer)

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

posi = A[0][1]
count = 1
for i in range(m):
    if posi <= A[i][0]:
        count += 1
        posi = A[i][1]
        
print(count)

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

ans = 0
x = 0
for i in range(m):
    if ab[i][0] <= x:
        continue
    else:
        x = ab[i][1] - 1
        ans += 1

print(ans)

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

ab = []
for i in range(0,M):
    inp = list(map(int,input().strip().split()))
    ab.append((inp[0],inp[1]))

abl = sorted(ab,key=lambda x: x[1])

rightest_cut = 0
count = 0

for m in abl:
    if m[0] <= rightest_cut:
        continue
    rightest_cut = m[1] -1
    count += 1

print(count)

Solution (Python):
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
l=sorted(l,key=lambda x:x[1])
start,ans=0,0
for i in range(m):
    if start<l[i][0]:
        start=l[i][1]-1
        ans+=1
print(ans)

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

c = 0
prevb = 0

for a, b in sorted(ab, key=lambda x: x[1]):
  if a >= prevb:
    c += 1
    prevb = b
print(c)

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

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

print(count)

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

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

Solution (Python):
N, M = [int(_) for _ in input().split()]
AB = sorted([[int(_) for _ in input().split()] for _ in range(M)])
l = 0
r = N + 1
ans = 1
for i in range(M):
    if AB[i][0] < r:

        r = min(r, AB[i][1])
    else:
        ans += 1
        r = AB[i][1]
    l = AB[i][0]
print(ans)

Solution (Python):
N, M = list(map(int, input().split()))
D = []
L = [0] * N
for i in range(M):
  D.append(list(map(int, input().split())))
D.sort(key = lambda x: x[1])

Ans = 0
Re = 0
for i in D:
  if Re < i[0]:
    Re = i[1]-1
    Ans += 1
print(Ans)

Solution (Python):


II = lambda: int(input())
MI = lambda: map(int, input().split())


def main():
    N, M = MI()
    ab = [tuple(MI()) for _ in range(M)]

    ab = sorted(ab, key=lambda x:x[1])
    lb = -1
    cnt = 0
    for a, b in ab:
        if lb <= a:
            lb = b
            cnt += 1
    return cnt


if __name__ == "__main__":
    print(main())

Solution (Python):
from operator import itemgetter

N, M = map(int, input().split())
ab = sorted([tuple(map(int, input().split())) for i in range(M)], key=itemgetter(1))
removed = -1
ans = 0
for a, b in ab:
    if a > removed:
        removed = b - 1
        ans += 1
print(ans)

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

ab.sort(key = lambda x:x[1])
dropped = [ab[0][1]-1]
for i in range(1, M): 
    if ab[i][0] > dropped[-1]:
        dropped += [ab[i][1]-1]

print(len(dropped))

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

cut, ans = 0, 0
for l, r in a:
    if l >= cut:
        ans += 1
        cut = r
print(ans)

Solution (Python):
n, m = map(int, input().split())
wars = []
for _ in range(m):
    wars.append(tuple(map(int, input().split())))
wars.sort(key = lambda x: x[1])
last_distruction = -1
distruction = 0
for l, r in wars:
    if l > last_distruction:
        distruction += 1
        last_distruction = r-1
print(distruction)

Solution (Python):
N,M=map(int,input().split())
AB=[[0,0] for i in range(M)]
for i in range(M):
    AB[i][0],AB[i][1]=map(int,input().split())
AB.sort(key=lambda x:x[0])
l=AB[0][0]
r=AB[0][1]
c=0
for i in range(1,M):
    if AB[i][0]<r:
        l=AB[i][0]
        if AB[i][1]<r:
            r=AB[i][1]
    else:
        c+=1
        l=AB[i][0]
        r=AB[i][1]
print(c+1)

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

cut, ans = 0, 0
for l, r in Requests:
    if l >= cut:
        ans += 1
        cut = r

print(ans)

Solution (Python):



def main():
    n, m = map(int, input().split())
    ab = sorted([list(map(int, input().split())) for _ in range(m)], key=lambda x: x[1])
    ans = 1
    axis = ab[0][1]

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

    print(ans)


if __name__ == '__main__':
    main()

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

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


pair.sort()

ans = 1
y, x = pair[0]

for i in range(1, M):
    b, a = pair[i]
    if y <= a:
        y = b
        ans += 1

print(ans)

Solution (Python):
from operator import itemgetter
n,m=map(int,input().split())
x=[]
for i in range(m):
    a,b=map(int,input().split())
    x.append([a,b])
x=sorted(x, key=itemgetter(1))
en=x[0][1]
count=1
for i in range(1,m):
    if en<=x[i][0]:
        en=x[i][1]
        count+=1
print(count)

Solution (Python):
N, M = [int(x) for x in input().split()]

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

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

ans = 0
while len(AB) != 0:
    cut = AB[0][1]
    newAB = []
    ans += 1
    for a, b in AB:
        if a < cut:
            pass
        else:
            newAB.append((a, b))
    AB = newAB

print(ans)