Problem:
 Score : 400 points    Problem Statement There are N islands lining up from west to east, connected by N-1 bridges.  The i -th bridge connects the i -th island from the west and the (i+1) -th island from the west.  One day, disputes took place between some islands, and there were M requests from the inhabitants of the islands:  Request i : A dispute took place between the a_i -th island from the west and the b_i -th island from the west. Please make traveling between these islands with bridges impossible.  You decided to remove some bridges to meet all these M requests.  Find the minimum number of bridges that must be removed.      Constraints  All values in input are integers.  2 \leq N \leq 10^5  1 \leq M \leq 10^5  1 \leq a_i < b_i \leq N  All pairs (a_i, b_i) are distinct.         Input Input is given from Standard Input in the following format:  N  M  a_1  b_1  a_2  b_2  :  a_M  b_M       Output Print the minimum number of bridges that must be removed.        Sample Input 1 5 2
1 4
2 5      Sample Output 1 1  The requests can be met by removing the bridge connecting the second and third islands from the west.       Sample Input 2 9 5
1 8
2 7
3 5
4 6
7 9      Sample Output 2 2       Sample Input 3 5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5      Sample Output 3 4

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

AB = [tuple(map(int, input().split())) for _ in range(M)]
AB.sort(key=lambda a: (a[0], -a[1]))

ans = 1
right = 10**18
for l, r in AB:
    if l >= right:
        ans += 1
        right = 10**18
    right = min(right, r)
print(ans)

Solution (Python):

import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    brs = sorted(zip(a, b), key=lambda br: br[1])
    last = -1
    ans = 0
    for ai, bi in brs:
        if ai <= last:
            continue
        ans += 1
        last = bi - 1
    print(ans)


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):
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(M)]
ab.sort(key=lambda t: t[1])
ans = 0
now_r = 0

for a, b in ab:
    if now_r<=a:
        ans += 1
        now_r = b

print(ans)

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

    ans = 0
    saw = 0

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

    for a, b in troubles:
        if saw <= a:
            saw = b
            ans += 1

    print(ans)
    
resolve()

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

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

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

ans = 0
for i in range(M):
  if i == 0:
    temp = R[i][1]-1 
    ans += 1
  else:
    if R[i][0] > temp:
      temp = R[i][1]-1
      ans += 1
print(ans)

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

count=1
mae=s[0][1]
for i in range(1,M):
    if s[i][0]>=mae:
        count+=1
        mae=s[i][1]

print(count)

Solution (Python):
INF = 10 ** 9
MOD = 10 **9 + 7
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from  collections import deque
from math import factorial

def main():
    n,m = map(int,input().split())
    War = [tuple(map(int,input().split())) for _ in range(m)]
    War.sort(key = lambda x:x[1])

    last_cut = 0
    ans = 0
    for a,b in War:
        if last_cut < a:
            last_cut = b - 1
            ans += 1
    print(ans)
if __name__=='__main__':
    main()

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

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

kijun=warlist[0][0]-1
bukkowashi=0

for war in warlist:
	if war[0] >= kijun:
		bukkowashi += 1
		kijun = war[1]

print(bukkowashi)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, m = map(int, readline().split())
ab = [tuple(map(int, readline().split())) for _ in range(m)]
ab.sort(key=lambda x: x[1])
cnt = 0
check = -1
for a, b in ab:
    if a <= check < b:
        continue
    check = b - 1
    cnt += 1
print(cnt)

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

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

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

MAX = 10 ** 9

count = 1
min_ = MAX
for a, b in AB:
    if a < min_:
        min_ = min(min_, b)
    else:
        count += 1
        min_ = b

print (count)

Solution (Python):
def main():
    N,M=map(int,input().split())
    a=[0]*M
    b=[0]*M
    r=[0]*M
    for i in range(M):
        a[i],b[i]=map(int,input().split())
        r[i]=[a[i],b[i]]
    r.sort(key=lambda x:x[1])
    point=float("-inf")
    pyout=0
    for fight in r:
        if fight[0]>point:
            point=fight[1]-1
            pyout+=1
    print(pyout)
