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


from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance





def main():
    n, m = intin()
    ablist = intinl(m)

    ablist.sort()
    candidates = []

    for a, b in ablist:
        if not candidates:
            candidates.append((a, b - 1))
            continue
        ca, cb = candidates[-1]
        if a <= cb:
            candidates[-1] = (max(a, ca), min(b - 1, cb))
            continue
        candidates.append((a, b - 1))

    print(len(candidates))


if __name__ == '__main__':
    main()

Solution (Python):
n,m=map(int,input().split())
b_list=[]
INF=10**6
for i in range(n):
    b_list.append(INF)
for i in range(m):
    a,b=map(int,input().split())
    b_list[a-1]=min(b-1,b_list[a-1])
end=INF
count=0
for i in range(n):
    if b_list[i]==INF:
        pass
    else:
        if i>=end:
            count=count+1
            end=b_list[i]
        else:
            end=min(end,b_list[i])
print(count+1)

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

A.sort(key=lambda a:a[1])
last = -1
ans = 0
for a in A:
    if last < a[0]:
        last = a[1] - 1
        ans += 1
print(ans)

Solution (Python):
N,M = map(int,input().split())
L = []
for _ in range(M):
    L.append(list(map(int,input().split())))
L = sorted(L,key=lambda x:x[1])
now = -10
cnt = 0
for x in L:
    if now < x[0]:
        now = x[1] - 0.5
        cnt += 1
print(cnt)

Solution (Python):
N,M = map(int,input().split())
L = []
for _ in range(M):
    L.append(list(map(int,input().split())))
L = sorted(L,key=lambda x:x[1])
now = -10
cnt = 0
for x in L:
    if now <= x[0]:
        now = x[1]
        cnt += 1
print(cnt)

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

Solution (Python):

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

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

cuts = [bridge[0][1]]
for b in bridge[1:]:
    cut = cuts[-1]
    if b[0]< cut <= b[1]:
        continue
    cuts.append(b[1])


print(len(cuts))

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

Solution (Python):

N,M=map(int,raw_input().split())
P=[]
for i in range(M):
    a,b=map(int,raw_input().split())
    P.append((a,b))
P.sort()
ans=0
l=-1
r=-1
for a,b in P:
    if r<=a:
        ans+=1
        l=a
        r=b
        continue
    l=a
    r=min(b,r)
print(ans)

Solution (Python):
import sys

def main():
    num, younou = map(int, input().split())

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

    ans = 0
    now_value = 1
    for ele in data:
        if ele[0] >= now_value:
            now_value = ele[1]
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,m = li()
ab = []
for _ in range(m):
    ai, bi = li_()
    ab.append((ai, bi))

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

ans = 0
cur = -1
for ai, bi in ab:
    if ai >= cur:
        ans += 1
        cur = bi

print(ans)

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

ans = 0
x = 0
for i in range(m):
  if x < l[i][1]:
    ans += 1
    x = l[i][0] -1
print(ans)

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

divide_list = [war_list[0][1]]
for i in range(1,M):
    if  war_list[i][0] < divide_list[-1]:
        pass
    else:
        divide_list.append(war_list[i][1])
    
print(len(divide_list))

Solution (Python):



import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N, M = read_ints()

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

from operator import itemgetter

AB.sort(key=itemgetter(1))  



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

print(ans)

Solution (Python):



import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N, M = read_ints()

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

from operator import itemgetter

AB.sort(key=itemgetter(1))  



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

print(ans)

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

print(ans)

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

ans = 0
ab = sorted(ab, key=lambda x: x[1])
n = 0
for i in range(M):
    if ab[i][0] >= n:
        n = ab[i][1]
        ans += 1
print(ans)

Solution (Python):
n,m = [ int (it ) for it in input().split() ]
lip =[]
lia =[ [] for i in range(n)]
lib =[ [] for i in range(n)]
for i in range(m):
  a,b = [ int(it)-1 for it in input().split() ]
  lip.append((a,b))
  lia[a].append(b)
  lib[b].append(a)


anow = 0
bnow = 0
mi = 1000000
s = 0
for i in range(n):
  
  if (len(lia[i])>0):
    _mi = min(lia[i])
    mi = min(_mi,mi)
  if (i==mi):
    s+=1
    
    if (len(lia[i])>0):
      mi = min(lia[i])
    else:
      mi = 1000000
