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):
N, M = map(int, input().split())
ab = [[int(x) for x in input().split()] for _ in range(M)]

ab = sorted(ab, key=lambda x: (x[0], x[1]))
cnt = 1
left, right = ab[0]
for a, b in ab[1:]:
    if b <= left or right <= a:
        cnt += 1
        left, right = a, b
    else:
        left = max(left, a)
        right = min(right, b)
print(cnt)

Solution (Python):
n, m = map(int, input().split())
ab = sorted([list(map(int, input().split())) for _ in range(m)], key = lambda x: x[1])
count = 1
broken = ab[0][1]-1
for i in range(m):
    if ab[i][0] <= broken:
        continue
    else:
        count += 1
        broken = ab[i][1]-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])
ans = 0
x = 0
for a,b in AB:
    if a <= x:
        continue
    x = b-1
    ans += 1
print(ans)

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

Q.sort(key=lambda x: x[1])
ans = 0
prev = 0
for ai, bi in Q:
    if prev < ai:
        ans += 1
        prev = bi - 1
print(ans)

Solution (Python):
n, m = map(int, input().split())
lst = []
for _ in range(m):
    a, b = map(int, input().split())
    lst.append((a, b))
sor = sorted(lst, key=lambda x:x[1])
spl = -1
cnt = 0
for a, b in sor:
    if a<=spl:
        continue
    else:
        spl = b-1
        cnt += 1
print(cnt)

Solution (Python):
n,m=map(int,input().split())
ab=[]
for _ in range(m):
  ab.append(tuple(map(int,input().split())))
ab=sorted(ab, key=lambda x: x[1])
lastbridge=0
cnt=0
for i in range(m):
  st=ab[i][0]
  go=ab[i][1]
  if st<=lastbridge<go:
    continue
  else:
    cnt+=1
    lastbridge=go-1
  

print(cnt)

Solution (Python):

"""
できるだけ右端に寄せればいいのでは？
区間の終わりが来た時にキューの中身を空にして全部終わりにする
"""
from collections import deque

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

a = []
b = []

for i in range(M):

    A,B = map(int,input().split())
    a.append([A-1,i])
    b.append([B-1,i])

q = deque([])
end = [False] * (M)
ans = 0

ai = 0
bi = 0
a.sort()
b.sort()
a.append([float("inf"),0])
b.append([float("inf"),0])

for i in range(2*M):

    

    if a[ai][0] < b[bi][0]:
        q.append(a[ai][1])
        ai += 1
    else:
        if end[b[bi][1]]:
            bi += 1
        else:
            loop = len(q)
            ans += 1
            for j in range(loop):

                now = q.popleft()
                end[now] = True
            bi += 1

print (ans)

Solution (Python):
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


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

AB.sort()

counts = np.zeros(N, dtype=int)
stack = []
ans = 0
p = 0
for a, b in AB:
    a -= 1
    b -= 1
    while True:
        if counts[p] > 0:
            while stack:
                r = stack.pop()
                counts[r] -= 1
            ans += 1
        if p >= a:
            break
        p += 1
    stack.append(b)
    counts[b] += 1
    
if stack:
    ans += 1
print(ans)

Solution (Python):

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

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

ab = [tuple([ab[i][0], ab[i][1], i]) for i in range(M)]
ans = 1
tmp = 0

a = sorted(ab, key=lambda x: x[0])
b = sorted(ab, key=lambda x: x[1])

checked = set()

for i in range(M):
    if b[tmp][1] <= a[i][0]:
        ans += 1
        while(b[tmp][1] <= a[i][0] or b[tmp][2] in checked):
            tmp += 1
    checked.add(a[i][2])

print(ans)

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


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

ans = 1
tmp = 0

a = sorted(ab, key=lambda x: x[0])
b = sorted(ab, key=lambda x: x[1])

checked = set()

for i in range(M):
    if b[tmp][1] <= a[i][0]:
        ans += 1
        while(b[tmp][1] <= a[i][0] or b[tmp][2] in checked):
            tmp += 1
    checked.add(a[i][2])