if __name__=='__main__':
    main()

Solution (Python):
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
L = [LIST() for i in range(M)]
L = sorted(L, key=lambda x: x[1])
tmp = L[0][1]

ans = 1

for a, b in L:
    if a < tmp <= b:
        continue
    else:
        ans += 1
        tmp = b
print(ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    AB = [[int(i) for i in input().split()] for j in range(M)]
    AB.sort(key=lambda p: p[1])
    mx_b = AB[0][1]
    ans = 1
    for a, b in AB[1:]:
        if a < mx_b:
            continue
        else:
            mx_b = b
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

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

a.sort()

ans=1

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

print(ans)

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

ans = 0
ab.sort()
for i, (ai, bi) in enumerate(ab):
    if i == 0:
        l = ai
        r = bi - 1
        ans += 1
    else:
        l_tmp = max(l, ai)
        r_tmp = min(r, bi - 1)
        if l_tmp > r_tmp:
            l = ai
            r = bi - 1
            ans += 1
        else:
            l = l_tmp
            r = r_tmp

print(ans)

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    
    N,M=MI()
    ab=[[0,0]for _ in range(M)]
    for i in range(M):
        ab[i][0],ab[i][1]=MI()
        
    ab.sort(key=lambda x:(x[0],-1*x[1]))
    ans=0
    
    left=-1
    right=N+1
    for i in range(M):
        if ab[i][0]>=right:
            left=ab[i][0]
            right=ab[i][1]
            ans+=1
        else:
            left=ab[i][0]
            right=min(right,ab[i][1])
            
    print(ans+1)
            

main()

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

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

lst.sort(key=lambda x: x[1])
end = -1
ctr = 0
for a, b in lst:
    if a < end: continue
    end = b
    ctr += 1

print(ctr)

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

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


t = -1
ans = 0
for i in range(m):
    a, b = X[i]
    if a >= t:
        ans += 1
        t = b
    else:
        continue
print(ans)

Solution (Python):
from operator import itemgetter
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
AB.sort(reverse=True, key=itemgetter(1))

ans = 1
left, right = AB.pop()
while AB:
    a, b = AB.pop()
    if a >= right:
        ans += 1
        left, right = a, b
    else:
        right = min(right, b)
        left = max(left, a)
print(ans)

Solution (Python):
from heapq import heappush, heappop

N, M = map(int, input().split())
LR = [tuple(map(int, input().split())) for _ in range(M)]
LR.sort(key=lambda a: (a[0], -a[0]))

R = 10**18
ans = 0
for l, r in LR:
    if R <= l:
        ans += 1
        R = 10**18
    R = min(R, r)

print(ans + 1)

Solution (Python):
import sys
def main():
    input = sys.stdin.readline
    N,M=map(int, input().split())
    AB=[tuple(map(int, input().split())) for _ in range(M)]
    from operator import itemgetter
    AB.sort(key=itemgetter(1))
    ans=0
    last=-1
    for a,b in AB:
        if last<=a:
            ans+=1
            last=b
    print(ans)

if __name__ == '__main__':
    main()

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

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

broken = [False] * (N - 1)

right = -1
for a,b in AB:
    if a > right:
        broken[b - 1] = True
        right = b - 1

print(broken.count(True))

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

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

r = -1
cnt = 0
for a, b in AB:
    if r <= a:
        cnt += 1
        r = b
    else:
        r = min(r, b)
print(cnt)

Solution (Python):
def main():
    n, m = map(int, input().split())
    query = [[int(x) for x in input().split()] for _ in range(m)]
    break_bridges = [-1]
    query.sort(key=lambda x: x[1])
    for begin, end in query:
        if not (begin <= break_bridges[-1] < end):
            break_bridges.append(end - 1)
    print(len(break_bridges) - 1)


if __name__ == '__main__':
    main()

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

Solution (Python):
n,m=map(int,input().split())
ab=[list(map(int,input().split()))for _ in range(m)]
ab.sort()
l,r=ab[0]
ans=1
for i,j in ab[1:]:
  if j<=l or r<=i:
    ans+=1
    l,r=i,j
  l=max(l,i)
  r=min(r,j)
print(ans)

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

cnt=0
flag=0
ma=war[0][0]
for i in range(M):
    if war[i][1]<=ma:
        cnt=cnt+1
        flag=0
        ma=war[i][0]
print(cnt+1)

Solution (Python):
N, M = map(int, input().split())
Bridge = []
for i in range(M):
    a, b = map(int, input().split())
    Bridge.append((a, b))
now = -10000000000
Bridge.sort(key=lambda x: x[1])
ans = 0

for i in range(M):
    if Bridge[i][0] >= now:
        ans += 1
        now = Bridge[i][1]

print(ans)

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

Solution (Python):
from operator import itemgetter

n,m = map(int, input().split())
ab = sorted([list(map(int, input().split())) for i in range(m)], key=itemgetter(1,0))
end = 1
ans = 0
for s,e in ab:
  if s >= end:
    ans += 1
    end = e
print(ans)

Solution (Python):
import sys

input=sys.stdin.readline

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

bomb.sort()

count=0
last=-1
for i in range(0,len(bomb)):
    b,a=bomb[i]
    if b-1>=last and last>=a:
        continue
    else:
        count+=1
        last=b-1

print(count)

Solution (Python):
nim,mike = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(mike)]
ab.sort()
result = 1
l, r = ab[0][0], ab[0][1]

