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 = list(map(int, input().split()))
ab_list = []

for _ in range(m):
    a, b = list(map(int, input().split()))
    ab_list.append((a, b))







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

i = 0
count = 0

while i < len(ab_list):
    count += 1

    a, b = ab_list[i]
    diff_index = 1
    end_index = b

    debug_list = [(a, b)]

    if (i + diff_index) >= len(ab_list):
        break

    
    while ab_list[i + diff_index][0] < end_index:
        

        diff_index += 1

        if (i + diff_index) >= len(ab_list):
            break

        
        

    
    

    i = i + diff_index

print(count)

Solution (Python):
import sys
INPUT = lambda: sys.stdin.readline().rstrip()
MAP = lambda: map(int, INPUT().split())
sys.setrecursionlimit(10 ** 9)


def main():
    N, M = MAP()
    AB = sorted([list(MAP()) for _ in range(M)], key=(lambda x: x[1]))

    point = cnt = 0
    for (a, b) in AB:
        if a > point:
            point = b - 1
            cnt += 1

    print(cnt)


if __name__ == '__main__':
    main()

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

Solution (Python):
from operator import itemgetter

n,m = list(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:
        ans += 1
        removed = b-1
print(ans)

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

conflict = [0] * M

for m in range(M):
    a, b = map(int, input().split())
    conflict[m] = (a, b)

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

used = [False] * M
count = 0

for m in range(M):
    if not used[m]:
        head, tail = conflict[m]
        used[m] = True

        j = m + 1
        while j < M:
            h, t = conflict[j]
            if tail <= h:
                break
            else:
                tail = min(tail, t)
                used[j] = True
            j += 1
        count += 1

print(count)

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

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

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


count=1
done=[intervals[0]]

for interval in intervals:
	
    
	if not interval[0] < done[-1][1]:
		count += 1
		done.append(interval)	

print(count)

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

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

intervals = sorted(bridges, key=lambda x: (x[1], x[0]))


count=1
done=[intervals[0]]

for interval in intervals:
	
	if not interval[0] < done[-1][1]:
		count += 1
		done.append(interval)	

print(count)

Solution (Python):
from bisect import bisect_left

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

cutted = [-1]
for i in range(M):
    a, b = ab[i]
    if a <= cutted[-1]:
        continue
    cutted.append(b-1)
print(len(cutted)-1)

Solution (Python):
from bisect import bisect_left

N, M = map(int, input().split())
ab = [0]*M
for i in range(M):
    ab[i] = tuple(map(int, input().split()))
ab.sort()


used = [False]*M
count = 0
for i in range(M):
    if used[i]:
        continue
    head, tail = ab[i]
    used[i] = True
    j = i+1
    while j < M:
        h, t = ab[j]
        if tail <= h:
            break
        tail = min(tail, t)
        used[j] = True
        j += 1
    count += 1
print(count)

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

N, M = map(int, input().split())
L = [[int(v) - 1 for v in input().split()] for _ in range(M)]

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

ans = 0
k = 0
bx = L[0][0]
for i in range(M):
    x, y = L[i]
    if bx < y:
        k += 1
        if bx <= x:
            bx = x
        continue
    else:
        ans += 1
        if i == M - 1:
            k = 1

        bx = x

print(ans + (1 if k != 0 else 0))

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

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

removed_bridge = []
for ab in AB_sorted:
    if removed_bridge:
        if ab[0] < removed_bridge[-1] < ab[1]:
            continue
    removed_bridge.append(ab[1] - 0.5)

print(len(removed_bridge))

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

ans = 0
lmax = 0
rmin = 10**9
for x in ab:
    a = x[0]
    b = x[1]
    if rmin <= a:
        ans += 1
        lmax = 0
        rmin = 10 ** 9
    if lmax < a:
        lmax = a
    if b < rmin:
        rmin = b
print(ans+1)

Solution (Python):
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
ba = []
for i in ab:
    ba.append(i[::-1])
ba.sort()
cnt = 1
broken = ba[0][0] - 1
for i in ba[1::]:
    if i[1] > broken:
        broken = i[0] - 1
        cnt += 1
print(cnt)

Solution (Python):
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
ba = []
for i in ab:
    ba.append(i[::-1])
ba.sort()
cnt = 1
broken = ba[0][0] - 1
for i in ba[1::]:
    if i[1] > broken:
        broken = i[0] - 1
        cnt += 1
print(cnt)

Solution (Python):

import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline

import math
import heapq

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

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

num = 0
loc = 0
for i in range(M):
	if loc < areas[i][1]:
		num += 1
		loc = areas[i][0]

print(num)

Solution (Python):
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue

Mod = 1000000007




def main(): 
    N,M = map(int,input().split())
    AB = [list(map(int,input().split())) for i in range(M)]
    AB.sort(key = lambda x:x[1],reverse = True)
    l = AB[0][0]
    r = AB[0][1]
    ans = 1
    for i in range(1,M):
        if r <= AB[i][0] or l >= AB[i][1]:
            ans += 1
            l = AB[i][0]
            r = AB[i][1]
        else:
            l = max(AB[i][0],l)
            r = AB[i][1]

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





def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n < 2 is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))):
        if prime[i] == 1:
            for j in range(2*i,n):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n):
        if prime[i] == 1:
            res.append(i)
    return res

