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())
bridge = [0] * M
for i in range(M):
    bridge[i] = [0] * 2
    bridge[i][0], bridge[i][1] = map(int, input().split())
ans = 1
bridge = sorted(bridge, reverse=True)

nowcut = bridge[0][0]
for k in range(1, M):
    if bridge[k][1] <= nowcut:
        
        nowcut = bridge[k][0]
        ans += 1
print(ans)

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

ab=sorted(ab,reverse=True)

ans=0
check=float('inf')
for a,b in ab:
    if b<=check:
        check=a
        ans+=1
print(ans)

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, key=lambda x: (x[0], x[1]))

e = 0
ans = 0
for i in range(M):
    a, b = q[i]
    if a >= e:
        ans += 1
        e = b
    elif b < e:
        e = b

print(ans)

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

lst.sort()
d = []
d.append(lst[0])
for i in range(1, M):
    if lst[i][0] != lst[i-1][0]:
        flag = 0
        for j in range(len(d)):
            if d[j][1] > lst[i][0]:
                d[j][0] = lst[i][0]
                if d[j][1] > lst[i][1]:
                    d[j][1] = lst[i][1]
                flag += 1
                break
        if flag == 0:
            d.append(lst[i])
print(len(d))

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

    cmap = [N for _ in range(N)]
    for a,b in [map(int,input().split()) for _ in range(M)]:
        cmap[min(a-1,b-1)] = min(max(a-1,b-1),cmap[min(a-1,b-1)])

    min_ptr = N 
    counter = 0
    for i,c in enumerate(cmap):
        if i == min_ptr:
            counter += 1
            min_ptr = N
        min_ptr = min(cmap[i],min_ptr)
    print(counter)
resolve()

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

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

ans = 1
s = -10**9
t = 10**9
for a, b in ab:
    if a >= t:
        ans += 1
        t = b
    else:
        t = min(t, b)

print(ans)

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

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

Solution (Python):
N, M = map(int, input().split())
ab = sorted([list(map(int, input().split())) for _ in range(M)], key=lambda x: x[1])
x = l = 0
for a, b in ab:
    if x < a:
        x = b - 1
        l += 1
print(l)

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[0])
cnt = 0
bmin = 10**6
for i in range(M):
    a,b = A[i][0],A[i][1]
    if a>=bmin:
        cnt += 1
        bmin = b
    else:
        bmin = min(bmin,b)
cnt += 1
print(cnt)

Solution (Python):
N, M = map(int, input().split())
vs = []
for i in range(M):
    a, b = map(int, input().split())
    vs.append((b, a))
vs.sort()
end = 0
ans = 0
for b, a in vs:
    if end<=a:
        ans += 1
        end = b
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])
c = 0
d = 0
for t in ab:
  if d < t[0]:
    c += 1
    d = t[1]-1
print(c)

Solution (Python):
(n,m), *d = [list(map(int, s.split())) for s in open(0)]

s = [n+1]*(n+1)
for x,y in d:
    if s[x] > y:
        s[x] = y

ans = 0
_min = n+1
for i, x in enumerate(s):
    if _min == i:
        _min = n+1
        ans += 1
    
    if _min > x:
        _min = x

print(ans)

Solution (Python):

import sys
from operator import itemgetter
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
span = [list(map(int, input().split())) for _ in range(m)]
span.sort(key=itemgetter(1))

setudan = span[0][1]
ans = 1
for i in span:
    if (i[0] >= setudan):
        setudan = i[1]
        ans += 1
print(ans)

Solution (Python):

def main():
    
    n, m = [int(i) for i in input().split()]
    abc = []
    for i in range(m):
        a, b  = [int(j) for j in input().split()]
        abc.append([a,b])
    abc.sort(key=lambda x:x[1])
    i = 1
    ans = 1
    now = abc[0]
    while i < m:
        if now[1] <= abc[i][0]:
            ans += 1
            now = abc[i]
        i += 1
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
def solve():
	n,_,*t=map(int,open(0).read().split());r=[n+1]*(n+1)
	for a,b in zip(*[iter(t)]*2):
		r[a]=min(r[a],b)
	a=0;cur=n+1
	for i in range(n+1):
		cur=min(cur, r[i])
		if i==cur:
			
			cur=r[i]
			a+=1
	print(a)
