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

Solution (Python):


from pprint import pprint
from copy import deepcopy





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

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


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

counter = 0
before_point = -float('inf')



for i in range(m):
    if requests[i][0] >= before_point:
        counter += 1
        before_point = requests[i][1]
        
    else:
        
        pass

print(counter)

Solution (Python):


from pprint import pprint
from copy import deepcopy





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

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


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

counter = 0
before_point = -float('inf')



for i in range(m):
    if requests[i][0] >= before_point:
        counter += 1
        before_point = requests[i][1]
        
    else:
        
        pass

print(counter)

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

ans = 1
stock = need[0][1]
for i in range(m):
  if stock <= need[i][0]:
    ans += 1
    stock = need[i][1]
    
print(ans)

Solution (Python):
def main():
    N, M = map(int, input().split())
    island = []
    for i in range(M):
        a, b = map(int, input().split())
        island.append(tuple((a, b)))
    
    s = sorted(island, key=lambda x:x[1])
    
    base = s[0][1]
    cnt = 1
    for i in range(1, len(s)):
        if(s[i][0] >= base):
            base = s[i][1]
            cnt += 1
    print(cnt)
    
main()

Solution (Python):
from operator import itemgetter

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

AB = [tuple(map(int, input().split())) for _ in range(M)]
AB.sort(key = itemgetter(1))

counter = 0
last_b = -1
for a, b in AB:
    if a >= last_b:
        counter += 1
        last_b = b

print(counter)

Solution (Python):
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(key=lambda x: x[1])
    r = 0
    p = 0
    for i, j in l:
        if p <= i:
            p = j
            r += 1 
    print(r)
main()

Solution (Python):
def main():
    N, M = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in range(M)]
    AB.sort(key=lambda x: x[1])
    c = -1
    r = 0
    for a, b in AB:
        if a >= c:
            c = b
            r += 1
    return r

print(main())

Solution (Python):
import sys
from operator import itemgetter
sys.setrecursionlimit(1000000) 

def main():
    input = sys.stdin.readline  
    N, M = map(int, input().rstrip().split())

    require_list = []
    for _ in range(M):
        s, e = map(int, input().rstrip().split())
        require_list.append([s, e])
    require_list.sort(key=itemgetter(1))

    count = 1
    now_require = require_list[0]
    for next_require in require_list[1:]:
        
        if now_require[1] <= next_require[0]:
            count += 1
        else:
            next_require[1] = now_require[1]
        now_require = next_require

    print(count)

if __name__ == '__main__':
    main()

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

p = [tuple(map(int,input().split())) for _ in [0]*m]

p = sorted(p)

ans = 0
area = (0,0)
for x,y in p:
  if area[0]<=x and x<area[1]:
    area = x,min(area[1],y)
  else:
    ans+=1
    area = x,y
print(ans)

Solution (Python):
from sys import stdin
def main():
    
    readline=stdin.readline
    N,M=map(int,readline().split())
    ab=[0]*M
    for i in range(M):
        ab[i]=list(map(int,readline().split()))

    ab.sort(key=lambda x:x[1])
    res=0
    for i in range(M):
        a=ab[i][0]
        b=ab[i][1]
        if i==0:
            bridge=b-1
            res+=1
        else:
            if a<=bridge:
                pass
            else:
                bridge=b-1
                res+=1
    
    print(res)

if __name__=="__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,m=MI()
lis=[]
for i in range(m):
    lis.append(LI())
lis.sort(key=lambda x:x[1])

bri=0
count=0
for i in range(m):
    if bri<=lis[i][0]:
        bri=lis[i][1]
        count+=1
        
print(count)

Solution (Python):
import sys, heapq, bisect, math, fractions
from collections import deque

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

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

for a, b in AB:
    if not a <= bridge: 
        res += 1
        bridge = b - 1

print(res)

Solution (Python):
import sys, heapq, bisect, math, fractions
from collections import deque

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

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

for a, b in AB:
    if not a <= bridge: 
        res += 1
        bridge = b - 1

print(res)

Solution (Python):
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right


from functools import reduce
from pprint import pprint

INF = float("inf")

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

n,m = myinput()
ab = mylistinput(m)

ab = mysort(ab,1,False)


e = 0

count = 0
for i in range(m):
    a = ab[i][0]
    b = ab[i][1]
    if e <= a:
        count += 1
        e = b
print(count)

Solution (Python):
n, m = map(int, input().split())
lst = []
for i in range(m):
    ai, bi = map(int, input().split())
    ai, bi = ai-1, bi-1
    lst.append([ai, bi])

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