class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py

    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

Solution (Python):
import heapq

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

Bri = [[] for _ in range(N+1)]
for a, b in AB:
    Bri[a].append(b)

q = []
ans = 0
for j in range(1, N+1):
    if q:
        if q[0] == j:
            q = []
            ans += 1
    for p in Bri[j]:
        heapq.heappush(q, p)
print(ans)

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

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

split=[0,]


for item in ab:
  if (item[1]-split[-1]>0 and item[0]-split[-1]<=0)!=True:
    split.append(item[1]-1)
  
  
print(len(split)-1)

Solution (Python):
n, m = map(int, input().split())
ab = sorted(tuple(map(int, input().split())) for _ in range(m))
s = n + 1
ret = 0
for a, b in ab:
    if s <= a:
        ret += 1
        s = n + 1
    s = min(s, b)
if s != n + 1:
    ret += 1
print(ret)

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

N, M = map(int, input().split())
a, b = (
    zip(*(map(int, input().split()) for _ in range(M))) if M else
    ((), ())
)


ans, _ = reduce(
    lambda acc, q: (
        (acc[0] + 1, q[1]) if q[0] >= acc[1] else
        acc
    ),
    sorted(zip(a, b), key=itemgetter(1)),
    (0, 0)
)

print(ans)

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

war = [float('inf')]*N

for i in range(M):
    a,b = map(int,input().split())
    war[a-1] = min(war[a-1],b-1)

ans = 0
cat = float('inf')
for i in range(N):
    if i == cat:
        ans += 1
        cat = float('inf')
    cat = min(cat,war[i])
print(ans)

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

del_num = 0
for i in range(M):
  if ab[i][0] >= del_num:
    count += 1
    del_num = ab[i][1]
print(count)

Solution (Python):
sortsecond = lambda val: val[1]
N, M = map(int, input().split())
l=[]
for i in range(M):
    t=input().split()
    l.append((int(t[0]),int(t[1])))
l.sort(key=sortsecond)
ans = int(0)
count = int(0)
br = int(0)


for i in range(M):
    if br<l[i][0]+1:
        count +=1
        br = l[i][1]

ans = count
print(ans)

Solution (Python):
from operator import itemgetter

N, M = map(int,input().split())
demand = [list(map(int,input().split())) for _ in range(M)]
demand.sort(key=itemgetter(1))
x = 1
b = demand[0][1]

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

print(x)

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

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

ab.sort()

l = ab[0][0]
r = ab[0][1]
ans = 1