print (s)

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

lst = []
for i in range(M):
    a = list(map(int, input().split()))
    lst += [a[::-1]]

lst.sort()

count = 0
position = 0

for i in range(M):
    if position <= lst[i][1]:
        count += 1
        position = lst[i][0]
        
print(count)

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

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

temp = 0
ans = 0
for a,b in AB:
    if b != temp and a >= temp:
        ans += 1
        temp = b
print(ans)

Solution (Python):

n, m = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(m)]
ab.sort(key=lambda x:x[1])
ans = 0
endplace = 0
for ai, bi in ab:
    if endplace <= ai:
        endplace = bi
        ans += 1
print(ans)

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


ans = 0
endtime = 0
for ai,bi in ab:
    if endtime <= ai:
        endtime = bi
        ans += 1
print(ans)

Solution (Python):
N,M = list(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
m = 0
for a,b in ab:
    if a<m:
        continue
    ans += 1
    m = b
print(ans)

Solution (Python):

import sys


def solve(N: int, M: int, P: "List[List[int]]"):
    fallen = -1
    count = 0
    P.sort(key=lambda p: p[1] * N - p[0])
    for p in P:
        if fallen==p[1]-1:
            continue
        if p[0] <= fallen:
            continue
        fallen = p[1]-1
        count += 1
    print(count)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    P = [[int(), int()] for _ in range(M)]   
    for i in range(M):
        P[i] = [int(next(tokens)), int(next(tokens))]
    solve(N, M, P)

if __name__ == '__main__':
    main()

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

pairs = []

for _ in range(M):
  pairs.append([int(x) for x in input().split()])

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

right_most = 0 

cnt = 0
for a,b in pairs:
  if a < right_most:
    continue
  cnt += 1
  right_most = b

print(cnt)

Solution (Python):
N,M=map(int, input().split())
inlist = [tuple([int(st) for st in input().split()]) for i in range(M)]
inlist.sort()
res=0
minright=100000000000
for fr, to in inlist:
    if to < minright: minright = to
    if minright <= fr:
        res += 1
        minright = to
print(res+1)

Solution (Python):
N,M=map(int, input().split())
inlist = [tuple([int(st) for st in input().split()]) for i in range(M)]
inlist.sort()
res=0
minright=100000000000
for fr, to in inlist:
    if to < minright: minright = to
    if minright <= fr:
        res += 1
        minright = to
print(res+1)

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

res=0
minright=100000000000
for fr, to in inlist:
    if to < minright:
        minright = to
    if minright <= fr:
        res += 1
        minright = to
    

print(res+1)

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

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])
ans=1
x=ab[0][1]
for a,b in ab[1:]:
    if a+1>x:
        x=b
        ans+=1
print(ans)

Solution (Python):
N,M=map(int,input().split())
ab=[]
for i in range(M):
    a,b=map(int,input().split())
    a,b=a-1,b-2
    ab.append([a,b])
ab.sort(key=lambda x:x[1])
ans=1
x=ab[0][1]
for a,b in ab[1:]:
    if a<=x:
        continue
    x=b
    ans+=1
print(ans)

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

ab_sort = ab[np.argsort(ab[:,1])]
ans = 0
nb = -1
for a, b in ab_sort:
    if a >= nb:
        ans += 1
        nb = b
print(ans)

Solution (Python):
import functools

import os
import sys

sys.setrecursionlimit(10000)
INF = float('inf')


def debug(fn):
    if not os.getenv('LOCAL'):
        return fn

    @functools.wraps(fn)
    def wrapper(*args, **kwargs):
        ret = fn(*args, **kwargs)
        print('DEBUG: {}({}) -> '.format(
            fn.__name__,
            ', '.join(
                list(map(str, args)) +
                ['{}={}'.format(k, str(v)) for k, v in kwargs.items()]
            )
        ), end='')
        print(ret)
        return ret

    return wrapper


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