for a,b in ab[1:]:
    if a < r:
        l = max(l,a)
        r = min(r,b)
    else:
        result += 1
        l = a
        r = b 

print(result)

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

base = AB[0][1]
ans = 1
for ab in AB[1:]:
    if ab[0] < base <= ab[1]:
        continue
    else:
        ans += 1
        base = ab[1]
print(ans)

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

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

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

q = -1
ctr = 0

for i in range(M):
    if lst[i][0] < q: continue
    ctr += 1
    q = lst[i][1]

print(ctr)

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

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

bridge=0
count=0
for wish in sorted_wish:
  left=wish[0]
  right=wish[1]
  if left>=bridge and right>bridge:
    count+=1
    bridge=right
print(count)

Solution (Python):
import sys

def main():
    N, M = map(int, input().split())
    LR = [tuple(map(int, input().split())) for _ in range(M)]
    RL = sorted([(R, L) for L, R in LR])

    now = 0
    ans = 0
    for R, L in RL:
        if L > now:
            now = R-1
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

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

war.sort(key=lambda x: x[1])
ans = 0
tmp = -1
for l, r in war:
    if tmp <= l:
        ans += 1
        tmp = r
print(ans)

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

l,r = ab[0][0],ab[0][1]-1

ans = 1

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

print(ans)

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

A = [0]*(N+1)

for i in range(M):
    A[data[i][1]] = max(A[data[i][1]],data[i][0])

ans = 0
a = 0
for i in range(1,N+1):
    if A[i] == 0:
        continue
    else:
        if A[i] >= a:
            ans += 1
            a = i

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

cnt=0
border=0

for item in ab:
    if item[0]>=border:
        border=item[1]
        cnt+=1

print(cnt)

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

ll=ab[0][0]
rr=ab[0][1]

cnt=1

for item in ab[1:]:
    l=item[0]
    r=item[1]
    if l>=rr:
        cnt+=1
        ll=l
        rr=r
    else:
        if r<rr:
            rr=r
        if ll<l:
            ll=l
    

print(cnt)

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

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

T=L_new[0][1]-1
count=1
for j in range(1,M):
    if L_new[j][0]<=T:
        pass
    else:
        count+=1
        T=L_new[j][1]-1

print(count)

Solution (Python):
def main():
    islands, request_num = map(int, input().split())
    demolition = []
    requests = []
    for _ in range(request_num):
        requests.append(list(map(int, input().split())))
    requests.sort(key=lambda x: x[1], reverse=False)
    for begin, end in requests:
        if 0 < len(demolition) and begin <= demolition[-1] < end:
            continue
        else:
            demolition.append(end - 1)
    print(len(demolition))


if __name__ == '__main__':
    main()

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