ans = 1
kiru = lst[0][1]
for i in range(1, m):
    if lst[i][0] >= kiru:
        ans += 1
        kiru = lst[i][1]

print(ans)

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

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


B=sorted(B)
now=-1
pre=1
ans=0
for i in range(M):
    
    left,right=B[i]
    if i==0:
        now=left
        pre=right
        if i==M-1:
            ans+=1
        continue
    if i==M-1:
        ans+=1
    if now!=left and pre<=left:
        now=left
        ans+=1
        pre=right
    elif now!=left and pre>left:
        pre=min(pre,right)
        continue
    elif now==left:
        pre=min(pre,right)
    

print(ans)

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)]
    AB.sort(key=lambda x:x[1])
    ans=0
    pre=-1
    for a,b in AB:
        if pre<=a:
            ans+=1
            pre=b
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)
MOD = 10 ** 9 + 7

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

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

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

ans = 0

right = N + 1
for a, b in AB:
    if a < right:
        right = min(right, b)
    else:
        ans += 1
        right = b

print (ans + 1)

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

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
prev_b = -1

for a, b in ab:
    if a>=prev_b:
        ans += 1
        prev_b = b

print(ans)

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

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

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

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

mx = 10**18
ans = 0
for a, b in AB:
    if a >= mx:
        ans += 1
        mx = 10**18
    mx = min(mx, b)
print(ans + 1)

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

Solution (Python):
from sys import stdin
N,M = [int(x) for x in stdin.readline().rstrip().split()]
data = []
for i in range(M):
    a,b = [int(x) for x in stdin.readline().rstrip().split()]
    data.append((b,a))

data.sort()

ans = 1
right = data[0][0]
for b,a in data:
    if a < right:
        continue
    else:
        ans += 1
        right = b
print(ans)

Solution (Python):
N, M = map(int, input().split())
inf =  10**9
brid = [inf]*N
for i in range(M):
  a, b =  map(int, input().split())
  brid[a-1] =min(b, brid[a-1])
right_side =  N+1
ans = 0
for i in range(N-1, -1, -1):
  if brid[i] == inf:
    continue
  else:
    if brid[i] <= right_side:
      ans += 1
      right_side = i+1
print(ans)

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

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

right=l[0][1]
cnt=1
for i in range(M):

    if right<=l[i][0]:
        cnt+=1
        right=l[i][1]
print(cnt)

Solution (Python):
n, m = list(map(int, input().split()))
wars = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]

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

tail = 0
cnt = 0

for i in range(m):
    if sorted_wars[i][0] >= tail:
        tail = sorted_wars[i][1]
        cnt += 1
print(cnt)

Solution (Python):


import sys



from operator import itemgetter              














from copy import copy, deepcopy                    



def main():
    mod = 1000000007                
    inf = float('inf')              
    
    sys.setrecursionlimit(10**6)    
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    """
    橋を [x_left, x_left + 1) の整数座標区間と考える
    (0-index で) 頂点 i から j へ行けなくする = [i, j) の整数座標区間とかぶるような橋を選択する
    全ての要望 m 個について [i, j) の整数座標区間を用意し、それらと最も被っているような橋を選択 -> 削除 & それにより条件が満たされた整数座標区間も削除...
    を貪欲で行えれば行ける気がしたが嘘貪欲 (半分くらい WA)、TLE
    """

    n, m = mi()
    edge = []
    for _ in range(m):
        a, b = mi()
        edge.append((a, b - 1))
    edge.sort(key=itemgetter(0))

    cnt = 0
    
    prev_left = n + 1
    prev_right = n
    for start, end in edge:
        if start > prev_right:
            cnt += 1
            prev_left = start
            prev_right = end
        
        else:
            prev_left = start
            prev_right = min(prev_right, end)

    
    if prev_left <= prev_right:
        cnt += 1
    print(cnt)


if __name__ == "__main__":
    main()

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

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

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

cnt=0
for i in range(m):
    
    if(i==0):
        last = req[i][1]
        cnt+=1
        continue
    now = req[i][0]
    if(now < last):
        continue
    last = req[i][1]
    cnt+=1

print(cnt)

Solution (Python):
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)


def main():
    N, M = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(M)]
    AB = sorted(AB, key=lambda x: x[0])
    flag = AB[0][1]
    cnt = 1
    for i in range(M):
        if AB[i][0] >= flag:
            flag = AB[i][1]
            cnt += 1
        elif AB[i][1] > flag:
            continue
        else:
            flag = AB[i][1]
    print(cnt)