for i in range(1,m):
    if r<=ab[i][0]:
        ans += 1
        l = ab[i][0]
        r = ab[i][1]
    else:
        r = min(r, ab[i][1])

print(ans)

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

sort_ab = sorted(AB, key=lambda x: x[1])
cur_max = 0
cnt = 0
for el in sort_ab:
  if el[0] >= cur_max:
    cnt += 1
    cur_max = el[1]
print(cnt)

Solution (Python):
n, m = map(int, input().split())
a_list = []
for _ in range(m):
    a, b = map(int, input().split())
    a_list.append([a, b])
a_list.sort(key = lambda x: (x[1], x[0]))
temp = -1
ans = 0
for a, b in a_list:
    if (temp < a):
        temp = b - 1
        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 ab: ab[1])
removed = list()
for a, b in AB:
    if len(removed) == 0:
        removed.append(b - 1)
    elif a <= removed[-1] < b:
        continue
    else:
        removed.append(b - 1)
print(len(removed))

Solution (Python):

import copy
import random
import bisect 
import fractions 
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) 

def LI(): return list(map(int, sys.stdin.readline().split()))

N,M = LI()
ab = [[] for i in range(M)]
for i in range(M):
    a,b = LI()
    a -= 1
    b -= 1
    ab[i] = [a,b]


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

print(ans)

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

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

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

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

last_break = 0
ans = 0
for ab in ab_array:
    a, b = ab
    if last_break >= a:
        continue
    last_break = b - 1
    ans += 1

print(ans)

Solution (Python):
N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for m in range(M)]
AB = sorted(AB, key=lambda x: x[1])
ans = 0
prev = 0
for a, b in AB:
    if ans > 0 and a <= prev:
        pass
    else:
        ans += 1
        prev = b-1
print(ans)

Solution (Python):


import operator

"""
区画スケジューリング
まず、(ai, bi) の組を bi について昇順にソートし、以下を行う
• 既にその要望を満たしている場合、何もしない
• 要望を満たしていない場合、bi − 1 番目と bi 番目を接続する橋を取り除く

TLE に注意
bridges[-1] == max(bridges), ms[i][0] == min(ms) という事実を使う
ジェネレータ表記は必ずしも使わなくてもよい
"""

n, m = map(int, input().split())
bridges = [0]
ms1 = (tuple(map(int, input().split())) for i in range(m))
ms2 = sorted(ms1, key=operator.itemgetter(1))

for i in range(m):
    if ms2[i][0] <= bridges[-1]:
        pass
    else:
        bridges.append(ms2[i][1] - 1)

if __name__ == "__main__":
    print(len(bridges)-1)

Solution (Python):


import operator

"""
区画スケジューリング
まず、(ai, bi) の組を bi について昇順にソートします。ソートした順に、以下を行う。
• 既にその要望を満たしている場合、何もしない。
• 要望を満たしていない場合、bi − 1 番目の島と bi 番目の島を接続する橋を取り除く。
TLE に注意
"""

n, m = map(int, input().split())
bridges = [0]
ms = sorted((tuple(map(int, input().split())) for i in range(m)), key=operator.itemgetter(1))

for i in range(m):
    if ms[i][0] <= bridges[-1]:
        pass
    else:
        bridges.append(ms[i][1] - 1)

if __name__ == "__main__":
    print(len(bridges)-1)

Solution (Python):



def ri():
    return int(input())

def rl():
    return list(input().split())

def rli():
    return list(map(int, input().split()))

def main():
    n, m = rli()
    edges = []
    for _ in range(m):
        a, b = rli()
        edges.append((a, b))
    edges.sort(key=lambda x:x[1])
    ans = 0
    left = 0
    for e in edges:
        if e[0] <= left:
            continue
        ans += 1
        left = e[1]-1
    
    
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np


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

demands = [0]*M
for i in range(0, M):
    demands[i] = list(map(int, input().split()))

demands = np.array(demands)

