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



Sample input:
5 2
1 4
2 5


Sample output:
1

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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())

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter
sys.setrecursionlimit(1000000) # 再帰上限を増やす

def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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
#s=input().rstrip()
n,m=MI()
lis=[]
for i in range(m):
    lis.append(LI())
lis.sort(key=lambda x:x[1])
#print(lis)
bri=0
count=0
for i in range(m):
    if bri<=lis[i][0]:
        bri=lis[i][1]
        count+=1
        
print(count)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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 math import gcd,ceil,floor,factorial
# from fractions import gcd
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):
    # lsはソート済みであること
    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)
# print(ab)

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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)
#print(B)

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
from copy import copy, deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    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())
    
    
    # n, m = mi()
    # edge = set()
    # for _ in range(m):
    #     a, b = mi_0()
    #     edge.add((a, b - 1))
    
    # cnt = 0
    # while edge:
    #     accum = [0] * n
    #     for start, end in edge:
    #         accum[start] += 1
    #         accum[end + 1] -= 1
    #     prev = 0
    #     covered_edge_max = 0    # 現時点で残されているインターバルについて最もかぶっているようなポイントを探す。その被っているインターバルの個数
    #     point_x = 0    # そのポイントの座標
    #     for i in range(n):
    #         accum[i] += prev
    #         prev = accum[i]
    #         if accum[i] > covered_edge_max:
    #             covered_edge_max = accum[i]
    #             point_x = i
    #     # print(accum)
    #     cnt += 1
    #     tmp = copy(edge)
    #     for elm in edge:
    #         start, end = elm
    #         if start <= point_x <= end:
    #             tmp.remove(elm)
    #     edge = tmp
    #     print(edge)
    # print(cnt)
    """
    橋を [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
        # 包含 or ずれているパターン
        else:
            prev_left = start
            prev_right = min(prev_right, end)

    # edge さえあれば必ず +1 されて欲しい (最後に区間が余るので)
    if prev_left <= prev_right:
        cnt += 1
    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
#区間スケジューリング
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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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()
#print(M)

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)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

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

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

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

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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:
    # print(end, a, b)
    if end <= a:
        ans += 1
        end = b
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

Solution code:
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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
## coding: UTF-8
##区間スケジューリング問題

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

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

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

itv = sorted(itv)
#print(itv)

tt = 0 #終点を保持
ans = 0
for i in range(M):
    #print('i:{},tt:{}, itv[i]:{}'.format(i, tt, itv[i]))
    #起点が現状の終点よりも後ろだったらその区間は満たしてやらないといけない
    #満たすのはその区間の終点でいい。なぜなら終点でソートしているので、その区間の終点を満たしてやったとしてもでこれから先に出てくる区間を抜かしてしまうことはないし、最大効率で他の区間も充たせるから
    if(itv[i][1] > tt):
        tt = itv[i][0]
        ans += 1
        #print('ans:{}, tt:{}'.format(ans, tt))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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  # b島の直前の橋を取り除く

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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