for i in range(m):
    ba.append(list(map(int, input().split())))
    ba[i][0], ba[i][1] = ba[i][1] - 1, ba[i][0] - 1

ba.sort()
bridge = [ba[0][0] - 1]


for i in range(1, m):
    if ba[i][1] > bridge[-1]:
        bridge.append(ba[i][0] - 1)

print(len(bridge))

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

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

Solution (Python):

"""
問題：
一列にn個の島があり、n-1本の橋で左右の島がつながっている。
m個のクエリが与えられ、aとbの島を橋を取り除くことにより行き来できないようにしたい。
取り除かなければならない橋の本数の最小値を出力

解法：
橋をかけても良い島を探す。
クエリをソートしておいて、左端が入ったものから右端をheapに入れる。heapqで取り出したものが右端であるならば、
そこに橋をかけないものとして、heapをリセットする。(heapに入っている全ての条件がクリアされる為)
"""
import sys
import heapq
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

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

g = []
for i in range(m):
    a,b = map(int,readline().split())
    a,b = a-1,b-1
    g.append((a,b))
g.sort()
heap = []
heapq.heapify(heap)
now = 0
count = 0
for i in range(n-1): 
    while now < m:
        if g[now][0] == i: 
            heapq.heappush(heap,g[now][1]) 
            now += 1
        else:
            break
    
    if len(heap):
        res = heapq.heappop(heap)
        if res == i+1: 
            count += 1
            heap = []
            heapq.heapify(heap)
        else:
            heapq.heappush(heap,res)
    

print(count)

Solution (Python):
n,m = [int(x) for x in input().split()]
a = []
for _ in range(m):
    a.append([int(x) for x in input().split()])
a.sort(key=lambda x: x[1])
ans = 0
r = 0
for i in range(m):
    if r<=a[i][0]:
        r = a[i][1]
        ans+=1
print(ans)

Solution (Python):

n,m = list(map(int,input().split()))
d = [0]*m
spr = [True]*m
ma = 0
mi = 0
for i in range(m):
    a,b = list(map(int,input().split()))
    d[i] = [a,b]

d = sorted(d)
pre = d[0][1]
ans = 1
for i,(a,b) in enumerate(d):
  if a < pre:
    if b < pre:
      pre = b
  else:
    ans += 1
    pre = b

print(ans)

Solution (Python):
import sys
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
def main():
    n, m = MII()
    ab = sorted([(MII()) for _ in range(m)], key=lambda x: x[1])
    pre = -1
    cnt = 0
    for a, b in ab:
        a -= 1; b-= 1
        if a>=pre: cnt+=1; pre=b
    print(cnt)


if __name__ == '__main__':
    main()

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

Solution (Python):
N, M = map(int, input().split(" "))
prohibit = {i: set() for i in range(N)}

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

now = set([0])
ans = 0
for i in range(1, N):
    if len(now & prohibit[i]) > 0:
        now = set([i])
        ans += 1
    else:
        now.add(i)
print(ans)

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

lr.sort(key = lambda x : x[1])
ans = 0
rm = 0 
for i in range(m):
    if lr[i][0] <= rm: 
        continue
    rm = lr[i][1] - 1  
    ans += 1

print(ans)

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

lr.sort(key = lambda x : x[1])
ans = 0
rm = 0 
for i in range(m):
    if lr[i][0] <= rm and lr[i][1] >= rm + 1: 
        continue
    rm = lr[i][1] - 1  
    ans += 1

print(ans)

Solution (Python):
NumIslands, NumRequest = map(int, input().split())
ListConflict = [[int(_) for _ in input().split()] for i in range(NumRequest)]

ListConflict = sorted(ListConflict, key=lambda x: x[1])
right_island_compare = ListConflict[0][1]
total_remove = 1

for i_left_island, i_right_island in ListConflict[1:]:
    if i_left_island < right_island_compare:
        continue

    right_island_compare = i_right_island
    total_remove += 1

print(total_remove)

Solution (Python):

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

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



c = 0

ans = 0

for a,b in l:
    if a >= c:
        c = b
        ans += 1

print(ans)

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