if __name__ == "__main__":
    main()

Solution (Python):
import sys


def input():
    return sys.stdin.readline().strip()


sys.setrecursionlimit(20000000)


def main():
    N, M = map(int, input().split())
    AB = [list(map(int, input().split())) for _ in range(M)]
    AB = sorted(AB, key=lambda x: x[0])
    flag = AB[0][1]
    cnt = 1
    for i in range(M):
        if AB[i][0] >= flag:
            flag = AB[i][1]
            cnt += 1
        elif AB[i][1] > flag:
            continue
        else:
            flag = AB[i][1]
    print(cnt)


if __name__ == "__main__":
    main()

Solution (Python):
import sys

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


def input():
    return sys.stdin.readline().strip()


def main():
    N, M = map(int, input().split())
    AB = []
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        AB.append((a, b))
    AB.sort(key=lambda x: x[0])

    cnt = 0
    end = INF
    for a, b in AB:
        if a >= end:
            cnt += 1
            end = b
        else:
            end = min(b, end)

    cnt += 1
    print(cnt)


if __name__ == "__main__":
    main()

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

ans = 0
ed = 0
for _ in lst:
    if _[0] < ed:
      pass
    else:
        ed = _[1]
        ans += 1
print(ans)

Solution (Python):
from operator import itemgetter

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

print(ans)

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])
bridge=[0]*n
flag=0
for w in war:
    if not w[0]<=flag<w[1]:
        flag=w[1]-1
        bridge[flag]=1
print(sum(bridge))

Solution (Python):
from operator import itemgetter

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

a = []
b = []

for i in range(M):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)

st = sorted([(a[i],b[i]) for i in range(M)], key=itemgetter(1))

ans = 0
last = -10000000

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

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

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


ans=0
nL=M[0][0]
nR=M[0][1]
for i in range(m):
    L=M[i][0]
    R=M[i][1]
    if nR<=L:
        ans+=1
        nL=L
        nR=R
    else:
        nL=L
        nR=min(nR,R)
ans+=1
print(ans)

Solution (Python):

N, M = [int(str) for str in input().strip().split()]
ab = [[int(str) for str in input().strip().split()] for _ in range(M)]


def solve():
    ab.sort(key=lambda x: x[1])
    ans = 0
    broken = 0
    for a, b in ab:
        if a < broken:
            continue
        broken = b
        ans += 1
    print(ans)

solve()

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

Solution (Python):



import numpy
from collections import defaultdict

def main():
  n, m = map(int, input().split())
  db2a = defaultdict(list)
  for _ in range(m):
    a, b = map(int, input().split())
    db2a[b-1].append(a-1)
    
  cnt = 0
  end = 0
  for b in sorted(db2a.keys()):
    if end <= max(db2a[b]):
      cnt += 1
      end = b
  print(cnt)

if __name__=='__main__':
  main()

Solution (Python):



import numpy
from collections import defaultdict

def main():
  n, m = map(int, input().split())
  db2a = defaultdict(list)
  for _ in range(m):
    a, b = map(int, input().split())
    db2a[b-1].append(a-1)
    
  cnts = numpy.zeros(n, dtype=numpy.int)
  i = 0
  for b in sorted(db2a.keys()):
    cnts[i:b] = cnts[i-1]
    cnts[b] = max(cnts[max(db2a[b])] + 1, cnts[b-1])
    i = b + 1
  cnts[i:] = cnts[i-1]
  print(cnts[-1])

if __name__=='__main__':
  main()

Solution (Python):
def main():
    N, M = map(int, input().split())
    y = []
    for i in range(M):
        y.append(list(map(int, input().split())))
    youbou = sorted(y, key = lambda x:x[1])
    
    cnt = 0
    k = 0
    for i in range(M):
        if(youbou[i][0] >= k):
            cnt += 1
            k = youbou[i][1]
    print(cnt)
main()

Solution (Python):
def main():
    N, M = map(int, input().split())
    wish = []
    for i in range(M):
        wish.append(tuple(map(int, input().split())))
    w = sorted(wish, key=lambda x:x[1])
    
    cnt = 0
    ans = 0
    for i in range(M):
        if(w[i][0] >= cnt):
            ans += 1
            cnt = w[i][1]
    print(ans)
main()

Solution (Python):
import numpy as np


