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

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

ans = 0
now = -1

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter
input = sys.stdin.readline

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

ans = 0
now = -1

li.sort(key = itemgetter(1))

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

print(ans)

Submission status: Accepted

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

ans = 0
now = -1

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

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

print(ans)

Submission status: Accepted

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(N, M, inputs):
    requests = list(map(lambda x: string_to_int(x), inputs))
    requests = sorted(requests, key=lambda x: x[1])

    deleted = []
    last = 0

    for request in requests:
        if request[0] > last:
            deleted.append(request[1] - 1)
            last = deleted[-1]

    return len(deleted)


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    [N, M] = string_to_int(input())
    ret = solve(N, M, inputs(M))
    print(ret)

Submission status: Accepted

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

for i in ab:
    if i[0] < last:
        continue
    else:
        last = i[1]
        ans += 1

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()
result = 0
min_b = N + 1
p = 0
for i in range(1, N + 1):
    if i == min_b:
        result += 1
        min_b = N + 1
    while p < M and i == ab[p][0]:
        min_b = min(min_b, ab[p][1])
        p += 1
print(result)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 19 20:12:17 2019

@author: Owner
"""

from operator import itemgetter
import bisect

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


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

ab = tuple(sorted(ab, key = itemgetter(1)))

#print(ab)
x_rm = -1
res = 0
for m in range(M):
    if ab[m][0] < x_rm:
        continue
    else:
        x_rm = ab[m][1]
        res += 1
    
    
        

print(res)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
claim = []
for i in range(M):
	claim.append(list(map(int, input().split())))
claim.sort(key=lambda a:a[1])

ans = 0
inter = [-1,-1]
for land in claim:
    if inter[1] <= land[0]:
        inter = land
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(m)]
arr=sorted(arr,key=lambda x:x[0])
arr=sorted(arr,key=lambda x:x[1])
cnt=0
pos=0
for i in range(m):
  if arr[i][0]<pos:
    continue
  else:
    cnt+=1
    pos=arr[i][1]
print(cnt)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
ab=[list(map(lambda x:int(x)-1,input().split())) for i in range(M)]
x=[0]*(N-1)
for i in range(M):
    if x[ab[i][0]]>ab[i][1] or x[ab[i][0]]==0:
        x[ab[i][0]]=ab[i][1]
flag=0
a=N
cnt=0

for i in range(N-1):
    if flag==0 and x[i]==0:
        continue
    elif flag==0 and x[i]>0:
        flag=1
        a=x[i]
        cnt+=1
    elif i<a:
        if x[i]<a and x[i]!=0:
            a=x[i]
    else:
        if x[i]>0:
            a=x[i]
            cnt+=1
        else:
            flag=0
            a=N
print(cnt)

Submission status: Accepted

Solution code:
from operator import itemgetter
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
ab.sort(key=itemgetter(1))
b_min = ab[0][1]
cut = 1
for abi in ab:
    if abi[0] >= b_min:
        cut += 1
        b_min = abi[1]
    b_min = min(b_min ,abi[1])
print(cut)

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 = 0
t = 0
for a, b in ab:
    if t <= a:
        ans += 1
        t = b

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
pairs = []
for i in range(m):
    a, b = map(int, input().split())
    pairs.append((a, b))
pairs.sort(key=lambda x: x[1], reverse=True)

res = 1

mina = pairs[0][0]
for i in range(m):
    a, b = pairs[i]
    if b <= mina:
        res += 1
        mina = a
    mina = max(mina, a)

print(res)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
e = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    e[a].append(b)
ans = 0
minb = float("inf")
for i in range(1, N + 1):
    if i == minb:
        ans += 1
        minb = float("inf")
    if len(e[i]):
        minb = min(minb, min(e[i]))
print(ans)

Submission status: Accepted

Solution code:
#coding utf-8
N,M=map(int,input().split())
ans=0
ba = [[0 for _ in range(2)] for _ in range(M)]

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

br=0
for b,a in ba:
  if not(a<br<b):
    br=b-0.5
    ans +=1
  
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
need=[tuple(map(int,input().split())) for i in range(M)]
ans=0
need.sort(key=lambda x:x[1])
bef=1
for a,b in need:
    if a<bef:
        continue
    else:
        ans+=1
        bef=b
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])

#print(ab)

count, last = 0, None
for a, b in ab:
	if not last:
		last = b
		count += 1
	if last <= a:
		last = b
		count += 1
print(count)

Submission status: Accepted

Solution code:
n, m = [int(i) for i in input().split()]
a=[]
b=[]
for i in range(m):
    x1, y1 = [int(i) for i in input().split()]
    a.append(x1)
    b.append(y1)

c = zip(b,a)
c = sorted(c)
b,a = zip(*c)

#print(a,b)
ans = 0
point=0

for i in range(m):
    if a[i]<point<b[i]:
        continue
    else:
        ans += 1
        point=b[i]-0.5

print(ans)

Submission status: Accepted

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

cutleftfrom = 0
cnt = 0
for a, b in sorted([list(map(int, input().split())) for _ in range(M)], key=lambda x:x[1]):
    if a < cutleftfrom:
        continue
    cutleftfrom = b
    cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
"""
- N個の島とN-1個の橋
- i番目の橋は島iと島i+1を接続する
- ai番目とbi番目の島の間での諍いを止めたい
    - aiとbi番目の島を隔離する