arr = np.argsort(demands, axis=0) 
lvl = arr[:,1] 

start = 1
end = 1
cnt = 0
for i in lvl:    
    
    if demands[i][0] < end:
        continue
    
    
    end = demands[i][1]
    cnt += 1
        
print(cnt)

Solution (Python):
n,m=map(int, input().split()) 
s=[list(map(int, input().split())) for i in range(m)]
s.sort(key = lambda x:x[1])
x=[0]
count=0
for i in range(m):
    if s[i][0]<=x[-1]:
        pass
    else:
        x.append(s[i][1]-1)
        count+=1
print(count)

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

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

i = 0
count = 1
b1=ab[0][1]
a1=ab[0][0]
while i < m:
    if ab[i][0]>=b1:
        count += 1
        b1 = ab[i][1]
    else:
        b1 = min(b1,ab[i][1])
    i += 1
print(count)

Solution (Python):



import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7

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

Solution (Python):
from operator import itemgetter
N,M = map(int,input().split())
graph = [[int(i) for i in input().split()] for _ in range(M)]
graph.sort(key=itemgetter(1))
ans = 0
cut = 0

for i in range(M):
    if cut < graph[i][0]:
        cut = graph[i][1] -1
        ans += 1

print(ans)

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

AB.sort(key=lambda x: x[0])
x = n
l = 0
for a, b in reversed(AB):
  if b > x :
    continue
  else:
    x = a
    l += 1
    
print(l)

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

x.sort(key=lambda x: x[1])
res = 0
right = 0
for i in range(M):
    if x[i][0] >= right:
        right = x[i][1]
        res += 1

print(res)

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])
ans = 0
lastremoved = 0

for i, j in enumerate(ab):
    if i == 0:
        ans += 1
        temp = j[1] - 1
    else:
        if j[0] <= temp:
            continue
        else:
            ans += 1
            temp = j[1] - 1
            
print(ans)

Solution (Python):
n,m=map(int,input().split())
sp=[None for i in range(m)]
for i in range(m):
  l,r=map(int,input().split())
  sp[i]=[l,r]
sp.sort(key=lambda x:x[1])
sp.sort(key=lambda x:x[0])
s=[sp[0]]
for i in sp:
  if i[0]!=s[-1][0]:
    s.append(i)
ans=1
c=s[0]
if len(s)==1:print(1)
else:
  for i in range(1,len(s)):
    if c[1]<=s[i][0]:
      ans+=1
      c=s[i]
    if c[1]>s[i][1]:
      c=s[i]
    else:
      c[0]=s[i][0]
  print(ans)

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

war = []

for _ in range(M) :
    A, B = map(int, input().split())
    war.append((A,B))

war.sort(key=lambda A : A[0])

ans = 1
left, right = war[0]

for i in range(1, M) :
    A, B = war[i]
    if right <= A :
        ans += 1
        left = A
        right = B
        continue
    left = A
    right = min(right, B)

print(ans)

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

def minpair(A,B):
    if A[1] <= B[0]:
        C = []
    elif B[0] < A[1] <= B[1]:
        C = [B[0],A[1]]
    else:
        C = B
    return C

Bridge.sort(key=lambda x: x[0])
c = 0
ans = 0
while c <= M-2:
    Temp = minpair(Bridge[c],Bridge[c+1])
    if Temp == []:
        ans += 1
    else:
        Bridge[c+1] = Temp
    c += 1
print(ans+1)

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

def minpair(A,B):
    if A[1] <= B[0]:
        C = []
    elif B[0] < A[1] <= B[1]:
        C = [B[0],A[1]]
    else:
        C = B
    return C

Bridge.sort(key=lambda x: x[0])
c = 0
ans = 0
while c <= M-2:
    Temp = minpair(Bridge[c],Bridge[c+1])
    if Temp == []:
        ans += 1
    else:
        Bridge[c+1] = Temp
    c += 1
print(ans+1)

Solution (Python):
from collections import deque