print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = [list(map(int,input().split())) for i in range(m)]
a.sort(key=lambda x:x[1])
bridge = [a[0][1]-1]
for i in range(1,m):
    if a[i][0] > bridge[-1]:
        bridge.append(a[i][1]-1)
print(len(bridge))

Solution (Python):
import sys
import numpy as np
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    a,b=[0]*M,[0]*M
    for i in range(M):
        a[i],b[i]=map(int,input().split())
    a_argsorted=np.argsort(a)
    a_max=0
    b_min=INF
    ans=1
    for i in a_argsorted:
        a_max=a[i]
        b_min=min(b_min,b[i])
        if a_max>=b_min:
            ans+=1
            b_min=b[i]
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
N,M=[int(x) for x in str(input()).split()]
X=[]
for i in range(M):
  t=[int(x) for x in str(input()).split()]
  X.append(t)

X.sort()

temp=N+1
ans=0
for j in range(1,M+1):
  if not (X[-j][0]<=temp and temp<=X[-j][1]):
    temp=X[-j][0]+1
    
    ans+=1

print(ans)

Solution (Python):
def solve():
    from sys import stdin
    f_i = stdin
    
    N, M = map(int, f_i.readline().split())
    ab = [tuple(map(int, f_i.readline().split())) for i in range(M)]
    ab.sort()
    
    ans = 1
    t = N
    for a, b in ab:
        if a >= t:
            ans += 1
            t = N
        t = min(t, b)
    
    print(ans)

solve()

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

for x in island:
    x.sort()
island.sort(key = lambda t: t[0], reverse = True)

ans = 0
broken = island[0][1]
for x in island:
    if x[0] <= broken < x[1]:
        pass
    else:
        ans += 1
        broken = x[0]
print(ans)

Solution (Python):
import sys

n, m, *ab = map(int, sys.stdin.read().split())
ab = sorted(zip(*[iter(ab)] * 2))

def main():
    r = ab[0][1]
    cnt = 0
    for a, b in ab[1:]:
        if a < r:
            if b < r:
                r = b
            continue
        else:
            cnt += 1
            r = b
    cnt += 1
    return cnt

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
import sys

n, m, *ab = map(int, sys.stdin.read().split())
ab = sorted(zip(*[iter(ab)] * 2))

def main():
    r = -1
    cnt = 0
    for a, b in ab:
        if a < r:
            if b < r:
                r = b
            continue
        else:
            cnt += 1
            r = b
    return cnt

if __name__ == '__main__':
    ans = main()
    print(ans)

Solution (Python):
N, M = map(int, input().split())
ablist = sorted([tuple(map(int, input().split())) for _ in range(M)], key=lambda x: x[1])
broken = 0
ans = 0
for a, b in ablist:
    if a > broken:
        ans += 1
        broken = b - 1
print(ans)

Solution (Python):
from operator import itemgetter

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

l = sorted([list(map(int,input().split())) for i in range(m)],key=itemgetter(1))



check = -1
count = 0
for a,b in l:
  if a > check:
    count += 1
    check = b-1

print(count)

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

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

max_a = a_b_list[0][0]
min_b = a_b_list[0][1]
count = 1

for a_b in a_b_list[1:]:
    

    if a_b[0] < min_b:
        min_b = min(min_b, a_b[1])
    else:
        count += 1
        min_b = a_b[1]

print(count)

Solution (Python):



def greedy():
    cnt = 0
    while len(E) > 0:
        edge = E.pop()
        cnt += 1
        while len(E) > 0 and E[-1][0] < edge[1]:
            E.pop()
    
    return cnt
    

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], reverse = True)

result = greedy()
print(result)

Solution (Python):
from operator import itemgetter

n, m = map(int, input().split())
r = sorted([list(map(int, input().split())) for _ in range(m)], key = itemgetter(0))


last = 0
count = 0
for i in range(m):
    if last > r[i][1]:
        last = r[i][1]
    elif last <= r[i][0]:
        count += 1
        last = r[i][1]

