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):
break_offs = set()
N, M = map(int, input().split())
for i in range(M):
    a, b = map(int, input().split())
    if a > b:
        a, b = b, a
    break_offs.add((a, b))

covered = []
break_offs = sorted(list(break_offs), key=lambda x:x[1])
for a, b in break_offs:
    found = False
    for area in covered:
        if not (area[0] >= b or area[1] <= a):
            covered.remove(area)
            covered.append((max(area[0], a), min(area[1], b)))
            found = True
            break

    if not found:
        covered.append((a, b))


answer = len(covered)
print(answer)

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

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


a=sorted(a, key=lambda x: x[1])
hasi = -1
sum = 0

for i in range(0,M):
    
    if (hasi >= a[i][0])and (hasi < a[i][1]):
        continue
    else:
        hasi = a[i][1]-1
        sum = sum+1

print(sum)

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

Solution (Python):
n, m = map(int, input(). split())
lists = [[int(i) for i in input().split()] for j in range(m)]
lists.sort()
a = b = count = 0
for x in lists:
  if a < x[0]:
    if b <= x[0]:
      count += 1
      a = x[0]
      b = x[1]
    else:
      b = min(b, x[1])
print(count)

Solution (Python):
N,M = map(int,input().split())
li = [[int(i) for i in input().split()] for j in range(M)]
li.sort()
a = b = C = 0
for d in li:
    if a < d[0]:
      if b <= d[0]:
        C += 1
        a = d[0]
        b = d[1]
      else:
        b = min(b,d[1])
print(C)

Solution (Python):


from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def solve(N, M, a, b):
    pass


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

    ans = 0
    mini = INF
    for a, b in l:
        if mini <= a:
            ans += 1
            mini = INF
        mini = min(mini, b)

    print(ans + 1)

if __name__ == '__main__':
    main()

Solution (Python):
a,b = list(map(int,input().split()))

input_lines = [list(map(int,input().split())) for i in range(b)]
input_lines = sorted(input_lines,key=lambda x: x[1]) 

c=[0]
for i in input_lines:
    
    
    
    if max(c)<=i[0]:
        c.append(i[1])
        
print(len(c)-1)

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

Solution (Python):
a=list(map(int,input().split()))
b=[]
c=0
r=0
for i in range(a[1]):
  b.append(list(map(int,input().split())))
b=sorted(b,key=lambda b:b[1])

for i in range(a[1]):
  if b[i][0]<=r:
    continue
  else:
    c=c+1
    r=b[i][1]-1

print(c)

Solution (Python):
n, m = map(int, input().split())
a = []
for _ in range(m):
    u, v = map(int, input().split())
    a.append((u, v))
a.sort()
i, c = 0, 0
for u, v in a:
    if u >= i:
        c += 1
        i = v
    else:
        i = min(i, v)
print(c)

Solution (Python):


from operator import itemgetter

str = input()
nm=[int(x) for x in str.split(' ')]
n = nm[0]
m = nm[1]
ab_2d = []
for i in range( 0, m ):
    str_ab = input()
    ab = [int(x) for x in str_ab.split(' ')]
    ab_2d.append(ab)

sorted_ab_2d = sorted(ab_2d, key = itemgetter(1))

bridge = 0
count = 0

for i in range( 0, m ):
    if(sorted_ab_2d[i][0] > bridge):
        count = count + 1
        bridge = sorted_ab_2d[i][1] - 1
    

print(count)

Solution (Python):
ab=[]

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

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

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

res=0
for z in range(len(ab)):
    x=ab[0][1]
    for j in range(len(ab)):
        if x > ab[0][0]:
            del ab[0]
        else:
            res+=1
            break
    if len(ab)==0:
        res+=1
        break
    
print(res)

Solution (Python):
def main():
    n = [int(i) for i in input().split()]
    bridge = set()
    counter = 0
    reqs = [[int(j) for j in input().split()] for i in range(n[1])]
    reqs.sort(key=lambda x:(x[0],x[1]))
    
    preset = 0
    for i in range(1, n[0]+1):
        if i in bridge:
            bridge.clear()
            counter += 1
        for j in range(preset, len(reqs)):
            if reqs[j][0] == i:
                bridge.add(reqs[j][1])
            else:
                preset = j
                break
    
    print(counter)