N, M = map(int, input().split())
AB = np.array([input().split() for _ in range(M)], np.int32)
AB = sorted(AB, key=lambda x: x[1])
ans, end = 0, 0
for a, b in AB:
    
    if end <= a:
        ans += 1
        end = b
print(ans)

Solution (Python):
import sys
LI = lambda : [int(x) for x in sys.stdin.readline().split()]

N,M = LI()
island = [0 for _ in range(N)]
req = [[] for _ in range(N)]
for _ in range(M):
    a,b = LI()
    req[a-1].append(b-1)

p = 1
ans = 0
for i in range(N):
    if island[i] > p:
        ans += 1
        p = island[i]
    for b in req[i]:
        island[b] = p+1
print(ans)

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N,M = LI()
island = [0 for _ in range(N)]
req = [[] for _ in range(N)]
for _ in range(M):
    a,b = LI()
    req[a-1].append(b-1)

p = 1
ans = 0
for i in range(N):
    if island[i] > p:
        ans += 1
        p = island[i]
    for b in req[i]:
        island[b] = p+1
print (ans)

Solution (Python):
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
AB.sort()
prev, ans = AB[0][1], 1
for a, b in AB[1:]:
    if prev <= a:
        ans += 1
        prev = b
    else:
        prev = min(prev, b)
print(ans)

Solution (Python):
import sys
from operator import itemgetter
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
 
def main():
    N, M = map(int, readline().split())
    ab = map(int, read().split())
    ab = sorted(zip(ab, ab), key=itemgetter(1))
 
    east_island = ab[0][1]
    answer = 1
 
    for i, j in ab:
        if i >= east_island:
            answer += 1
            east_island = j
 
    print(answer)
 
 
if __name__ == '__main__':
    main()

Solution (Python):
from operator import itemgetter

def main():
  N, M = map(int, input().split())
  ab = [tuple(map(int, input().split())) for _ in range(M)]
  ab.sort(key=itemgetter(1))
  east_island = ab[0][1]
  answer = 1

  for i, j in ab:
      if i >= east_island:
          answer += 1
          east_island = j

  print(answer)


if __name__ == '__main__':
    main()

Solution (Python):
from operator import itemgetter

N, M = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(M)]
ab.sort(key=itemgetter(1))
east_island = ab[0][1]
answer = 1

for i, j in ab:
    if i >= east_island:
        answer += 1
        east_island = j

print(answer)

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

cnt = 0
l = 1
r = N
for left, right in islands:
    if r <= left:
        cnt += 1
        l = left
        r = right
    else:
        l = max(l, left)
        r = min(r, right)

print(cnt+1)

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

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

req.sort()

removed = 0
last = 0
for b, a in req:
    if a >= last:
        removed += 1
        last = b

print(removed)

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

ans = 1
t = AB[0][1]-1

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

Solution (Python):



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

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


itv = []
for i in range(M):
    itv.append([graph[i][1] - 1, graph[i][0]])

itv = sorted(itv)


tt = 0 
ans = 0
for i in range(M):
    
    
    
    if(itv[i][1] > tt):
        tt = itv[i][0]
        ans += 1
        
print(ans)

Solution (Python):
n,m=map(int,input().split())
war=[list(map(int,input().split())) for i in range(m)]
war=sorted(war)
right=0
left=0
ans=0
for i in range(m):
  if right<=war[i][0]:
    ans+=1
    right=war[i][1]
    left=war[i][0]
  else:
    left=war[i][0]
    right=min(war[i][1],right)
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],x[0]))

f = ab[0][1]
ans = 0
for a,b in ab:
  if a >= f:
    ans += 1
    f = b
    
print(ans+1)

Solution (Python):
inf = 10**15
mod = 10**9+7
n,m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
ab.sort(key=lambda x:x[1])
pre = -inf
ans=0
for tmp in ab:
    a,b = tmp
    if a >= pre:
        ans+=1
        pre=b
print(ans)

Solution (Python):
N, M = list(map(int, input().split(' ')))
left_list = list()
right_list = list()
for _ in range(M):
    a, b = list(map(int, input().split(' ')))
    left_list.append(a)
    right_list.append(b)
sorted_blocking_section_list = sorted(range(M), key=lambda i: right_list[i])
blocking_bridge = None
blocking_bridge_cnt = 0
for section in sorted_blocking_section_list:
    left_bridge = left_list[section]
    right_bridge = right_list[section] - 1
    if blocking_bridge is None or blocking_bridge < left_bridge:
        blocking_bridge = right_bridge
        blocking_bridge_cnt += 1
