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



Sample input:
5 2
1 4
2 5


Sample output:
1

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ls = [list(map(int, input().split())) for _ in range(m)]
ls.sort()
res = 1
rmin = float('inf')
for l, r in ls:
    if l >= rmin:
        res += 1
        rmin = r
    else:
        rmin = min(rmin, r)

print(res)

Submission status: Accepted

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

r.sort()
i_l = r[0][0]
i_r = r[0][1]
cnt = 1
for i in range(1, M):
    if r[i][0] < i_r:
        i_r = min(i_r, r[i][1])
    else:
        cnt += 1
        i_l = r[i][0]
        i_r = r[i][1]
print(cnt)

Submission status: Accepted

Solution code:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    N,M = map(int, input().split())
    battles = [[] for _ in range(N)]
    for _ in range(M):
        a,b = map(int, input().split())
        battles[b-1].append(a-1)

    x = -1
    ans = 0
    for i in range(1,N):
        battle = battles[i]
        if len(battle) == 0: continue

        closest_idx = max(battle)
        if x < closest_idx:
            ans += 1
            x = i-1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#01:00
n,m = map(int,input().split())
check = [-1 for _ in range(n)]
for _ in range(m):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  check[b] = max(check[b],a)
#print(check)
ans = [0]
for i in range(n):
  if check[i] != -1:
    ans.append(max(ans[-1],ans[check[i]+1]+1))
  else:
    ans.append(ans[-1])
#print(ans)
print(ans[-1])

Submission status: Accepted

Solution code:
import sys
from pprint import pprint

n, m = map(int, sys.stdin.readline().strip().split(" "))

troubles = []
for _ in range(m):
    a, b = map(int, sys.stdin.readline().strip().split(" "))
    troubles.append((a, b))

breaked = -1
ans = 0
for a, b in sorted(troubles, key=lambda x: x[1]):
    # print(a, b)
    if a <= breaked < b:
        # print("pass")
        continue

    breaked = b - 1
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = [int(i) for i in input().split()]
# 終端でソート、昇順
ab = sorted([list(map(int,input().split())) for _ in [0]*M],key=lambda x:x[1])
x = cnt = 0
for(a,b)in ab:
  #終端ノードを超える始端ノードがあれば、カバー外なので追加
   if x < a:
      x = b - 1
      cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(M)]
ab.sort()
ans = 1
l, r = ab[0][0], ab[0][1]

for a,b in ab[1:]:
    if a < r:
        l = max(l,a)
        r = min(r,b)
    else:
        ans += 1
        l = a
        r = b 

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

from bisect import bisect_right

N,M = II()

a = []
b = []
for i in range(M):
    a0,b0 = II()
    a.append([a0-1,i])
    b.append([b0-2,i])

a.sort(key=lambda x:x[0])
b.sort(key=lambda x:x[0])
left = [a[i][0] for i in range(M)]
used = [False]*M

ans = 0
pb = 0
for r in b:
    if used[r[1]] == False:
        p = bisect_right(left,r[0])
        for i in range(pb,min(M,p)):
            used[a[i][1]] = True
        pb = p
        ans += 1
    else:
        continue

print(ans)

Submission status: Accepted

Solution code:
# ABC103D - Islands War
from operator import itemgetter as gt


def main():
    N, M, *AB = map(int, open(0).read().split())
    Q = [(a, b) for a, b in zip(*[iter(AB)] * 2)]
    Q.sort(key=gt(1))
    ans, cur = 0, -1
    for a, b in Q:
        if a >= cur:  # need to break another bridge
            ans += 1
            cur = b
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC103D - Islands War
from operator import itemgetter as gt


def main():
    N, M, *AB = map(int, open(0).read().split())
    Q = [(a, b) for a, b in zip(*[iter(AB)] * 2)]
    Q.sort(key=gt(1))
    ans, cur = 0, -1
    for a, b in Q:
        if not a < cur <= b:
            ans += 1
            cur = b
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC103D - Islands War
from operator import itemgetter as gt


def main():
    N, M, *AB = map(int, open(0).read().split())
    Q = sorted([(a, b) for a, b in zip(*[iter(AB)] * 2)], key=gt(1))
    ans, cur = 0, -1
    for a, b in Q:
        if not a < cur <= b:
            ans += 1
            cur = b
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
Q = [list(map(int, input().split())) for _ in range(M)]
Q.sort(key = lambda x: (x[1], x[0]))
b = 0
res = 0
for i in range(M):
  if Q[i][0] >= b:
    b = Q[i][1]
    res += 1
print(res)

Submission status: Accepted