N , M = map(int,input().split())
ikusa_L = []
for i in range(M):
    ikusa_L.append(list(map(int,input().split())))
ikusa_L.sort(key=lambda x: x[1])
q = deque(ikusa_L)
q_1 = deque(q)
count = 0
while len(q_1) > 0:
    q_1 = deque([])
    a = q.popleft()
    cut = a[1]
    
    count += 1
    pop_count = 0
    for i in q:
        if not(i[0] < cut):
            q_1.append(i)
    q = deque(q_1)
    

print(count)

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

def main():
    N, M = map(int, input().split())
    ab = sorted([list(map(int, input().split())) for i in range(M)], key = lambda x:x[1])
    count = 0
    break_ = -1
    for a, b in ab:
        a -= 1; b -= 1;
        if a > break_:
            count += 1
            break_ = b-1
    print(count)

if __name__ == "__main__":
    main()

Solution (Python):
import numpy as np

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

dtype = [('start', int), ('end', int)]
req = np.empty([M], dtype=dtype)

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

req.sort(order=['end'])

cutList = []

def isConnected(start, end):
    for i in cutList:
        if start <= i and i < end:
            return False
    return True

ans = 0

for i in range(M):
    if isConnected(req[i][0], req[i][1]):
        cutList.append(req[i][1]-1)
        ans += 1

print(ans)

Solution (Python):
from operator import itemgetter
N, M = map(int, input().split())
table = []
for i in range(M):
  a,b = map(int, input().split())
  table.append((a,b))
t = 0
ans = 0
table.sort(key=itemgetter(1))
for a,b in table:
  if t < a:
    ans += 1
    t = b-1
print(ans)

Solution (Python):
import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict






INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)








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

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

cnt = 0
i = 0
while i < len(AB):
    cut = AB[i][0]
    while i < len(AB) and AB[i][1] >= cut:
        i += 1
    cnt += 1

print(cnt)

Solution (Python):
from operator import itemgetter

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

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

es.sort(key=itemgetter(1))

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

Solution (Python):
import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

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

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

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

heap = []

ans = 0
for a, b in AB:
    if heap and a >= heap[0]:
        heap = []
        ans += 1
    heapq.heappush(heap, b)
if heap:
    ans += 1
print(ans)

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

ba = []
for i in range(M):
    ba.append([ab[i][1], ab[i][0]])
ba.sort() 

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

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

BA.sort()

cnt = 0
end = 0
for ba in BA:
    b, a = ba
    if a > end:
        cnt += 1
        end = b - 1

print(cnt)

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

import numpy as np

d2=np.array(d)


d3=d2[np.lexsort(d2.T)][::-1]


cnt=1
i=0

while i<n:
	j=i+1
	st=d3[i][0]
	while j<n:
		if d3[j][1]<=st:
			
			
			
			
			cnt+=1
			i=j-1
			j=n-1
		if st<d3[j][0]:
			st=d3[j][0]
		j+=1
	i+=1
print(cnt)

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

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

removed = []

for a,b in AB:
    if len(removed) == 0:
        removed.append(b - 1)
    elif max(removed) < a:
        removed.append(b - 1)

print(len(removed))

Solution (Python):


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

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

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

pre=0
cnt=0
for i in range(m):
    if pre<=ab[i][0]:
        pre=ab[i][1]
        cnt+=1
    else:
        pre=min(pre,ab[i][1])
print(cnt)

Solution (Python):


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

for i in range(m):
    ab.append(tuple((map(int,input().split()))))

sep=[0]*n

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

ans=0
pre=0

for i in range(m):
    if pre<=ab[i][0]:
        ans+=1
        pre=ab[i][1]
    else:
        pre=min(pre,ab[i][1])    
print(ans)

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

ab = []

for _ in range(M):
    a,b = map(int,input().split())
    ab.append((a,b))
    
ab.sort()

ans = 0
b_prev = 0