main()

Solution (Python):
N, M = map(int, input().split())
disputes = [list(map(int, input().split())) for x in range(M)]
disputes.sort(key=lambda x: x[1])
disconnects = []
for dispute in disputes:
    for disconnect in disconnects:
        if dispute[0] <= disconnect and disconnect < dispute[1]:
            break
    else:
        disconnects.append(dispute[1] - 1)
print(len(disconnects))

Solution (Python):
n,m = list(map(int,input().split()))
wars = []
last_bs = 0
cnt = 0

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

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

for war in wars:
    if war[0] > last_bs:
        last_bs = war[1]-1
        cnt += 1

print(cnt)

Solution (Python):
def main():
    """
    2 <= N <= 10^5
    1 <= M <= 10^5
    1 <= ai < bi <= N
    (ai, bi) != (aj, bj)
    """
    N, M = map(int, input().split())
    A, B = zip(*[
        map(int, input().split())
        for _ in range(M)
    ])
    
    ans = editorial(N, M, A, B)
    

    print(ans)


def editorial(N, M, A, B):
    ans1 = AC_b_sort(N, M, A, B)
    ans2 = AC_a_sort(N, M, A, B)
    assert ans1 == ans2
    return ans1


def AC_b_sort(N, M, A, B):
    ab = sorted(zip(A, B), key=lambda x: (x[1], x[0]))
    ans = 0
    bef_b = 0
    for a, b in ab:
        
        if bef_b <= a:
            ans += 1
            bef_b = b

    return ans


def AC_a_sort(N, M, A, B):
    ab = sorted(zip(A, B), key=lambda x: (x[0], -x[1]))
    ans = 0
    bef_b = float("inf")
    for a, b in ab:
        
        if bef_b <= a:
            ans += 1
            bef_b = b
        else:
            bef_b = min(bef_b, b)

    return ans + 1


def TLE(N, M, A, B):
    """
    """
    ans = N - 1
    for a in A:
        for b in B:
            pass

    return ans


def WA(N, M, A, B):
    """
    ai, bi の分断:

    入力例1
        1, 4 の分断
            橋1-3 のどれかを除去
        2, 5 の分断
            橋2-4 のどれかを除去
        共通部: 2-3
        要望ごとの共通部を探す必要がある
            M^2: TLE

    A_min: 西
    A_max: 東
    B_min: 西
    B_max: 東

    入力例2
    9 5
    1------8
     2----7
      3-5
       4-6
          7-9

    a_min,b_max の順に並べる
    要望の東側が以前の西側未満ならOK
    要望の西側が以前の東側を超えないならOK ?
    """
    ab = sorted(zip(A, B), key=lambda x: (x[0], -x[1]))
    ans = 0
    bef_a, bef_b = -1, float("inf")
    for i, (a, b) in enumerate(ab):
        print(" " * (a-1), a, "-" * (b - a - 1), b, sep="")
        if bef_a <= a < b <= bef_b:
            pass
        elif bef_b <= a:
            ans += 1
        elif bef_a < a < bef_b < b:
            pass

        bef_a, bef_b = a, b

    return ans + 1


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    string = input().split()
    island = int(string[0])
    dispute_num = int(string[1])
    disputes = []
    for i in range(dispute_num):
        string = input().split()
        disputes.append([int(string[0]), int(string[1])])
    disputes.sort()

    cut_count = 1
    left_cut = disputes[0][0]
    right_cut = disputes[0][1]
    for i in range(1, dispute_num):
        left = disputes[i][0]
        right = disputes[i][1]
        if( right_cut > left):
            left_cut = left
            if(right_cut > right):
                right_cut = right
        else:
            cut_count += 1
            right_cut = right
            left_cut = left

    print(cut_count)


if __name__ == "__main__":
    main()

Solution (Python):
from operator import itemgetter
def main():
  n, m = map(int, input().split())
  bridge = 0
  ab = []
  for _ in range(m):
    a, b = map(int, input().split())
    ab.append((a,b))
  ab = sorted(ab, key=itemgetter(1))
  count = 0
  for a, b in ab:
    if not a <= bridge <= b:
      count += 1
      bridge = b-1
  print(count)