reqs = [INF for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    reqs[a] = min(reqs[a], b)

ans = 0

broken = INF

for i in reversed(range(len(reqs))):
    req = reqs[i]
    if req < broken:
        
        broken = i + 1
        ans += 1
print(ans)

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

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

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

ans = 1
x = demand[0][1] - 2
for i in range(1, m):
    if x < demand[i][0] - 1:
        ans += 1
        x = demand[i][1] - 2
print(ans)

Solution (Python):
from collections import defaultdict
n, m = map(int, input().split())
edge = defaultdict(list)
for i in range(m):
    a,b = map(int, input().split())
    edge[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 edge[i]:
        dp[j] = max(dp[j], dp[i]+1)

print(dp[n])

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

ans = 0
now = -1
for s, e in ab:
    if now <= s:
        ans += 1
        now = e
print(ans)

Solution (Python):
def main():
	N, M = map(int, input().split())
	LR = [0]*M
	for i in range(M):
		LR[i] = list(map(int, input().split()))

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

	l, r = LR[0][0], LR[0][1]
	ans = 1
	for i in range(1, M):
		if LR[i][0] < r:
			l = max(l, LR[i][0])
		else:
			ans += 1
			l = LR[i][0]
			r = LR[i][1]
	print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
from operator import itemgetter

N, M = map(int, raw_input().split())
request = []
for i in range(0, M):
	inpt = map(int, raw_input().split())
	request.append(inpt)
request.sort(key=itemgetter(1))
cnt = 0
tmp = -1
for i in range(0, len(request)):
	if tmp <= request[i][0]:
		cnt += 1
		tmp = request[i][1]
print cnt

Solution (Python):
from operator import itemgetter

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

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

ab.sort(key=itemgetter(1))

fall = -1
ans = 0

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

print(ans)

Solution (Python):
islands, requests = map(int, input().split(" "))
req = []
for r in range(requests):
    a, b = map(int, input().split(" "))
    req.append([a, b])
req = sorted(req, key = lambda x:x[1])
answer = 1
temp_end = req[0][1]
for r in req:
    if r[0] >= temp_end:
        temp_end = r[1]
        answer += 1
print(answer)

Solution (Python):
islands, requests = map(int, input().split(" "))
req = []
for r in range(requests):
    a, b = map(int, input().split(" "))
    req.append([a, b])
req = sorted(req, key = lambda x:x[1])
answer = 1
temp_end = req[0][1]
for r in req:
    if r[0] >= temp_end:
        temp_end = r[1]
        answer += 1
print(answer)

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

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

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

ans = 0
x = 0
for a in A:
    if x < a[0]:
        x = a[1] - 1
        ans += 1
print(ans)

Solution (Python):
import heapq
N, M = map(int, input().split())
data = []
for i in range(M):
    a, b = map(int, input().split())
    heapq.heappush(data, (b, a))

cut = 0
answer = 0
for i in range(M):
    b, a = heapq.heappop(data)
    if cut <= a:
        answer += 1
        cut = b

print(answer)

Solution (Python):

n,m = map(int,input().split())
ab = [[0,0] for _ in range(m)]
for i in range(m):
    ab[i][1],ab[i][0] = map(int,input().split())

ab.sort()

cnt = 0
before = 0
for i in range(m):
    if cnt >= 1 and ab[i][1] < before:
        pass
    else:
        before = ab[i][0]
        cnt += 1

print(cnt)

Solution (Python):
n,m=map(int,input().split())
w=[]
for i in range(m):
    a,b=map(int,input().split())
    w.append((a,b))
w.sort(reverse=True)
d=[]
for i in range(m):
    a,b=w.pop()
    if i==0:
        d.append([a,b])
    else:
        if d[-1][1]<=a:
            d.append([a,b])
        elif d[-1][1]>b:
            d[-1][1]=b
print(len(d))

Solution (Python):









from operator import itemgetter
N,M = (int(_) for _ in input().split())
mostNeightborOpponent = [(N+1,i+1) for i in range(N)]

for i in range(M):
    a,b = (int(_) for _ in input().split())
    if mostNeightborOpponent[a-1][0] > b:
        mostNeightborOpponent[a-1] = (b,a) 


island = 1
bridgeWillBreak = 0

sortedOpponent = sorted(mostNeightborOpponent,key = itemgetter(0))

for b,a in sortedOpponent:
    if a < island :
        continue
    island = b
    if island > N :
        break
    bridgeWillBreak += 1

print(bridgeWillBreak)

Solution (Python):
if __name__ == '__main__':
    islands_count, demands_count = list(map(int, input().split()))
    demands = []
    break_count = 0

    for i in range(demands_count):
        demand = list(map(int, input().split()))
        demands.append(demand)

    demands.sort(key=lambda x: x[1])
    west_edge = 0

    for demand in demands:
        if demand[0] >= west_edge:
            break_count += 1
            west_edge = demand[1]

    print(break_count)

Solution (Python):

import sys
import itertools
import collections
import functools
import math
import operator
from queue import Queue
INF = float("inf")


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):

    ab = [[x, y] for x, y in zip(a, b)]
    ab.sort(key=operator.itemgetter(1))
    

    cut = [0]                   
    for a, b in ab:
        if a <= cut[-1]:         
            continue
        cut.append(b-1)
    print(len(cut)-1)


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    a = [int()] * (M)  
    b = [int()] * (M)  
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)