print(count)

Solution (Python):
N,M=map(int,input().split())
H=[list(map(int,input().split()))for _ in range(M)]
H.sort()
a=H[-1][0]
s=1
for i in range(M-2,-1,-1):
 if H[i][1]<=a:
  s+=1
  a=H[i][0]
print(s)

Solution (Python):
N,M=map(int,input().split())
H=[list(map(int,input().split()))for _ in range(M)]
H.sort()
a=H[-1][0]
s=1
for i in range(M-2,-1,-1):
    if H[i][1]<=a:
        s+=1
        a=H[i][0]
print(s)

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

Solution (Python):
def main():
    n, m = map(int, input().split())
    D = [list(map(int, input().split())) for _ in range(m)]
    D.sort()
    result = 1
    checker = D[0][1]
    for i in range(m):
        if checker <= D[i][0]:
            result += 1
            checker = D[i][1]
        elif checker > D[i][1]:
            checker = D[i][1]
    print(result)
if __name__ == '__main__':
    main()

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

ans = 0
idx = 0
for l in ls:
    if idx <= l[0]:
        idx = l[1]
        ans += 1

print(ans)

Solution (Python):

from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations
import sys
import bisect
import string
import math
import time
from fractions import gcd



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 StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['Yes', 'No']
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)



show_flg = True


def main():
    N, M = MI()
    ab = [None] * M

    for i in range(M):
        a, b = MI()
        ab[i] = (a, b)

    ab = sorted(ab, key=lambda x: x[1])
    
    bridge = [(ab[0][1]-1, ab[0][1])]

    for i in range(1, len(ab)):
        
        if ab[i][0] <= bridge[-1][0] and ab[i][1] >= bridge[-1][1]:
            pass
        else:
            bridge.append((ab[i][1]-1, ab[i][1]))

    print(len(bridge))


if __name__ == '__main__':
    main()

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


common=[[bri[0][0],bri[0][1]]]
j=0 

for i in range(1,m):
  a,b=bri[i]
  c,d=common[j] 
  if d<=a:
    common.append([a,b])
    j+=1
  else:
    c=a
    d=min(b,d)
    common[j][0]=c
    common[j][1]=d


print(len(common))

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

AB.sort()
INF = 10 ** 10

B_min = INF
answer = 0
for A, B in AB:
  if A >= B_min:
    answer += 1
    B_min = B
  else:
    B_min = min(B_min, B)
answer += 1

print(answer)

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):
def remove_path(islands,x,N):
    if x==0:
        islands[0].remove(1)
    elif x==N-1:
        islands[N-1].remove(N-2)
    else:
        islands[x].remove(x-1)
        islands[x-1].remove(x)

if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    orders=[tuple(map(int,input().split())) for i in range(M)]
    islands={i:[i-1,i+1] for i in range(1,N-1)}
    islands[0]=[1]
    islands[N-1]=[N-2]

    orders.sort(key=lambda x:x[1])
    flag=False
    last=None
    count=0

    for order in orders:
        a,b=order[0],order[1]
        if flag and a<=last:
            continue
        else:
            remove_path(islands,b-1,N)
            last = b - 1
            count += 1
            flag = True

    print(count)

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

from collections import deque

def main():
    n,m = map(int, input().split())
    qp = [tuple(map(int, input().split())) for _ in range(m)]

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

    qp = deque(qp)

    ans = 0
    pre = 0

    while qp:
        a,b = qp.popleft()
        if pre<a:
            ans += 1
            pre = b-1
    print(ans)

if __name__ == "__main__":
    main()

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

from collections import deque

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

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

qp = deque(qp)

ans = 0
pre = 0

while qp:
    a,b = qp.popleft()
    if pre<a:
        ans += 1
        pre = b-1
print(ans)

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

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

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

ans = 0
pre = 0

while qp:
    a,b = qp.pop(0)
    if pre<a:
        ans += 1
        pre = b-1
print(ans)

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

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

ans = 0
pre = 0