- こんな要望がM個

始点と終点が必要そうだから、2次元に値を保存してみる⇨遅い。ダメ
"""
import heapq
N,M = map(int, input().split())

# たくさん値を持っておく必要はない
# 左端を固定しながら、右端の一番近いところを算出していく
# 一番近いところを切れれば、それより遠いところも自ずと切れる
dic = {}
for i in range(M):
    a, b = map(int, input().split())
    if a not in dic or dic[a] > b:
        dic[a] = b

# 条件が厳しい右から考えていくパターン
# a,bで考えて,まだ着られていない(最後に切られたposより右にある)なら、aで切る(最も左端)
# 切った左端よりも左側にあるならもう一回切る必要がある。そうじゃないなら切る必要なし
cnt = 0
pos = 1000000000000
for j in sorted(dic.keys(),reverse=True): # 降順に並べる(右側から)
    if dic[j] <= pos:
        cnt += 1
        pos = j
print(cnt)

Submission status: Accepted

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

conf.sort()
divp.append(conf[0][0]-1)
for i in range(1, M):
  if divp[-1] < conf[i][1]:
    divp.append(conf[i][0]-1)
print(len(divp))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

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

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, M = LI()
    bars = []
    for _ in range(M):
        a, b = LI_()
        bars.append((a,b))
    bars = sorted(bars, key=lambda x: x[0])
    l_max = bars[0][0]
    r_min = bars[0][1]

    count = 1 
    for bar in bars[1:]:
        l, r = bar
        if r_min <= l:
            count += 1
            r_min = r
        else:
            r_min = min(r, r_min)
        l_max = l

    print(count)
main()

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
hope=[tuple([int(i) for i in input().split()]) for j in range(M)]
hope.sort(key=lambda x:x[1])
ans=0
prebroke=0#prebroke=2 :島2と島3を結ぶ橋
for s,g in hope:
    if s<=prebroke:
        continue
    else:
        ans+=1
        prebroke=g-1
print(ans)

Submission status: Accepted

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

bdg = -1
cnt = 0
for a, b in X:
    if a > bdg:
        bdg = b - 1
        cnt += 1
        
print(cnt)

Submission status: Accepted

Solution code:
"""
区間スケジューリング
終端で降順にソートすれば良い
最適解は，貪欲法で，1つ次の区間を通るように串刺すこと
終端で降順にソートしているので，1本で区間を刺せる条件はi<jのとき，a[i]<b[j]
さらにその後，刺せる範囲が狭まる場合(a[i]>b[i])は，狭めて次の区間に行く
"""
n, m=map(int, input().split())
hope=[]
for i in range(m):
    a, b=map(int, input().split())
    hope.append((a, b))
hope.sort(reverse=True, key=lambda x: x[1])
ans=0
for i in range(m-1):
    if i==0:
        target=hope[i][0]
    if target<hope[i+1][1]:
        if target<hope[i+1][0]:
            target=hope[i+1][0]
    else:
        ans=ans+1
        target=hope[i+1][0]
print(ans+1)

Submission status: Accepted

Solution code:
"""
区間スケジューリング
終端で降順にソートすれば良い
"""
n, m=map(int, input().split())
hope=[]
for i in range(m):
    a, b=map(int, input().split())
    hope.append((a, b))
hope.sort(reverse=True, key=lambda x: x[0])
hope.sort(reverse=True, key=lambda x: x[1])
ans=0
for i in range(m-1):
    if i==0:
        target=hope[i][0]
    if target<hope[i+1][1]:
        if target<hope[i+1][0]:
            target=hope[i+1][0]
    else:
        ans=ans+1
        target=hope[i+1][0]
print(ans+1)

Submission status: Accepted

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

ans = 0
ba = [[0 for _ in range(2)] for _ in range(m)]

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

ba.sort()

br = 0
for b,a in ba:
    #if bridge[(a-1):] != 0:
    if not (a < br < b):
        #bridge[b-2] = 0
        br = b - 0.5
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
*D, = open(0)
n, m = map(int, D[0].split())
edges = [list(map(int, it.split())) for it in D[1:]]
edges = sorted(edges, key=lambda x:x[1])

bridge = edges[0][1]
cnt = 1
for a, b in edges[1:]:
    if bridge <= a:
        bridge = b
        cnt += 1
print(cnt)

Submission status: Accepted

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


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    ll = [[a[i],b[i]] for i in range(M)]

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

    endtime = 0
    ans = 0
    for i in range(M):
        if(endtime <= ll[i][0]):
            endtime = ll[i][1]
            ans += 1
        
    print(ans)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]" 
    b = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 2019 6/7
# ABC 103 D Island War

from operator import itemgetter
from collections import deque


def find_ans(queue):
    cnt = 0
    while len(queue):
        head = queue.popleft()
        i = 0
        while i < len(queue):
            if head[1] <= queue[i][0]:
                break
            queue.popleft()
        cnt += 1

    return cnt


if __name__ == '__main__':
    N, M = map(int, input().split())
    islands = []
    queue = deque()
    for i in range(M):
        island = list(map(int, input().split()))
        islands.append(island)
    # islands.sort(key=lambda x: x[1])
    islands.sort(key=itemgetter(1))
    for i in range(M):
        queue.append(islands[i])
    print(find_ans(queue))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
pair = []
ans = 0
x = 0

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

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


for (i,j) in pair:
    if i > x:
        x = j - 1
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
L = [[int(v) - 1 for v in input().split()] for _ in range(M)]
L.sort(key = lambda x:(-x[1], -x[0]))

ans = 1
sx, sy = L[0]
for i in range(1, M):
    x, y = L[i]
    
    if sx >= y:
        ans += 1
        sx = x
    elif sx <= x:
        sx = x
    
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
l.sort(key=lambda x:x[1])
c=[l[0][1]]
for i,j in l[1:]:
    if i<c[-1]<=j:pass
    else:c.append(j)
print(len(c))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np

def main():
	N, M = map(int, input().split(" "))
	ab = []
	
	for _ in range(M):
		a, b = map(int, input().split(" "))
		ab.append((a, b))
		
	ab = sorted(ab, key=lambda x:(x[1]))
	ans = 0
	otosu = -1
	for i, val in enumerate(ab):
		a, b = val
		if i == 0:
			ans += 1
			otosu = b
			continue
		if otosu <= a:
			ans += 1
			otosu = b
			continue
	
	print(ans)
	
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
from collections import Counter
from collections import deque
from functools import reduce
from pprint import pprint
import bisect
import copy
import fractions
import itertools
import math
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers): return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers): return reduce(LCM, numbers)
def LCM(m, n): return (m * n // fractions.gcd(m, n))


n, m = MI()
bridge = sorted([LI() for _ in range(m)], key=lambda x: x[1])
ans = 0
endtime = 0
for i in range(m):
    if endtime <= bridge[i][0]:
        endtime = bridge[i][1]
        ans += 1 
print(ans)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self,n):
        self.parent = [-1 for _ in range(n)]

    def size(self,x):
        return -self.parent[self.find(x)]

    def find(self,x):
        if(self.parent[x]<0):
            return x
        else:
            self.parent[x]=self.find(self.parent[x])
            return self.parent[x]

    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return False
        if(self.size(x)<self.size(y)):
            self.parent[y]+=self.parent[x]
            self.parent[x]=y
        else:
            self.parent[x]+=self.parent[y]
            self.parent[y]=x
        return True

    def same(self,x,y):
        return self.find(x)==self.find(y)

N,M = [int(x) for x in input().split()]
ab = [[int(x) for x in input().split()]for _ in range(M)]
#%%
di = {}
for i in ab:
    if(i[0] in di):
        di[i[0]].append(i[1])
    else:
        di[i[0]]=[i[1]]
    if(i[1] in di):
        di[i[1]].append(i[0])
    else:
        di[i[1]]=[i[0]]

joint = 0
un = UnionFind(N)
for i in range(N):
    if(i==0): pass
    else:
        flag = True
        if(i+1 in di):
            for j in di[i+1]:
                if(un.find(i-1)==un.find(j-1)):
                    flag = False
        if(flag):
            joint += 1
            un.unite(i-1,i)
print(N-1-joint)

Submission status: Accepted

Solution code:
import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
from bisect import bisect_left, bisect_right
# import numpy as np
 
def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W
 
# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

N, M = l_inpl()
l = []
for _ in range(M):
    li = l_inpl()
    l.append(li)

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

ans = 0
cur = None
for li in l:
    if cur is None:
        cur = li[1] - 1
        ans += 1
    elif not (li[0] <= cur <= li[1]):
        cur = li[1] - 1
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
qs = [list(map(int, input().split())) for _ in range(M)]
qs.sort(key = lambda x: x[1], reverse = True)
ans = 0
prv = 0
while qs:
    a, b = qs.pop()
    if prv <= a:
        ans += 1
        prv = b
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
st=[[] for i in range(n)]
en=[[] for i in range(n)]
ju=[0 for i in range(m)] #0：未処理、1：処理中、－１：処理後
for i in range(m):
    a,b=map(int,input().split())
    st[a-1].append(i)
    en[b-1].append(i)
ans=0
co=0
now=[]
while(co<n):
    if len(now)!=0 and len(en[co])!=0:
        ch=False
        for i in en[co]:
            if ju[i]==1:
                ch=True
        if ch:       
            for i in now:
                ju[i]=-1
            ans+=1
            now=[]
    for i in st[co]:
        ju[i]=1
        now.append(i)
    co+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N, M = (int(i) for i in input().split())
dic = {}
cnt = 0
pos = 0
for i in range(M):
    a, b = map(int, input().split())
    if b not in dic or dic[b] < a:
        dic[b] = a

for j in sorted(dic.keys()):
    if dic[j] >= pos:
        cnt += 1
        pos = j
print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import operator


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):

    AB = list(zip(a,b))
    AB.sort(key=operator.itemgetter(1))

    db = []
    for a,b in AB:
        bAppend = True
        for di in db:
            if a <= di < b:
                bAppend = False
                break
        if bAppend:
            db.append(b-1)

    print(len(db))


    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]" 
    b = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

r = -1
for i in range(M):
    if war[i][0] <= r:
        continue
    else:
        ans += 1
        r = war[i][1]-1
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
L = sorted([list(map(int,input().split())) for i in range(M)],key = lambda x:x[1])
p,res = 0,0
for a,b in L:
    if a > p:
        p = b-1
        res += 1
print(res)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
L = [list(map(int,input().split())) for i in range(M)]
L.sort()
ans = 0
l,r = 0,0
for a,b in L:
    l = a
    if r <= a:
        ans += 1
        r = b
    else:
        r = min(r,b)
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
L = [list(map(int,input().split())) for i in range(M)]
L.sort()
ans = 1
l = L[0][0]
r = L[0][1]
for a,b in L:
    if r <= a:
        ans += 1
        l = a
        r = b
    else:
        l = a
        r = min(r,b)
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
L = [list(map(int,input().split())) for i in range(M)]
L.sort()
ans = 1
l = L[0][0]
r = L[0][1]
for a,b in L:
    if r <= a or l >= b:
        ans += 1
        l = a
        r = b
    else:
        l = a
        r = min(r,b)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
N, M = map(int, input().split())
L = [tuple(map(int, input().split())) for i in range(M)]
L_sort = sorted(L, key=lambda x:x[1])
ans = 0
rb = 0
for l in L_sort:
    if l[0] > rb:
        rb = l[1] - 1
        ans += 1
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 x: x[1])

count = 0
c = 0
for (a, b) in AB:
    if a >= c:
        count += 1
        c = b

print(count)

Submission status: Accepted

Solution code:

N,M= list(map(int,input().split(" ")))
yobos = []

for _ in range(M):
     yobos.append(list(map(int, input().split(" "))))
yobos.sort(key=lambda x:x[1])
right = yobos[0][1]
ans = 1
for yobo in yobos[1:]:
    if yobo[0] >= right:
        right = yobo[1]
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    qs = sorted(list(zip(a, b)), reverse=True)
    
    ret = 0
    d = float('inf')
    for ai, bi in qs:
        if bi < d:
            ret += 1
            d = ai + 1
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]" 
    b = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    result = solve(N, M, a, b)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

def main():
    N, M = LI()
    demands = []
    for i in range(M):
        demands.append(LI())

    demands = sorted(demands, key=lambda x: x[1])
    demands_met_flag = [False]*len(demands)

    counter = 0
    deleting_bridge = 0
    for i in range(len(demands)):
        if demands_met_flag[i] == True: continue
        if demands[i][0] <= deleting_bridge:
            demands_met_flag[i] = True
            continue
        demand = demands[i]
        demands_met_flag[i] = True
        counter += 1
        deleting_bridge = demand[1]-1

    print(counter)

main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
AB=[]
append=AB.append
for i in range(m):
  a,b=map(int,input().split())
  append([a,b])
AB.sort(key=lambda x:x[1])
c,ans=0,0
for a,b in AB:
  if a>=c:
    ans+=1
    c=b
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()
L=10**6
ans=0
for a,b in ab[::-1]:
    if not a<=L<b:
        ans+=1
        L=a
print(ans)

Submission status: Accepted

Solution code:
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    n , m = f()
    d = []
    for i in range(m):
        d.append(f())
    
    d = [(i[0], i[1]-1) for i in d]

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


    cover = 0
    cnt = 0
    for i in d:
        if i[0]>cover:
            cover = i[1]
            cnt += 1

    
    print(cnt)



solve()

Submission status: Accepted

Solution code:
from functools import partial
from itertools import islice


def take(n, iterable):
    return list(islice(iterable, n))


def chunked(iterable, n):
    return iter(partial(take, n, iter(iterable)), [])


def solve(string):
    n, m, *ab = map(int, string.split())
    ab = sorted([tuple(_ab) for _ab in chunked(ab, 2)])
    cl = cr = None
    ans = 0
    for a, b in ab:
        if cr is None or cr <= a:
            cl, cr = a, b
            ans += 1
            continue
        cl = a if cl < a else cl
        cr = cr if cr < b else b
    return str(ans)


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(m)])))

Submission status: Accepted

Solution code:
from operator import itemgetter

N, M = list(map(int, input().split()))
ab = sorted([list(map(int, input().split())) for i in range(M)], key=itemgetter(1))
ans = B = 0

for a, b in ab:
    if a >= B:
        ans += 1
        B = b
print(ans)

Submission status: Accepted

Solution code:
N, M = [int(t) for t in input().split()]
a = [[0]*2 for i in range(M)]
for i in range(M):
    a[i][0], a[i][1] = [int(t) for t in input().split()]

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

count = 1
flag = b[0][1]
for i in range(1, M):
    if b[i][0] < flag:
        continue
    elif b[i][1] > flag:
        flag = b[i][1]
        count += 1

print(count)

Submission status: Accepted

Solution code:
N, M = [int(t) for t in input().split()]
a = [[0]*2 for i in range(M)]  # 始点と距離
for i in range(M):
    s, e = [int(t) for t in input().split()]
    a[i][0] = s - 1
    a[i][1] = e - 1

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

count = 1
flag = b[0][1]
for i in range(1, M):
    if b[i][0] < flag:
        continue
    elif b[i][1] > flag:
        flag = b[i][1]
        count += 1

print(count)

Submission status: Accepted

Solution code:
from functools import partial
from itertools import islice


def take(n, iterable):
    return list(islice(iterable, n))


def chunked(iterable, n):
    return iter(partial(take, n, iter(iterable)), [])


def solve(string):
    n, m, *ab = map(int, string.split())
    ab = sorted([tuple(_ab) for _ab in chunked(ab, 2)])
    cl = cr = None
    ans = 0
    for a, b in ab:
        if cr is None or cr <= a:
            cl, cr = a, b
            ans += 1
            continue
        cl, cr = max(cl, a), min(cr, b)
    return str(ans)


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(m)])))

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
T=[]
for i in range(M):
    u,v=map(int,input().split())
    u,v=u,v-1
    T.append([u,v])
T.sort(key=lambda x:x[1])
tmp=0
ans=0
for i in range(M):
    if tmp<T[i][0]:
        tmp=T[i][1]
        ans+=1
print(ans)

Submission status: Accepted

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

war.sort()

ans = 1
removed_bridge = war[0][0]-1
for i in range(M):
    if war[i][1] > removed_bridge:
        removed_bridge = war[i][0]-1
        ans += 1

print(ans)