Solution (Python):
n, m = map(int, input().split())
w = [list(map(int, input().split())) for _ in range(m)]
w.sort(key=lambda x: x[1])
f = -float('inf')
ans = 0
for p, q in w:
    if p >= f:
        ans += 1
        f = q
print(ans)

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

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

ans = 1
start = s[0][1]
end = s[0][0]
for i in range(1,m):
    temp_start = s[i][1]
    temp_end = s[i][0]
    if temp_start >= end:
        ans += 1
        end = temp_end
    
print(ans)

Solution (Python):

def submit():
    n, m = map(int, input().split())
    
    dislike = [tuple(map(int, input().split())) for _ in range(m)]
    dislike.sort(key=lambda x: x[1])

    cnt = 0
    prev_cut = -1
    for da, db in dislike:
        if da <= prev_cut < db:
            continue
        else:
            cnt += 1
            prev_cut = db - 1

    print(cnt)


submit()

Solution (Python):
N,M = map(int,input().split())
ts = []
for i in range(M):
    a,b = map(int,input().split())
    ts.append([b,a])
ts.sort()
tmp = 0
count = 0
for i in range(M):
    if ts[i][1]>=tmp:
        tmp = ts[i][0]
        count += 1
print(count)

Solution (Python):
def main():
    islands, request_num = map(int, input().split())
    demolition = []
    requests = []
    for _ in range(request_num):
        requests.append(list(map(int, input().split())))
    requests.sort(key=lambda x: x[0], reverse=True)
    for begin, end in requests:
        if 0 < len(demolition) and begin <= demolition[-1] < end:
            continue
        else:
            demolition.append(begin)
    print(len(demolition))


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate, groupby
    
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    

    
    

    n,m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(m)]
    ab.sort(key=lambda a: a[1])
    res = 0
    cur = 0
    for i in range(m):
        if cur <= ab[i][0]:
            res += 1
            cur = ab[i][1]
    print(res)

if __name__ == '__main__':
    main()

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

rightest_bridge = -1
ans = 0
for a, b in query:
    if a > rightest_bridge:  
        ans += 1
        rightest_bridge = b-1
print(ans)

Solution (Python):
if __name__ == '__main__':
    N, M = map(int, input().split())
    hopes = []
    for _ in range(M):
        a, b = map(int, input().split())
        hopes.append([b, a])
    hopes.sort()
    ans = 0
    pos = -1
    for idx, (e, s) in enumerate(hopes):
        if idx == 0 or pos <= s:
            ans += 1
            pos = e
    print(ans)

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

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

end = ab[0][1]
cursol = 0
end = ab[0][1]
cnt = 1
while cursol < M -1:
    cursol += 1
    if end <= ab[cursol][0]:
        end = ab[cursol][1]
        cnt += 1
print(cnt)

Solution (Python):
N,M = map(int,input().split())
Alist = []
for i in range(M):
    array = list(map(int, input().strip().split()))
    Alist.append(array)
Alist.sort()
q = 0
p = [Alist[0][0],Alist[0][1]]
for i in range(len(Alist)-1):
    if p[0] < Alist[i+1][0]:
        p[0] = Alist[i+1][0]
    if p[0] >= p[1]:
        q = q+1
        p = [Alist[i+1][0],Alist[i+1][1]]
    if p[1] > Alist[i+1][1]:
        p[1] = Alist[i+1][1]
print(q+1)

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

ab.sort(key=lambda ab:ab[1])
ans=[ab[0]]
for i in range(1,m):
    if ans[-1][1]<=ab[i][0]:
        ans.append(ab[i])
print(len(ans))

Solution (Python):
import sys

input = sys.stdin.readline


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

    ans = 1
    right = AB[0][1]
    left = AB[0][0]
    for a, b in AB[1:]:
        if a >= right:
            ans += 1
            right = b
            left = a
        else:
            left = max(left, a)
            right = min(right, b)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

input = sys.stdin.readline


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

    ans = 1
    right = AB[0][1]
    left = AB[0][0]
    for a, b in AB[1:]:
        if a >= right:
            ans += 1
            right = b
            left = a
        else:
            left = max(left, a)
            right = min(right, b)

    print(ans)