while qp:
    a,b = qp.pop(0)
    if pre<a:
        ans += 1
        pre = b-1
print(ans)

Solution (Python):
import numpy as np

temp=list(map(int, input().split()))
N=temp[0]
M=temp[1]

A=np.zeros((M,2)).astype(int)

for i in range(M):
  temp=list(map(int, input().split()))
  temp[0]-=1
  temp[1]-=1
  A[i]=temp
idx=A[:,1].argsort()
a=[0]*M
b=[0]*M
for i in range(M):
  a[i]=A[idx[i],0]
  b[i]=A[idx[i],1]
flag=False
x=-1
ans=0
for i in range(M):
  if a[i]>x:
    x=b[i]-1
    ans+=1
print(ans)

Solution (Python):
N , M  = map(int,input().split())
bridge = []
cut = []

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

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

for a,b in bridge:
    if len(cut)==0:
        cut.append(b-1)
    else:
        c = cut[-1]
        if a > c:
            cut.append(b-1)

print(len(cut))

Solution (Python):
from functools import reduce
import sys
input = sys.stdin.readline

N, M = map(int, input().split(" "))
disputes = list()
current = 0
for _ in range(M):
    a, b = map(int, input().split(" "))
    disputes.append((a, b))

disputes = sorted(disputes, key=lambda x: x[1])
count = 1
most_recently_removed = disputes[0][1] - 1
for i, dispute in enumerate(disputes[1:]):
    a, b = dispute
    if a <= most_recently_removed <= b-1:
        pass
    else:
        most_recently_removed = b-1
        count += 1

print(count)

Solution (Python):


import sys
from operator import itemgetter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = MAP()
edges = []
for i in range(M):
    a, b = MAP()
    edges.append((a, b))

edges.sort(key=itemgetter(1))

nxt = cnt = 0
for a, b in edges:
    
    if a > nxt:
        
        nxt = b - 0.5
        cnt += 1
print(cnt)

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log 
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,M=MI()
    AB=LLIN_(M)
    AB.sort(key=lambda x: x[1])
    before = -1
    ans=0
    for a,b in AB:
        if before<=a:
            before=b
            ans+=1
    print(ans)
if __name__ == '__main__':
    main()

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


def solve():
    
    bridges = sorted(list(zip(a, b)), key=lambda tup: tup[1])

    ans, tmp = 0, 1

    for bi in range(0, len(bridges)):
        
        
        if tmp <= (bridges[bi])[0]:
            tmp = (bridges[bi])[1]
            ans += 1


    print(ans)

def main():
    solve()

if __name__ == "__main__":
    main()

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() 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)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



n, m = LI()
L = sorted(LIR(m), key=lambda x:x[1])
pre_end = 0
cnt = 0
for start, end in L:
    if start < pre_end:
        continue
    else:
        cnt += 1
        pre_end = end


print(cnt)

Solution (Python):



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

request_list = []

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

ans = 0
f = False

while True:
    ans += 1
    end_point = request_list[0][1]
    for i in range(len(request_list)):
        if request_list[0][0] < end_point:
            del request_list[0]
            if len(request_list) == 0:
                f = True
                break
        else:
            break
            
            
    
    if f:
        break
    
print(ans)

Solution (Python):
def solve(n, m, a, b):
    x = -1/2
    ans = 0
    for s, t in sorted(zip(a, b), key=lambda _:_[1]):
        if x < s:
            ans += 1
            x = t - 1/2
    return ans

n, m = map(int, input().split())
a = [0] * m
b = [0] * m
for i in range(m):
    a[i], b[i] = map(int, input().split())
print(solve(n, m, a, b))

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()
answer = 0
last = 0
for b, a in l:
    if a >= last:
        answer += 1
        last = b
print(answer)

Solution (Python):
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m = inpl()
ab = [inpl() for i in range(m)]

ab.sort(key=lambda x:x[1])
ab.sort()
res = 0
now = 0
l = 0
r = 0
for i in range(m):
    if ab[i][0] == now:
        continue
    if ab[i][0] >= r:
        res += 1
        r = ab[i][1]
    elif ab[i][1] < r:
        r = ab[i][1]
    l = ab[i][0]
    now = l