if __name__=="__main__":
	solve()

Solution (Python):
n,m,*t=map(int,open(0).read().split());r=[n+1]*(n+1)
for a,b in zip(*[iter(t)]*2):
	r[a]=min(r[a],b)
a=0;cur=n+1
for i in range(n+1):
	cur=min(cur, r[i])
	if i==cur:
		cur=r[i]
		a+=1
print(a)

Solution (Python):
n,m,*t=map(int,open(0).read().split())
c=d=0
for b,a in sorted([(b,a)for a,b in zip(*[iter(t)]*2)]):
	if a>d:c+=1;d=b-1
print(c)

Solution (Python):
def solve():
	n,m,*t=map(int,open(0).read().split())
	r=sorted([(b,a)for a,b in zip(*[iter(t)]*2)])
	c=bef=0
	for b,a in r:
		if a>bef:
			c+=1
			bef=b-1
	print(c)
if __name__=="__main__":solve()

Solution (Python):

n, m = map(int, input().split())
ab = [0]*m
for i in range(m):
    a, b = map(int, input().split())
    ab[i] = (b, a)
ab.sort()
count = 0
last_break = n
for abi in ab:
    if not ((count != 0) & (abi[1] <= last_break)):
        count += 1
        last_break = abi[0] - 1
print(count)

Solution (Python):
N, M = map(int, input().split())
ls = [-1]*N
ans = 0
for i in range(M):
  a, b = map(int, input().split())
  ls[b-1] = max(ls[b-1], a-1)

ps = -1
for i in range(N):
  if ls[i]==-1:
    continue
  if ls[i]>=ps:
    ans += 1
    ps = i
print(ans)

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

Solution (Python):
n,m = map(int,input().split())
War = [list(map(int,input().split())) for i in range(m)]
War = sorted(War, key=lambda x:x[1])
count = 0
bridge = 0
for war in War:
  if bridge <= war[0]:
    bridge = war[1]
    count += 1
  else:
    continue
print(count)

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.sort()
cnt = 1
r_min = float('inf')
for l,r in AB:
    if l>=r_min:
        cnt += 1
        r_min = r
    else:
        r_min = min(r_min,r)
print(cnt)

Solution (Python):
N, M = map(int, input().split())
ab_s = [list(map(int, input().split())) for _ in range(M)]
bridges = [0] * N
ab_s = sorted(ab_s, key=lambda x: x[1])
for ab in ab_s:
    if bridges[ab[1]-1] - bridges[ab[0]-1] == 0:
        for i in range(ab[1]-1, N):
            bridges[i] += 1
print(bridges[-1])

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    a, b, c = LI()
    ans = 10 ** 5
    ans = min(ans, abs(a - b) + abs(b - c))
    ans = min(ans, abs(a - c) + abs(b - c))
    ans = min(ans, abs(a - c) + abs(a - b))
    print(ans)
    return


def B():
    s, t = S(), S()
    f = 0
    for i in range(len(s)):
        f = f or s[i:] + s[:i] == t
    print(["No","Yes"][f])
    return


def C():
    return








def D():
    n, m = LI()
    d = defaultdict(int)
    for _ in range(m):
        a, b = LI_()
        if d[a] < n - b:
            d[a] = n - b
    mi = 0
    ans = 0
    for i in range(n - 1):
        if mi < d[i]:
            mi = d[i]
        if i == n - mi - 1:
            mi = 0
            ans += 1
    print(ans)
    return