print(blocking_bridge_cnt)

Solution (Python):
from operator import itemgetter

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

a = []
b = []

for i in range(M):
    ao,bo = map(int,input().split())
    a.append(ao)
    b.append(bo)

ab = sorted([(a[i],b[i]) for i in range(M)], key = itemgetter(1))

ans = 0
last = 0

for i in range(M):
    if last <= ab[i][0]:
        ans += 1
        last = ab[i][1]

print(ans)

Solution (Python):
from operator import itemgetter

n, m = map(int, input().split())
youbou = [tuple(map(int, input().split())) for _ in range(m)]
ab = sorted(youbou, key=itemgetter(1))

ans = 0
removed = 0

for a, b in ab:
    if a >= removed:
        ans += 1
        removed = b  

print(ans)

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

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

L=sorted(L)
preb=0
ans=0
for l in L:
    b,a=l
    if preb<=a:
        ans+=1
        preb=b
print(ans)

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

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

Solution (Python):
N, M = map(int,input().split())
B = sorted([list(map(int,input().split())) for k in range(M)],key = lambda x: x[1])
now = -1
ans = 0
for e in B:
    if now <= e[0]:
        ans += 1
        now = e[1]
print(ans)

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

b = [[] for _ in range(n)]
for i,j in ab:
    b[j].append(i)
ans = n-1


class UnionFind:
    def __init__(self, n):
        self.parent = [-1] * n
        self.rank = [1] * n
        self.count = [1] * n

    def get_root(self, i):
        while self.parent[i] != -1:
            i = self.parent[i]
        return i

    def is_same_tree(self, i, j):
        return self.get_root(i) == self.get_root(j)

    def merge(self, i, j):
        i = self.get_root(i)
        j = self.get_root(j)
        if i == j:
            return

        if self.rank[i] > self.rank[j]:
            self.parent[j] = i
            self.rank[i] = max(self.rank[i], self.rank[j] + 1)
            self.count[i] += self.count[j]
        else:
            self.parent[i] = j
            self.rank[j] = max(self.rank[j], self.rank[i] + 1)
            self.count[j] += self.count[i]

uf = UnionFind(n)

for i in range(1,n):
    ok = True
    for j in b[i]:
        if uf.is_same_tree(i - 1, j):
            ok = False
    if ok:
        ans -= 1
        uf.merge(i, i - 1)

print(ans)

Solution (Python):
import sys
from operator import itemgetter

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    Cut = [[int(i) - 1 for i in input().split()] for _ in range(M)]
    Cut.sort(key = itemgetter(1))
    count = 1
    cindex = 1
    cutPlace = Cut[0][1]
    while cindex < M:
        if Cut[cindex][0] < cutPlace: cindex += 1
        else:
            count += 1
            cutPlace = Cut[cindex][1]
            cindex += 1
    print(count)

    return 0

if __name__ == "__main__":
    solve()

Solution (Python):
def main():
    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])
    ma = AB[0][1]
    ans = 1
    for a, b in AB[1:]:
        if a < ma:
            continue
        else:
            ma = b
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import heapq

def main():
    n, m = map(int, input().split())
    ab = [None] * m
    for i in range(m):
        ab[i] = list(map(int, input().split()))

    ab.sort()

    que = []
    cut_front = 0
    for x in ab:
        if que:
            if que[0] <= x[0]:
                cut_front += 1
                que.clear()
        heapq.heappush(que, x[1])
    if que:
        cut_front += 1
        que.clear()

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

    cut_back = 0
    for x in ab:
        if que:
            if x[1] <= -que[0]:
                cut_back += 1
                que.clear()
        heapq.heappush(que, -x[0])
    if que:
        cut_back += 1
        que.clear()

    print(min(cut_front, cut_back))

if __name__ == '__main__':
    main()

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

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

count = 1
B = 10 ** 9
for a, b in AB:
    if a < B:
        B = min(B, b)
    else:
        count += 1
        B = b

print (count)

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

ab.sort()

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

print(ans)

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

ab.sort()
l=1
r=N
ans=1
for a,b in ab:
  l=max(a,l)
  r=min(b,r)
  if l>=r:
    ans+=1
    l=a
    r=b
print(ans)

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


if __name__ == '__main__':
    main()

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 a,b in ab[1:]:
  if r<=a:
    ans+=1
    l,r=a,b
  else:
    l=max(l,a)
    r=min(r,b)
print(ans)