print(res)

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

l.sort(key=lambda x:x[1])
ans=0
x=0
for li in l:
    a,b=li
    if x<=a:
        x=b
        ans+=1

print(ans)

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

Solution (Python):
import sys
input = sys.stdin.readline
INF = float('INF')

n, m = map(int, input().split())
path = [INF]*(n+1)

for _ in range(m):
    a, b = map(int, input().split())
    path[a] = min(path[a], b)

left = 1
ans = 1
right = n
while left <= n:
    cut = path[left]
    if cut == INF:
        left += 1
        continue
    if right <= left:
        ans += 1
        right = n
    right = min(right, cut)
    left += 1

print(ans)

Solution (Python):
import sys
from collections import defaultdict
input = sys.stdin.readline


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

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

idx = 1
ans = 1
right = n
while idx <= n:
    candidate = path[idx]
    if not candidate:
        idx += 1
        continue
    if right <= idx:
        ans += 1
        right = n
    cut = min(candidate)
    right = min(right, cut)
    idx += 1

print(ans)

Solution (Python):












import heapq





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





ab = []
for _ in range(M):
    a, b = map(int, input().split())
    heapq.heappush(ab, (a, b))














R = -1
count = 0
for i in range(M):
    (abl, abr) = heapq.heappop(ab)
    if R <= abl:
        
        count += 1
        R = abr
    elif abr < R:
        
        R = abr





print(count)

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

last_removed = conflicts[0][1]
bridge_removed = 1

for conflict in conflicts[1:]:
    if conflict[0] < last_removed and conflict[1] >= last_removed:
        continue
    else:
        last_removed = conflict[1]
        bridge_removed += 1

print(bridge_removed)

Solution (Python):
import numpy as np
N, M=map(int, input().split())
ab=np.array([list(map(int, input().split())) for i in range(M)])
ab-=1
ab=ab[np.argsort(ab[:, 1]), :]

counter=1
x=ab[0, 1]
for i in range(1, M):
  if ab[i, 0]<x:
    pass
  else:
    counter+=1
    x=ab[i, 1]
    
print(counter)

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

wars = [tuple(map(int, input().split())) for _ in range(M)]
wars.sort()

ans = 0
right = -1

for a, b in wars:
    if a >= right:
        ans += 1
        right = b
    else:
        right = min(right, b)

print(ans)

Solution (Python):
N,M = map(int, input().split())
r_table = [-1]*N
for _ in range(M):
    l_n, r_n = map(int, input().split())
    r_table[r_n-1] = max(l_n-1, r_table[r_n-1])

ret = 0
left = -1
for i in range(N):
    if left < r_table[i]:
        ret += 1
        left = i-1

print(ret)

Solution (Python):
def solve():
    N, M = map(int, input().split())
    ab = [[0, 0] for _ in range(M)]
    for i in range(M):
        ab[i] = list(map(int, input().split()))
    ab.sort(key=lambda x: x[1])

    ans = 0
    p_except = 0
    for a, b in ab:
        if a <= p_except:
            continue
        p_except = b - 1
        ans += 1
    
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
def examD():
    N, M = LI()
    right = defaultdict(int)
    for _ in range(M):
        a, b = LI()
        right[b] = max(right[b],a)
    ans = 0; cur = 0
    for i in range(1,N+1):
        if right[i]>cur:
            ans +=1
            cur = i-1
    print(ans)

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

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

    sort_A = sorted(A)
    left = 0
    right = N
    cnt = 1
    for i in range(M):
        left = max(sort_A[i][0],left)
        right = min(sort_A[i][1], right)
        if left >= right:
            cnt += 1
            right = sort_A[i][1]

    print(cnt)


    



if __name__ == "__main__":
    main()