for i in range(M):
    if b_prev <= ab[i][0]:
        ans += 1
        b_prev = ab[i][1]
    else:
        b_prev = min(b_prev, ab[i][1])
    
print(ans)

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

check = [B[0][1]-1]

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

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

Solution (Python):
from sys import stdin

input=[int(x) for x in stdin.readline().rstrip().split()]
N=input[0]
M=input[1]

order_list=[]
for m in range(M):
    order_list.append([int(x) for x in stdin.readline().rstrip().split()])

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

a=0
b=0
output=0
for i in order_list:
    a=i[0]
    if a>=b:
        output+=1
        b=i[1]
print(output)

Solution (Python):
n,m=map(int,input().split())
b=[]
for i in range(m):
    b.append(list(map(int,input().split())))
b.sort(key=lambda x:x[1])
time=0
count=0
for k in range(len(b)):
    if b[k][0]>=time:
                time=b[k][1]
                count+=1
print(count)

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

e = []
for _ in range(M):
    e.append(tuple(map(int, input().split())))

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


ans = 1
s, g = e[0]

for i in range(1, M):

    
    if e[i][0] < g:
        continue
    else:
        g = e[i][1]
        ans += 1

print(ans)

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] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N, M = LI()
ab = LIR(M)

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

before = 0
ans = 0
for ai, bi in ab:
    if (ai <= before):
        continue
    else:
        ans += 1
        before = bi-1
print(ans)

"""
left = [0]*N
right = [0]*N

for ai, bi in ab:
    left[ai-1] = 1
    right[bi-1] = 1

l = N-1
r = N-1
ans = 0

flag = False
while (l>=0):
    if (left[l]):
        while (r>l):
            if (right[r]):
                flag = True
            r -= 1
        if (flag):
            ans += 1
            flag = False
    l -= 1

print(ans)
"""

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


l = 0
for i in range(m):
    if e[i][0] < l:
        continue
    else:
        l = e[i][1]
        ret += 1
    
print(ret)

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

Schedule = sorted(Schedule, key=lambda x: x[1])
cnt = 0
before_end = 0
for task in Schedule:
    start = task[0]
    end = task[1]
    if start < before_end:
        continue
    cnt += 1
    before_end = end
print(cnt)

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

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

ans = 0
now = -1

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

for i in range(m):
    if li[i][0] <= now and li[i][1] > now:
        pass
    else:
        ans += 1
        now = li[i][1] - 1

print(ans)

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

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

ans = 0
now = -1

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

for i in range(m):
    if li[i][0] > now or li[i][1] <= now:
        ans += 1
        now = li[i][1] - 1

print(ans)

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

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

ans = 0
now = -1

li.sort(key = itemgetter(1))

for i in range(m):
    if li[i][0] <= now and li[i][1] > now:
        pass
    else:
        ans += 1
        now = li[i][1] - 1

print(ans)

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

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

ans = 0
now = -1

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

for i in range(m):
    if li[i][0] <= now and li[i][1] > now:
        pass
    else:
        ans += 1
        now = li[i][1] - 1

print(ans)

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

ans = 0
now = -1

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

for i in range(m):
    if li[i][0] <= now and li[i][1] > now:
        pass
    else:
        ans += 1
        now = li[i][1] - 1

print(ans)

Solution (Python):
def main():
    N, M = map(int, input().split())
    A = [tuple(map(int, input().split())) for _ in range(M)]
    S = sorted(A, key=lambda x: x[1])
    count = 0
    last = 0
    for s in S:
        if last < s[0]:
            count += 1
            last = s[1] - 1
    print(count)


if __name__ == "__main__":
    main()

Solution (Python):
n, m = map(int, input().split())
a_b = []
a_b = [[int(x) for x in input().split()] for _ in range(m)]
a_b = sorted(a_b, key=lambda x: x[1])
ans = 0
last = 0
for i in a_b:
    if i[0] < last:
        continue
    else:
        last = i[1]
        ans += 1
print(ans)