main()

Solution (Python):
from operator import itemgetter
n, m = map(int, input().split())
bridge = 0
ab = []
for _ in range(m):
  a, b = map(int, input().split())
  ab.append((a,b))
ab = sorted(ab, key=itemgetter(1))
count = 0
for a, b in ab:
  if not a <= bridge <= b:
    count += 1
    bridge = b-1
print(count)

Solution (Python):

import sys
import math
import numpy as np
import itertools



n,m = (int(i) for i in input().split())  

l = [[int(i) for i in input().split()] for i in range(m)] 

l = sorted(l, key=lambda x:x[0])
answer=1
a=l[0][0]
b=l[0][1]
for i in range(1,m):
    if l[i][0] >= b:
        answer += 1
        a=l[i][0]
        b=l[i][1]
    else:
        a=l[i][0]
        b=min(b,l[i][1])


print(answer)

Solution (Python):
from operator import itemgetter
n, m = map(int, input().split())
bridge = 0
ab = []
for _ in range(m):
  a, b = map(int, input().split())
  ab.append((a,b))
ab = sorted(ab, key=itemgetter(1))
count = 0
for a, b in ab:
  if not a <= bridge <= b:
    count += 1
    bridge = b-1
print(count)

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


count = 0
while(0 < len(ab)):
    count += 1
    cutb = ab[0][1]
    
    remove_index = 0
    for i in range(len(ab)):
        a, b = ab[i]
        if a <= cutb - 1 and cutb <= b:
            remove_index = i
        else:
            break

    ab = ab[remove_index+1:]

print(count)

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

arr = []

for i in range(m):
	arr.append(map(int,raw_input().split()))

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


ans = 0
t = 0


for i in range(m):
	if arr[i][0] >= t:
		ans += 1
		t = arr[i][1]

print ans

Solution (Python):
def main():
    n = [int(i) for i in input().split()]
    bridge = set()
    counter = 0
    reqs = [[int(j) for j in input().split()] for i in range(n[1])]
    reqs.sort(key=lambda x:(x[0],x[1]))
    
    preset = 0
    for i in range(1, n[0]+1):
        if i in bridge:
            bridge.clear()
            counter += 1
        for j in range(preset, len(reqs)):
            if reqs[j][0] == i:
                bridge.add(reqs[j][1])
            else:
                preset = j
                break
    
    print(counter)

main()

Solution (Python):
def main():
    n = [int(i) for i in input().split()]
    bridge = set()
    counter = 0
    reqs = [[int(j) for j in input().split()] for i in range(n[1])]
    reqs.sort(key=lambda x:(x[0],x[1]))
    
    preset = 0
    for i in range(1, n[0]+1):
        if i in bridge:
            bridge.clear()
            counter += 1
        for j in range(preset, len(reqs)):
            if reqs[j][0] == i:
                bridge.add(reqs[j][1])
            else:
                preset = j
                break
    
    print(counter)

main()

Solution (Python):
def main():
    n = [int(i) for i in input().split()]
    bridge = set()
    counter = 0
    reqs = [[int(j) for j in input().split()] for i in range(n[1])]
    reqs.sort(key=lambda x:(x[0],x[1]))
    prefix = 0
    
    for i in range(1, n[0]+1):
        if i in bridge:
            bridge.clear()
            counter += 1
        for j in range(prefix, len(reqs)):
            if reqs[j][0] == i:
                bridge.add(reqs[j][1])
            else:
                prefix = j
                break
    
    print(counter)
 
main()

Solution (Python):
n, m = map(int, input().split())
x = sorted(tuple(map(int, input().split()))[::-1] for _ in range(m))
r = p = 0
for b, a in x:
    if p <= a:
        r += 1
        p = b
print(r)

Solution (Python):
n, m = map(int, input().split())
x = [[] for _ in range(n)]
for q in range(m):
    a, b = map(int, input().split())
    x[b-1].append(a-1)
r = p = 0
for i in range(n):
    for j in x[i]:
        if j >= p:
            r += 1
            p = i