Solution (Python):
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(m)]
ab.sort(key=lambda x:x[1])
x=0
ans=0
for i in range(m):
    a,b=ab[i][0],ab[i][1]
    if a>x:
        x=b-1
        ans+=1
    else:
        continue
print(ans)

Solution (Python):
n,m=map(int,input().split())
AB=[list(map(int,input().split())) for _ in [0]*m]
AB.sort(key=lambda x:x[1])
l=-1
ans=0
for i in range(m):
    if AB[i][0]>l:
        ans+=1
        l=AB[i][1]-1

print(ans)

Solution (Python):
from operator import itemgetter
n, m = map(int, input().split())
ab = sorted([ list(map(int, input().split())) for _ in range(m)], key=itemgetter(1) )
x = 0
ans = 0
for a, b in ab:
  if a > x:
    ans += 1
    x = b-1
print(ans)

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

res = 0
i = 1
for m in range(M):
    if req[m][0] >= i:
        i = req[m][1]
        res += 1

print(res)

Solution (Python):



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

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

l,r = 1,N

ans = 1
for a,b in AB:

    if r <= a:
        ans += 1
        l,r = a,b
    else:
        l = max(l,a)
        r = min(r,b)

print(ans)

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

ans = 0
L,R = 0,n
for a,b in ab:
    if b <= L or a >= R:
        ans += 1
        L,R = a,b
        continue
    L = max(L,a)
    R = min(R,b)
    
print(ans+1)

Solution (Python):
from operator import itemgetter
n,m=map(int,input().split())
a=[]
b=[]
for i in range(m):
    a_,b_=map(int,input().split())
    a.append(a_)
    b.append(b_)
ab=sorted([(a[i],b[i]) for i in range(m)],  key=itemgetter(1))  
removed=-1
ans=0

for i,j in ab:
    if i>removed:
        ans+=1
        removed=j-1
print(ans)

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

p = 0
for i in a:
    
    if p >= i[0]:
        continue
    
    
    p = i[1]-1
    divided[p -2]=1
    
print(sum(divided))

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

p = 0
for i in a:
    
    if p >= i[0]:
        continue
    
    
    p = i[1]-1
    divided[p -2]=1
    
print(sum(divided))

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])
ans = 1
tmp = ab[0][1]
for i in range(1, M):
    if tmp <= ab[i][0]:
        ans += 1
        tmp = ab[i][1]
print(ans)

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])

ans = 1             
tmp = ab[0][1] - 0.1      
for i in range(1, M):
    if ab[i][0] < tmp < ab[i][1]:   
        pass
    else:                           
        ans += 1
        tmp = ab[i][1] - 0.1

print(ans)

Solution (Python):
import sys
from operator import itemgetter
sys.setrecursionlimit(10**6)
def MAP(): return [int(s) for s in input().split()]

if sys.platform =='darwin':
	sys.stdin=open('input.txt')
input = sys.stdin.readline

N, M = MAP()
W = [MAP() for _ in range(M)]
W.sort()

low = W[0][0]
high = W[0][1]
cnt = 1

for i in range(1,M):
	low = max(low, W[i][0])
	high = min(high, W[i][1])
	if low < high:
		continue
	else:
		cnt += 1
		low = W[i][0]
		high = W[i][1]

print(cnt)

Solution (Python):
def main():
    N, M = (int(i) for i in input().split())
    ab = [tuple(int(i) for i in input().split()) for _ in range(M)]
    ab.sort(key=lambda p: p[1])

    pre_b = 1
    ans = 0
    for a, b in ab:
        if pre_b <= a:
            ans += 1
            pre_b = b
    print(ans)


if __name__ == '__main__':
    main()

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

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

ans=0
removed=-1
for i in range(M):
  if A[i][0] > removed:
    ans+=1
    removed=A[i][1]-1
print(ans)

Solution (Python):
def main():

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

    ans = 0
    rel.sort()
    a, b = rel[0]
    ans = 1
    for i in range(1, M):
        c, d = rel[i]
        if c < b:
            a = c
            b = min(b, d)
        else:
            ans += 1
            a, b = c, d
    return ans

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