if __name__ == '__main__':
    main()

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

ab = sorted(ab,key=lambda x : x[1])
end = 0
ans = 0
for y in ab:
    if y[0] >= end:
        ans += 1
        end = y[1]
print(ans)

Solution (Python):
inf = 10**10

N,M = map(int,input().split())
ab =[list(map(int,input().split())) for i in range(M)]
ab.sort(reverse=True)
ans = 0
tmp = inf
for i in range(M):
    if ab[i][1] > tmp:
        continue
    else:
        ans += 1
        tmp = ab[i][0]
print(ans)

Solution (Python):
N,M = (int(num) for num in input().split())
ab = []
for i in range(M):
    ab.append([int(num)-1 for num in input().split()])
    
ab.sort(key= lambda l:l[1])

tmppos = 0
cnt = 0
for dem in ab:
    a = dem[0]
    b = dem[1]
    if a >= tmppos:
        tmppos = b
        cnt += 1
        
print(cnt)

Solution (Python):
from collections import deque
def dfs(v,N,memo):
    ans =0
    if not False in memo.values():
        return 1
    for u in E[v]:
        if memo[u]!=True:
            memo[u] = True
            ans += dfs(u,N,memo)
            memo[u] = False
    return ans
N,M = list(map(int,input().split()))
memo = {i:False for i in range(1,N+1)}
E = {i: []for i in range(1,N+1)}
for i in range(M):
    u,v = list(map(int,input().split()))
    E[v].append(u)
a =0
b = 0
counter =0
for i in range(1,N+1):
    if E[i]:
        if a<max(E[i]):
          if b>max(E[i]):
            a = max(E[i])
            continue
          a = max(E[i])
          b = i
          counter +=1
print(counter)

Solution (Python):
def main():
    N, M = [int(n) for n in input().split()]
    paths = [[int(n) for n in input().split()] for _ in range(M)]
    paths.sort(key = lambda x: x[0])

    prev = (-1, -1)
    result = 0
    for l, r in paths:
        r = r - 1
        pl, pr = prev
        if pl <= l and r <= pr:
            prev = (l, r)
            continue
        elif pl <= l <= pr and pr < r:
            prev = (l, pr)
            continue
        elif pr < l :
            prev = (l, r)
            result += 1
            continue
        else:
            raise ValueError("aaa")
    print(result)
if __name__ == "__main__":
    main()

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

requests = sorted(requests, key=lambda x: x[1])
start = 0
end = 0
ans = 0
for request in requests:
    nextstart, nextend = request
    if end <= nextstart:
        ans += 1
        start = nextstart
        end = nextend
print(ans)

Solution (Python):
N,M = map(int,input().split())
L = []
des = [0]
ans = 0
for i in range(M):
  L.append(list(map(int,input().split())))
L = sorted(L,key = lambda x:x[1])
for i in range(M):
  if des[len(des)-1] < L[i][0]:
    ans += 1
    des.append(L[i][1]-1)
print(ans)

Solution (Python):
N,M = map(int,input().split())
L = []
des = [0]
ans = 0
for i in range(M):
  L.append(list(map(int,input().split())))
L = sorted(L,key = lambda x:x[1])
for i in range(M):
  if des[len(des)-1] < L[i][0]:
    ans += 1
    des.append(L[i][1]-1)
print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
import operator
n,m=map(int,input().split())
l_ab=[0]*m
for i in range(m):
    l_ab[i]=list(map(int,input().split()))

l_ab.sort(key=operator.itemgetter(1))

l_br_last=0
num_br=0
for i in range(m):
    
    
        
    if l_br_last<l_ab[i][0]:
        l_br_last=l_ab[i][1]-1
        num_br+=1