print(r)

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

right_bridge,sum_bridge = 0,0
for a, b in village:
    if right_bridge<a:
        right_bridge=b-1
        sum_bridge+=1
        
print(sum_bridge)

Solution (Python):
n,m = map(int,input().split())
r = []
for _ in range(m):
    r.append(tuple(map(int,input().split())))
r.sort(key = lambda x:x[1],reverse = True)
ans = 0
while len(r) > 0:
    _,y = r[-1]
    ans += 1
    while len(r) > 0 and r[-1][0] < y:
        r.pop()
print(ans)

Solution (Python):
n,m = map(int,input().split())
r = []
for _ in range(m):
    r.append(tuple(map(int,input().split())))
r.sort(key = lambda x:x[1],reverse = True)
ans = 0
while len(r) > 0:
    _,y = r[-1]
    ans += 1
    while len(r) > 0 and r[-1][0] < y:
        r.pop()
print(ans)

Solution (Python):
from collections import deque
n,m = map(int,input().split())
r = []
for _ in range(m):
    r.append(tuple(map(int,input().split())))
r = deque(sorted(r,key = lambda x:x[1]))
ans = 0
while len(r) > 0:
    _,y = r[0]
    ans += 1
    while len(r) > 0 and r[0][0] < y:
        r.popleft()
print(ans)

Solution (Python):
from collections import deque
n,m = map(int,input().split())
r = []
for _ in range(m):
    r.append(tuple(map(int,input().split())))
r = deque(sorted(r,key = lambda x:x[1]))
ans = 0
while len(r) > 0:
    _,y = r[0]
    ans += 1
    while len(r) > 0 and r[0][0] < y:
        r.popleft()
print(ans)

Solution (Python):
n,m = map(int,raw_input().split())
arr = []
for _ in range(m):
	a,b = map(int,raw_input().split())
	arr.append((b,a))
arr.sort()
mr = -1
ans = 0
for i in range(m):
	if mr > arr[i][1]:
		continue
	else:
		mr = arr[i][0]
		ans += 1
print ans

Solution (Python):
n,m = map(int,input().split())
war = []
for i in range(m):
    a,b = map(int,input().split())
    war.append([a,b])
war.sort(key = lambda x: x[1])
ans = 1
now = war[0][1]
k = 1
while k < m:
    if war[k][0] >= now:
        ans += 1
        now = war[k][1]
    k += 1
print(ans)

Solution (Python):
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab.sort(key=lambda x: x[1])
c = 0
d = 0
i = 0
for t in ab:
  if d < t[0]:
    c += 1
    d = t[1]-1
print(c)

Solution (Python):


n,m = map(int, input().split())
itv = []
for i in range(m):
    si,ti = map(int, input().split())
    itv.append([ti, si])
itv.sort()

ans = 0
t = 0
for i in range(m):
    if itv[i][1] >= t:
        ans += 1
        t = itv[i][0]

print(ans)

Solution (Python):
import numpy as np

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

a = np.zeros(M, dtype='int')
b = np.zeros(M, dtype='int')
for i in range(M):
    a[i], b[i] = map(int, input().split())

ind = np.argsort(b)
a = a[ind]
b = b[ind]

num_broken_bridge = 0
last_bridge_position = - float("inf")
for i in range(len(a)):
    if a[i] > last_bridge_position:
        last_bridge_position = b[i] - 1
        num_broken_bridge += 1
    
print(num_broken_bridge)

Solution (Python):
def d_islands_war(N, M, Demands):
    demands = sorted(Demands, key=lambda x: x[1])
    _, previous_cut = demands[0]  
    ans = 1
    for a, b in demands[1:]:
        if a >= previous_cut:
            
            ans += 1
            previous_cut = b
    return ans

N, M = [int(i) for i in input().split()]
Demands = [[int(i) for i in input().split()] for j in range(M)]
print(d_islands_war(N, M, Demands))

Solution (Python):

import sys
n, m = map(int, input().split())
demands = [
    tuple(map(int,
              line.strip().split())) for line in sys.stdin.readlines()
]
demands.sort(key=lambda demand: demand[1])