Solution code:
# 自力
N, M = map(int, input().split())
AB = [0]*M
for i in range(M):
    a, b = map(int, input().split())
    AB[i] = a, b

def key(ab):
    a, b = ab

AB.sort()

a0, b0 = AB[0]
cnt = 1
for a, b in AB[1:]:
    #print(cnt, (a0, b0), " : ", (a, b))
    if b0 > a:
        a0 = max(a, a0)
        b0 = min(b, b0)
    else:
        a0, b0 = a, b
        cnt += 1
#print((a0,b0))
print(cnt)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
AB = [0]*M
for i in range(M):
    a, b = map(int, input().split())
    AB[i] = a, b

def key(ab):
    a, b = ab

AB.sort()

a0, b0 = AB[0]
cnt = 1
for a, b in AB[1:]:
    #print(cnt, (a0, b0), " : ", (a, b))
    if b0 > a:
        a0 = max(a, a0)
        b0 = min(b, b0)
    else:
        a0, b0 = a, b
        cnt += 1
#print((a0,b0))
print(cnt)

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    query = []
    for _ in range(M):
        a, b = map(int, input().split())
        query.append([a,b])

    sort_query = sorted(query)

    cnt = 1
    left = 0
    right = float('inf')
    for i, j in sort_query:
        if max(left,i) >= min(right,j):
            cnt += 1
            left = i
            right = j
            continue
        left = max(left,i)
        right = min(right,j)

    print(cnt)
main()

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
ab = []
for i in range(m):
    point = list(map(int, input().split()))
    ab.append(point)
ab.sort(key=lambda x:x[0], reverse=True)
ans = 0
right = 1e7
left = 0
for i in range(m):
    left = max(left, ab[i][0])
    right = min(right, ab[i][1])
    if left>=right:
        left=ab[i][0]
        ans +=1

    if i==m-1 and left<right:
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
requires = [tuple(map(int, input().split())) for _ in range(M)]
requires.sort()
cnt = 0
last = 0
for require in requires:
  if last <= require[0]:
    cnt += 1
    last = require[1]
  last = min(last, require[1])
print(cnt)

Submission status: Accepted

Solution code:
N,M = [int(i) for i in input().split()]
wars = [[int(i) for i in input().split()] for _ in range(M)]

wars.sort(key=lambda x:x[1],reverse=False)
r = set()
for war in wars:
    for i in r:
        if war[0] <= i and i <= war[1]:
            break
    else:
        r.add(war[1]-1)
    

print(len(r))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def solve():
  n,m = (int(i) for i in input().split())
  query = []
  for i in range(m):
    a,b = (int(i) for i in input().split())
    query.append((b-1,a-1))
  query.sort()
  ans = 0
  remove = 10**15
  for i in range(m):
    b,a = query[i]
    if a > remove or remove >= b:
        ans += 1
        remove = b-1
  print(ans)
    
solve()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def main():
    N,M = map(int,input().split())
    X = [list(map(int,input().split())) for _ in range(M)]
    X.sort(key=lambda X:(X[1],-X[0]))
    count = 1
    left = X[0][1]
    for i in range(M):
        if X[i][0] >= left:
            count += 1
            left = X[i][1]

    print(count)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
ts=time.time()
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
show_flg=False
#show_flg=True

ans=0
n,m=MI()
ed=[-1]*n
bg=[[] for _ in range(n)]
A=[0]*n
B=[0]*n
r=[]
for i in range(m):
    a,b=LI_()
    r+=[(a,b)]
    bg[a].append(b)
    ed[a]=b
    A[a]+=1
    B[b]+=1

show(r,A,B)
q=[]
for i in range(n):
    show(i,'q=',q,ans,end=' | ')
    if B[i]>0:
        ans+=1
        for j in q:
            B[j]-=1
        q=[]
    if A[i]>0:
        q+=bg[i]
    show(i,'q=',q,'ans=',ans,'A,B=',A,B)    
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
st=[list(map(int,input().split())) for _ in [0]*m]
st.sort(key=lambda x:(x[1],x[0]))
now,cnt=0,0
for s,t in st:
    if now<=s:
        cnt+=1
        now=t
print(cnt)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    N, M = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in [0]*M]
    ab = sorted(ab, key=lambda x: x[1])
    cnt = 0
    ans = 0
    for a, b in ab:
        if ans < a:
            ans = b - 1
            cnt += 1
    print(cnt)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
maxa = [0] * (N+1)

for i in range(M):
    a,b = map(int,input().split())
    if maxa[b] < a:
        maxa[b] = a 

ok = 0
count = 0