if __name__ == '__main__':
    main()

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

print(ans)

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

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

ans = 0
pre = 0

for i in range(m):
    a, b = req[i]
    if a < pre:
        continue
    pre = b
    ans += 1
    
print(ans)

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


req = []
for _ in range(m):
    a, b = map(int, input().split())
    req.append((a, b))
req.sort(key=lambda x: x[1])
ans = 0
pre = 0
for a, b in req:
    if a >= pre:
        ans += 1
        pre = b
print(ans)

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


war = sorted(war,key=lambda x:x[1])
a = 0
ans = 0
for i in range(M):
    if a <= war[i][0]:
        a= war[i][1]
        ans +=1
    else:
        continue
print(ans)

Solution (Python):
import numpy as np

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

b = np.array(b)
idx = np.argsort(b)
a=np.array(a)
a=a[idx]

n=1
r = a[0][1]
for i in range(M):
  if r <= a[i][0]:
    n+=1
    r=a[i][1]

print(n)

Solution (Python):
import sys
from io import StringIO
import unittest


def resolve():
    
    n, m = map(int, input().split())

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

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

    
    new_remove_bridge = 0
    
    remove_bridge_count = 0

    for demand in demands:

        
        
        
        if new_remove_bridge  < demand[0]:
            new_remove_bridge = demand[1] -1
            remove_bridge_count += 1

    print(str(remove_bridge_count))



class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """5 2
1 4
2 5"""
        output = """1"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """9 5
1 8
2 7
3 5
4 6
7 9"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5"""
        output = """4"""
        self.assertIO(input, output)

if __name__ == "__main__":
    
    resolve()

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

Solution (Python):


import sys

def main():
    n, m = map(int, input().split())
    a = []
    b = []
    atoi = [[] for i in range(n)]
    btoi = [[] for i in range(n)]
    for i in range(m):
        aa, bb = map(int, sys.stdin.readline().split())
        a.append(aa - 1)
        b.append(bb - 1)
        atoi[aa - 1].append(i)
        btoi[bb - 1].append(i)

    achieved = [False for i in range(m)]
    res = 0
    aptr = -1  
    for x in range(n - 1):
        tobreak = False
        for i in btoi[x + 1]:
            if not achieved[i]:
                tobreak = True
        if tobreak:
            res += 1
            while aptr < x:
                aptr += 1
                for j in atoi[aptr]:
                    achieved[j] = True
    print(res)

if __name__ == "__main__":
    main()

Solution (Python):


import sys
from collections import defaultdict

def main():
    n, m = map(int, input().split())
    a = []
    b = []
    atoi = defaultdict(list)
    btoi = defaultdict(list)
    for i in range(m):
        aa, bb = map(int, sys.stdin.readline().split())
        a.append(aa - 1)
        b.append(bb - 1)
        atoi[aa - 1].append(i)
        btoi[bb - 1].append(i)

    achieved = [False for i in range(m)]
    res = 0
    aptr = -1  
    for x in range(n - 1):
        tobreak = False
        for i in btoi[x + 1]:
            if not achieved[i]:
                tobreak = True
        if tobreak:
            res += 1
            while aptr < x:
                aptr += 1
                for j in atoi[aptr]:
                    achieved[j] = True
    print(res)

if __name__ == "__main__":
    main()

Solution (Python):


from collections import defaultdict

def main():
    n, m = map(int, input().split())
    a = []
    b = []
    atoi = defaultdict(list)
    btoi = defaultdict(list)
    for i in range(m):
        aa, bb = map(int, input().split())
        a.append(aa - 1)
        b.append(bb - 1)
        atoi[aa - 1].append(i)
        btoi[bb - 1].append(i)

    achieved = [False for i in range(m)]
    res = 0
    aptr = -1  
    for x in range(n - 1):
        tobreak = False
        for i in btoi[x + 1]:
            if not achieved[i]:
                tobreak = True
        if tobreak:
            res += 1
            while aptr < x:
                aptr += 1
                for j in atoi[aptr]:
                    achieved[j] = True
    print(res)

if __name__ == "__main__":
    main()