x = -1
cnt = 0
for ai, bi in demands:

    if ai <= x:
        continue

    else:
        x = bi - 1
        cnt += 1

print(cnt)

Solution (Python):
n,m=[int(x) for x in input().split()]
isA,atob=[0]*n,[n+1]*n
for _ in [0]*m:
    ai,bi=[int(x) for x in input().split()]
    isA[ai-1]=1
    atob[ai-1]=min(atob[ai-1],bi-1)
bstack=n+1
ans=0
for a in range(n):
    if bstack==a:
        ans+=1
        bstack=n+1
    if isA[a]==0:
        continue
    bstack=min(bstack,atob[a])
print(ans)

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

inputList = [[int(_) for _ in input().split()] for _ in range(M)]
abList = sorted(inputList, key=lambda x:x[1])

bridge = 0
ans = 0

for ab in abList:
  if not ab[0] <= bridge < ab[1]: 
    bridge = ab[1] -1             
    ans += 1                      

print(ans)

Solution (Python):
NM = [int(i) for i in input().split()]
N, M = NM[0], NM[1]
abList = sorted([[int(i) for i in input().split()] for _ in range(M)], key=lambda x: x[1])
bridge = 0
ans = 0

for ab in abList:
    if not ab[0] <= bridge < ab[1]:
        bridge = ab[1] - 1
        ans += 1

print(ans)

Solution (Python):


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

wars = []

for i in range(m):
    wars.append(list(map(int, input().split())))

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

res = 0
recent_destroyed = -1

for i in range(len(wars)):
    if wars[i][0] <= recent_destroyed and wars[i][1] > recent_destroyed:
        continue
    res += 1
    recent_destroyed = wars[i][1] - 1

print(res)

Solution (Python):
import sys

N, M = map(int, input().split())
A = [0 for i in range(N+1)]
for i in range(M):
	A1, A2 = map(int, input().split())
	if A[A1] > A2 or A[A1] == 0:
		A[A1] = A2
	
ans = 0
min_dir = sys.maxsize
for i in range(1, N+1):
	if A[i] != 0:
		min_dir = min(A[i], min_dir)
	if i >= min_dir:
		ans += 1
		if A[i] != 0:
			min_dir = A[i]
		else:
			min_dir = sys.maxsize
print(ans)

Solution (Python):
n,m=map(int,input().split())
data=sorted([tuple(map(int,input().split())) for i in range(m)],reverse=True)
ans=0
last=-1
for d in data:
    if d[0]<=last<d[1]:
        pass
    else:
        ans+=1
        last=d[0]
print(ans)

Solution (Python):
n, m = map(int, input().split())
array = sorted([[int(x) for x in input().split()] for x in range(m)], key=lambda x:x[1])

deleted_bridges = [array[0][1]-1]
for rule in array:
    bridge_flag = True
    for bridge in deleted_bridges:
        if rule[0] <= bridge < rule[1]:
            bridge_flag = False
            break
    if bridge_flag:
        deleted_bridges.append(rule[1]-1)

print(len(deleted_bridges))

Solution (Python):


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

ab.sort(reverse=True)
x = ab[0][0]
ans = 1
for i in ab:
    if i[1] <= x:
        x = i[0]
        ans += 1

print(ans)