for j in range(1,N+1):
    if ok < maxa[j]:
        count += 1
        ok = j-1

print(count)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
info = []
maxa = [0] * (N+1)

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

ok = 0
count = 0

for j in range(1,N+1):
    if ok < maxa[j]:
        count += 1
        ok = j-1

print(count)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
info = []

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

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

ok = 0
count = 0

for i in range(M):
    if info[i][0] > ok:
        count += 1
        ok = info[i][1] - 1

print(count)

Submission status: Accepted

Solution code:
from operator import itemgetter
n,m=map(int,input().split())
L=[]
for _ in range(m):
    a,b=map(int,input().split())
    L.append([a,b])
L.sort(key=itemgetter(1))
cut=0
cnt=0
for i in L:
    if not (i[0]<=cut<i[1]):
        cut=i[1]-1
        cnt+=1
print(cnt)

Submission status: Accepted

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

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

for x, y in box:
    if cut <= x:
        count += 1
        cut = y

print(count)

Submission status: Accepted

Solution code:
N, M, *AB = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    E[a].append(b)

dp = [0] * (N + 1)
for i in range(1, N + 1):
    dp[i] = max(dp[i], dp[i - 1])
    for j in E[i]:
        dp[j] = max(dp[j], dp[i] + 1)

print(dp[N])

Submission status: Accepted

Solution code:
N, M, *AB = map(int, open(0).read().split())
L = [(a, b) for a, b in zip(*[iter(AB)] * 2)]

L.sort(key=lambda t: t[1])

ans = end = 0
for a, b in L:
    if a >= end:
        end = b
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
box=[list(map(int,input().split())) for i in range(m)]
box=sorted(box,key=lambda x:x[1])
count,cut=0,0

for x,y in box:
    if cut<=x:
        count +=1
        cut=y
        
print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


n, m = LI()
S = sorted(LIR(m), key=lambda x:x[1])



cnt = 0
ret = 0
for i in S:
    if i[0] >= ret:
        cnt += 1
        ret = i[1]


print(cnt)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab=[0]*m
for i in range(m):
    ab[i] = [int(x) for x in input().split()]
ab.sort()
ans = 1
key = ab[0][1]
for i in range(m):
    if ab[i][0] >= key:
        ans += 1
        key = ab[i][1]
    elif ab[i][1] < key:
        key = ab[i][1]
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    N,M = map(int,input().split())
    
    A = [list(map(int,input().split())) for i in range(M)]
    A = sorted(A, key=lambda x:x[1])
    A = sorted(A, key=lambda x:x[0])
    
    maxmin = float("inf")
    ans = 0
    for i in range(M):
        a,b = A[i]
        if maxmin <= a:
            ans += 1
            maxmin = b
        elif b < maxmin:
            maxmin = b
    ans += 1
    print(ans)
    
    
    
    
main()

Submission status: Accepted

Solution code:
N, M = (int(x) for x in input().split())
task_list = [
    {
        "index": i,
        "a": 0,
        "b": 0,
    } for i in range(M)
]
for i in range(M):
    task_list[i]["a"], task_list[i]["b"] = (int(x) for x in input().split())

task_list.sort(key=lambda x:x["b"])
ans, pointer = 0, 0
while pointer < M-1:
    task = task_list[pointer]
    j = 1
    while pointer+j < M and task_list[pointer+j]["a"] <= task["b"]-1/2\
    and task["b"]-1/2 <= task_list[pointer+j]["b"]:
        j += 1
    else:
        ans += 1
        if pointer+j == M:
            print(ans)
            exit()
        else:
            pointer += j
else:
    print(ans+(M-pointer))

Submission status: Accepted

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

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

bridge = n
ans = 0
for i in range(m):
    count = True
    if a[m - i - 1][1] > bridge:
        count = False
            
    if count:
        ans += 1
        bridge = a[m - i - 1][0]

print(ans)

Submission status: Accepted

Solution code:
#入力
n, m = map(int, input().split())
itv = []
for i in range(m):
    a, b = map(int, input().split())
    itv.append([b,a])
itv.sort()

cut = 0
ans = 0
for i in range(m):
    if itv[i][1] <= cut:
        i = i + 1
    else:
        cut = itv[i][0] - 1
        ans = ans + 1
        i = i + 1
        
print(ans)

Submission status: Accepted

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

c = E[0]
cnt = 0
for i in range(1,M):
	if c[0] <= E[i][0] < c[1]:
		c = [max(c[0],E[i][0]), min(c[1],E[i][1])]
	else:
		cnt += 1
		c = E[i]

print(cnt+1)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline

n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(m)]
ab.sort()
ans=0
memo=-1