if __name__ == '__main__':
    D()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    a, b, c = LI()
    ans = 10 ** 5
    ans = min(ans, abs(a - b) + abs(b - c))
    ans = min(ans, abs(a - c) + abs(b - c))
    ans = min(ans, abs(a - c) + abs(a - b))
    print(ans)
    return


def B():
    s, t = S(), S()
    f = 0
    for i in range(len(s)):
        f = f or s[i:] + s[:i] == t
    print(["No","Yes"][f])
    return


def C():
    return








def D():
    n, m = LI()
    d = defaultdict(int)
    for _ in range(m):
        a, b = LI_()
        d[a] = max(d[a], n-b)
    mi = 0
    ans = 0
    for i in range(n - 1):
        if mi < d[i]:
            mi = d[i]
        if i == n - mi - 1:
            mi = 0
            ans += 1
    print(ans)
    return


if __name__ == '__main__':
    D()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    a, b, c = LI()
    ans = 10 ** 5
    ans = min(ans, abs(a - b) + abs(b - c))
    ans = min(ans, abs(a - c) + abs(b - c))
    ans = min(ans, abs(a - c) + abs(a - b))
    print(ans)
    return


def B():
    s, t = S(), S()
    f = 0
    for i in range(len(s)):
        f = f or s[i:] + s[:i] == t
    print(["No","Yes"][f])
    return


def C():
    return








def D():
    n, m = LI()
    d = defaultdict(int)
    for _ in range(m):
        a, b = LI_()
        d[a] = max(d[a], n-b)
    mi = 0
    ans = 0
    for i in range(n-1):
        mi = max(mi, d[i])
        if i == n - mi - 1:
            mi = 0
            ans += 1
    print(ans)
    return


if __name__ == '__main__':
    D()

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')


def A():
    a, b, c = LI()
    ans = 10 ** 5
    ans = min(ans, abs(a - b) + abs(b - c))
    ans = min(ans, abs(a - c) + abs(b - c))
    ans = min(ans, abs(a - c) + abs(a - b))
    print(ans)
    return


def B():
    s, t = S(), S()
    f = 0
    for i in range(len(s)):
        f = f or s[i:] + s[:i] == t
    print(["No","Yes"][f])
    return


def C():
    return








def D():
    n, m = LI()
    ab = LIR(m)
    ab.sort(key=lambda x: x[1])
    before = 0
    ans = 0
    for a, b in ab:
        if a < before <= b:
            continue
        else:
            before = b
            ans += 1
    print(ans)
    return


if __name__ == '__main__':
    D()

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


def main():
    N, M = map(int, input().split())
    Q = []
    for _ in range(M):
        a, b = map(int, input().split())
        heapq.heappush(Q, [b, a])
    
    cnt = 0
    x = 0
    while len(Q)!=0:
        b, a = heapq.heappop(Q)
        if x<a:
            cnt += 1
            x = b-1

    print(cnt)


if __name__ == '__main__':
    main()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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()

Solution (Python):

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)

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

Solution (Python):
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]):
    
    if a <= breaked < b:
        
        continue

    breaked = b - 1
    ans += 1

print(ans)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):

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:  
            ans += 1
            cur = b
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

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

Solution (Python):

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

Solution (Python):
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)

Solution (Python):

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:]:
    
    if b0 > a:
        a0 = max(a, a0)
        b0 = min(b, b0)
    else:
        a0, b0 = a, b
        cnt += 1

print(cnt)

Solution (Python):
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:]:
    
    if b0 > a:
        a0 = max(a, a0)
        b0 = min(b, b0)
    else:
        a0, b0 = a, b
        cnt += 1

print(cnt)

Solution (Python):
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()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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))

Solution (Python):
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()

Solution (Python):
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()

Solution (Python):
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


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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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])

Solution (Python):
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)

Solution (Python):
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)

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

Solution (Python):
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)

Solution (Python):
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()

Solution (Python):
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))

Solution (Python):
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)

Solution (Python):

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)

Solution (Python):
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)

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

Solution (Python):
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)