Solution (Python):
N,M=map(int, input().split())
G=[list() for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
ans=0
index=-1
for i in range(1,N):
    for p in G[i]:
        if index<p<i:
            ans+=1
            index=i-1
import time
time.sleep(1.54)
print(ans)

Solution (Python):
N,M=map(int, input().split())
G=[list() for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
ans=0
index=-1
for i in range(1,N):
    for p in G[i]:
        if index<p<i:
            ans+=1
            index=i-1
import time
time.sleep(1.53)
print(ans)

Solution (Python):
N,M=map(int, input().split())
G=[list() for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
ans=0
index=-1
for i in range(1,N):
    for p in G[i]:
        if index<p<i:
            ans+=1
            index=i-1
print(ans)

Solution (Python):
N,M=map(int, input().split())
G=[list() for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
ans=0
index=-1
for i in range(1,N):
    for p in G[i]:
        if index<p<i:
            ans+=1
            index=i-1
import time
time.sleep(1.5)
print(ans)

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

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

idx = ans = 0
for x in data:
  if x[0] >= idx:
    idx = x[1]
    ans += 1

print (ans)

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

paths = []

for i in range(M) :
    _a, _b = map(int, input().split())
    paths.append((_a, _b))

st = sorted(paths, key = lambda x : x[1])
cnt = 0
prev_b = -1

for i in st :
    if cnt == 0 :
        cnt += 1
        prev_b = i[1]
    else :
        if i[0] >= prev_b :
            cnt += 1
            prev_b = i[1]
    
print(cnt)

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

last  = -1  
count = 0   
for a, b in sorted(R, key=lambda r: r[1]):
    if last < a:
        last = b - 1
        count += 1
print(count)

Solution (Python):





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

orders=[]
for i in range(M):
	first, second = map(int, raw_input().split())
	orders.append((first, second))
	


cmpFunc = lambda x, y : x[1] - y[1]
sorted_orders = sorted(orders, cmpFunc)


ret=0
endtime=0
for order in sorted_orders:
	if order[0] >= endtime:
		endtime=order[1]
		ret+=1


print ret

Solution (Python):


















''' 二次元配列を一列ずつ
for i in ans:
	print(*i)
'''
''' heapq
queue = []
heapq.heapify(queue) 
heapq.heappush(queue,num) 
pop = heapq.heappop(queue) 
pop = heapq.heappushpop(queue,num) 

'''

from collections import defaultdict
import sys,heapq,bisect,math,itertools,string
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7


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

left = 0
ans = 0
for q in queue:
	if q[0] >= left:
		ans += 1
		left = q[1]

print(ans)

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

reg = 0
counter = 0

for ab in ass:
    if ab[0]>=reg:
        counter = counter+1
        reg=ab[1]

print(counter)

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 a>x:x=b-1;l+=1
print(l)

Solution (Python):
N,M=map(int, input().split())
G=[list() for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
ans=0
index=-1
for i in range(1,N):
    for p in G[i]:
        if index<p<i:
            ans+=1
            index=i-1
import time
time.sleep(1.5)
print(ans)

Solution (Python):
N,M=map(int, input().split())
G=[list() for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
ans=0
index=-1
for i in range(1,N):
    for p in G[i]:
        if index<p<i:
            ans+=1
            index=i-1
import time
time.sleep(1)
print(ans)

Solution (Python):
N, M = map(int,input().split()) 
a = []
for i in range(M):
    l, r = map(int,input().split())
    a.append((r, l))
a.sort()
ans = 0
last = -1
for i in range(0, M):
    r, l = a[i]
    if last <= l:
        ans = ans + 1
        last = r
print (ans)

Solution (Python):



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

N, M = map(int, input().split())
war = []
for i in range(M):
    war.append(get_list())
war.sort()

cnt = 1
west, east = war[0]

for i in range(1, len(war)):
    west_chk, east_chk = war[i]
    if west_chk < east and east <= east_chk:
        pass
    elif east <= west_chk:
        cnt += 1
        east = east_chk
    elif east_chk < east:
        east = east_chk
        
print(cnt)

Solution (Python):



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

N, M = map(int, input().split())
war = []
for i in range(M):
    war.append(get_list())
war.sort()

cnt = 1
west, east = war[0]

for i in range(1, len(war)):
    west_chk, east_chk = war[i]
    if west_chk < east and east <= east_chk:
        pass
    elif east <= west_chk:
        cnt += 1
        east = east_chk
    elif west_chk < east:
        east = east_chk
        
print(cnt)

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

A = []
for i in range(0, M):
    l, r = (int(i) for i in input().split())
    A.append((r, l))

A.sort()

ans = 0
last = -1
for i in range(0, M):
    r, l = A[i]
    if last <= l:
        ans = ans + 1
        last = r

print (ans)

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

ans = []


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


cnt = 0
ans.append(num_list[0][1] - 1)
for i in num_list:
    cnt += 1
    last = ans[-1]
    
    if last not in range(i[0], i[1] + 1):
        
        
        
        ans.append(i[1] - 1)

print(len(ans))

Solution (Python):
N,M=map(int, input().split())
G=[list() for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
ans=0
index=-1
for i in range(1,N):
    for p in G[i]:
        if index<p<i:
            ans+=1
            index=i-1
print(ans)

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

Solution (Python):

import sys
n, m = map(int, input().split())
demands = [
    tuple(map(int,
              line.strip().split())) for line in sys.stdin.readlines()
]
demands.sort(key=lambda demand: demand[1])

x = -1
cnt = 0
for ai, bi in demands:

    if ai <= x:
        continue

    else:
        x = bi - 1
        cnt += 1

print(cnt)

Solution (Python):

import sys
n, m = map(int, input().split())
demands = [
    tuple(map(int,
              line.strip().split())) for line in sys.stdin.readlines()
]
demands.sort(key=lambda demand: demand[1], reverse=True)

x = -1
cnt = 0
while demands:
    ai, bi = demands.pop()

    if ai > x:
        x = bi - 1
        cnt += 1

else:
    print(cnt)

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

ans = 1
p = n+1
for i in range(m):
    if p == n+1:
        p = a[i][0]

    elif p < a[i][1]:
        pass
    else:
        p = a[i][0]
        ans += 1
print(ans)

Solution (Python):
s=input().split()
n=int(s[0])
m=int(s[1])
l=[]
for i in range(m):
    s=input().split()
    l.append((int(s[1]),int(s[0])))
l.sort()
o=[]
for p in l:
    if len(o)>0 and p[0]>=o[-1]>p[1]:
        continue
    else:
        o.append(p[0])
print(len(o))

Solution (Python):
n,m=map(int,input().split())
v,r,ans=[float('inf') for i in range(n)],float('inf'),0
for i in range(m):
	a,b=map(lambda x:int(x)-1,input().split())
	v[a]=min(v[a],b)
for i in range(n-1):
	r=min(r,v[i])
	if r-i==1:
		ans+=1
		r=float('inf')
print(ans)

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

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

requests.sort(key=lambda x:x[1])
answer=1
pulldown=(requests[0][1]-1)-1
for i in range(1,M):
    if requests[i][0]-1 <= pulldown:
        pass
    else:
        pulldown=(requests[i][1]-1)-1
        answer+=1
print(answer)

Solution (Python):
n,m=map(int,input().split())
s=[]
for i in range(m):
    a,b=map(int,input().split())
    s.append([a,b-1])
s.sort(key=lambda x:x[1])
ans=0
t=None
for i,j in s:
    if(t is None or t<i):
        t=j
        ans+=1

print(ans)

Solution (Python):



if __name__ == '__main__':
    n, m = list(map(int, input().split()))
    ab = sorted([tuple(map(int, input().split())) for _ in range(m)],
                key=lambda x: x[1])
    count = 1

    
    
    b = ab[0][1]

    for i in range(1, m):
        if ab[i][0] >= b:
            b = ab[i][1]
            count += 1

    print(count)

Solution (Python):
N, M = map( int, input().split())
Q = [[int(s) for s in input().split()] for _ in range(M)]
Q = sorted(Q)
ans = 1
LQ = len(Q)
stan = Q[0][1]
while LQ != 0:
    k = 1
    if Q[0][0] < stan:
        stan = min(stan,Q.pop(0)[1])
        LQ -= 1
    else:
        ans += 1
        stan = Q[0][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)
ans = 1
LQ = len(Q)
stan = Q[0][1]
while LQ != 0:
    k = 1
    if Q[0][0] < stan:
        stan = min(stan,Q.pop(0)[1])
        LQ -= 1
    else:
        ans += 1
        if LQ == 0:
            break
        else:
            stan = Q[0][1]
print(ans)

Solution (Python):

def main():
    n, m = [int(x) for x in input().split()]
    ab = [[int(x) for x in input().split()] for _ in range(m)]

    ab.sort(key=lambda x: x[1]) 
    cut = []
    for a, b in ab:
        c = False
        for x, y in cut:
            if a <= x:
                c = True
                break
        if not c:
            cut.append((b-1, b))

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