print(num_br)

Solution (Python):
from operator import itemgetter

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

req.sort(key=itemgetter(1))

max=0
ans=0

for i in range(M):
    if not req[i][0]<=max<req[i][1]:
        max=req[i][1]-1
        ans+=1
        
print(ans)

Solution (Python):
import numpy as np
N, M  = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(M)]
ab.sort(key=lambda student: student[1])
temp = [0,0]
count = 0
for x in ab:
    if  x[0] <= temp[0] and temp[1] <= x[1] :
        continue
    else:
        temp[0] = x[1]-1
        temp[1] = x[1]
        count += 1
print(count)

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

D = {}

for _ in range(M):
  a,b = map(int, input().split())
  if not b in D.keys():
    D[b] = a
  elif a > D[b]:
    D[b] = a

th = 0
count = 0
D = sorted(D.items(), key=lambda x: x[0])
for (e,s) in D:
  if ((th < s) or (e < th)):
    th = e - 1
    
    count += 1
print(count)

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

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

ans = 0
cut_pos = -1
for i in range(m):
    if cut_pos <= info[i][0]:
        ans += 1
        cut_pos = info[i][1]
print(ans)

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

N,M = (int(i) for i in input().split())
dic = {}
cnt = 0
pos = 0
for i in range(M):
  a,b = map(int,input().split())
  if b not in dic or dic[b] < a:
    dic[b] = a

for j in sorted(dic.keys()):
  if dic[j] >= pos:
    cnt += 1
    pos = j
print(cnt)

Solution (Python):
n,m = map(int, input().split())
l = [tuple(map(int, input().split())) for _ in range(m)]
l.sort(key=lambda x:x[1])
dec = 0
cur = 0
for i in l:
  if i[0] < cur <= i[1]:
    continue
  else:
    dec += 1
    cur = i[1]
print(dec)

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

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

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

print(cnt)

Solution (Python):

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

res = 0
ab.sort(key=itemgetter(1))

i = 0
while i<m:
    a,b = ab[i]
    for j in range(i+1,m):
        if ab[j][0]<b<=ab[j][1]:
            i += 1
        else:
            break
    i += 1
    res += 1

print(res)

Solution (Python):
N,M=map(int,input().split())
conflict=[tuple(map(int,input().split())) for i in range(M)]
conflict.sort(key=lambda x:x[0])
ans=0
Right=N
for i in range(M):
    if conflict[i][0]>=Right:
        Right=conflict[i][1]
        ans+=1
    else:
        Right=min(Right,conflict[i][1])
print(ans+1)

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

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

t = ab[0][1]
ans = 1 

for (a, b) in ab:
    if a >= t:
        ans += 1
        t = b

print(ans)

Solution (Python):
N,M=map(int,input().split())
B=[]
for i in range(M):
  a,b=map(int,input().split())
  B.append([a,b])
B.sort(key=lambda x:x[1])
ans=1
c=[B[0][1]]
for item in B:
  if c[-1]<=item[0]:
    c.append(item[1])
    ans+=1
print(ans)

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

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

ans = 0
disconnected = [0]
for a, b in ab:
  if disconnected[-1] > a:
    continue
  disconnected.append(b)
  ans += 1
  
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
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))
cnt = 0
bridge = 0

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

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

li = [[] for _ in range(N)]
for _ in range(M):
    a,b = [int(i) for i in input().split()]
    li[a-1  ].append(b-1)

a = N+1
ans = 0
for i in range(N):
    if i == a:
        ans += 1
        a = N+1
    if len(li[i]) != 0:
        b = min(li[i])
        if a > b:
            a = b
print(ans)

Solution (Python):
from operator import itemgetter
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
l=sorted(l,key=itemgetter(1))
bridge=0
ct=0
for i in range(m):
  if bridge<l[i][0] or l[i][1]<=bridge:
    bridge=l[i][1]-1
    ct+=1
print(ct)

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

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007
sys.setrecursionlimit(1000000)


def A():
    return


def B():
    return


def C():
    return


def D():
    n,m = LI()
    a = LIR(m)
    a.sort(key = lambda x:x[1])
    x = 0
    ans = 0
    for i in range(m):
        if a[i][0] >= x:
            x = a[i][1]
            ans += 1
    print(ans)

def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == "__main__":
    D()