for i in range(m):
   if memo<ab[i][0]:
      ans+=1
      memo=ab[i][1]-1
   elif memo>ab[i][1]:
      memo=ab[i][1]-1
   else:
      pass

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
query = [[] for _ in range(N + 1)]
for i in range(M):
    a, b = map(int, input().split())
    query[a].append(b)
nearest = [0] * (N + 1)
for i in range(1, N + 1):
    nearest[i] = min(query[i]) if len(query[i]) > 0 else 0

ans = 0
a_current = 0
b_current = N + 1
for i in range(1, N + 1):
    if nearest[i] > 0:
        a = i
        b = nearest[i]
        if a >= b_current:
            ans += 1
            a_current = a
            b_current = b
        else:
            a_current = a
            b_current = min(b_current, b)
ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
l=[[0,0] for _ in range(m)]
for i in range(m):
    l[i][1],l[i][0]=map(int,input().split())

l=sorted(l)

ans=1

c=l[0][0]
for i in range(m):
    if l[i][1]>=c:
        ans+=1
        c=l[i][0]
    else:
        continue
print(ans)

Submission status: Accepted

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

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

bridge_i = 0
cnt = 0
for i in range(m):
    if ab[i][0] > bridge_i:
        bridge_i = ab[i][1] - 1
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
bridge=[]
for i in range(M) :
    array =list(map(int,input().split()))
    bridge.append(array)
bridge =  (sorted(bridge,key=lambda x : x[1]))
result = 0
B = 0

for i in range(M):
    a, b = bridge[i]
    if a>=B :
        B=b
        result+=1

print(result)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
reqs = []
ans = 0
B = 0
for _ in range(M):
    a, b = map(int, input().split())
    reqs.append((a, b))
reqs = sorted(reqs, key=lambda x: x[1])
for i in range(M):
    a, b = reqs[i]
    if a >= B:
        B = b
        ans += 1
print(ans)

Submission status: Accepted

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

list_a = []
for m in range(M):
  list_a.append(list(map(int,input().split(' '))))

list_a.sort()

i = 0
cnt_break = 0
flg = False

while True:
  right = list_a[i][1]
  
  while list_a[i][0] < right:
    if i == M-1:
      flg = True
      break
    
    right = min(right,list_a[i][1])
    i += 1

  cnt_break += 1
      
  if flg:
    break
    
  
print(cnt_break)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

    B = 0
    ans = 0
    for i in range(M):
        a, b = ab[i]
        if a >= B:
            B = b
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

req = []
for i in range(m):
    a,b = map(int,input().split())
    req.append([a,b])
req.sort(key=lambda x:x[1])
bef = -1
ans = 0
# print(req)
for i in range(m):
    if req[i][0] > bef:
        ans += 1
        bef = req[i][1]-1
    # print(bef,ans)

print(ans)

Submission status: Accepted

Solution code:
def bridge_break(reqs):
    reqs.sort()
    ps = 0
    out = 0

    for req in reqs:
        if req[1] >= ps:
            out += 1
            ps = req[0]

    return out


n, m = map(int, raw_input().split())
reqs = []
for _ in range(m):
    st, end = map(int, raw_input().split())
    reqs.append((end, st))

print bridge_break(reqs)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
frontiers = {}
for i in range(m):
  a, b = map(int, input().split())
  if a in frontiers.keys():
    frontiers[a] = min(frontiers[a], b)
  else:
    frontiers[a] = b

cuts = 0
frontier = 10**6

for i in range(1, n):
  if i in frontiers.keys():
    frontier = min(frontier, frontiers[i])
  if i + 1 == frontier:
    cuts += 1
    frontier = 10**6
    
print(cuts)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
wars = {}
for i in range(m):
  a, b = map(int, input().split())
  if a in wars.keys():
    wars[a] = min(wars[a], b)
  else:
    wars[a] = b

cuts = 0
antis = 10**6

for i in range(1, n):
  if i in wars.keys():
    antis = min(antis, wars[i])
  if i + 1 == antis:
    cuts += 1
    antis = 10**6
    
print(cuts)

Submission status: Accepted

Solution code:
from operator import itemgetter
n, m = map(int, input().split())

ab = [tuple(map(int, input().split())) for i in range(m)]

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

count = 0
cut = 0
for i in range(m):
    if cut <= ab[i][0]:
        count += 1
        cut = ab[i][1]

print(count)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
ab.sort(key = lambda x:x[1])
point = 0 
cnt = 0
for a, b in ab:
  if a < point:
    continue
  else:
    cnt += 1
    point = b
print(cnt)