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:
# Youtubeをみて作りましょう


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

request_list = []

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

ans = 0
f = False

while True:
    ans += 1
    end_point = request_list[0][1]
    for i in range(len(request_list)):
        if request_list[0][0] < end_point:
            del request_list[0]
            if len(request_list) == 0:
                f = True
                break
        else:
            break
            
            
    
    if f:
        break
    
print(ans)

Submission status: Accepted

Solution code:
def solve(n, m, a, b):
    x = -1/2
    ans = 0
    for s, t in sorted(zip(a, b), key=lambda _:_[1]):
        if x < s:
            ans += 1
            x = t - 1/2
    return ans

n, m = map(int, input().split())
a = [0] * m
b = [0] * m
for i in range(m):
    a[i], b[i] = map(int, input().split())
print(solve(n, m, a, b))

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.sort()
answer = 0
last = 0
for b, a in l:
    if a >= last:
        answer += 1
        last = b
print(answer)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m = inpl()
ab = [inpl() for i in range(m)]

ab.sort(key=lambda x:x[1])
ab.sort()
res = 0
now = 0
l = 0
r = 0
for i in range(m):
    if ab[i][0] == now:
        continue
    if ab[i][0] >= r:
        res += 1
        r = ab[i][1]
    elif ab[i][1] < r:
        r = ab[i][1]
    l = ab[i][0]
    now = l
print(res)

Submission status: Accepted

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

l.sort(key=lambda x:x[1])
ans=0
x=0
for li in l:
    a,b=li
    if x<=a:
        x=b
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
dem=[]
ans=[]
for i in range(m):
    a,b=map(int,input().split())
    dem.append([a,b])
dem=sorted(dem,key=lambda x:x[1])  
for i in range(m):
    if len(ans)==0:
        ans.append(dem[i][1]-1)
    else:
        if ans[-1]<dem[i][0]:
            ans.append(dem[i][1]-1)  
print(len(ans))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
INF = float('INF')

n, m = map(int, input().split())
path = [INF]*(n+1)

for _ in range(m):
    a, b = map(int, input().split())
    path[a] = min(path[a], b)

left = 1
ans = 1
right = n
while left <= n:
    cut = path[left]
    if cut == INF:
        left += 1
        continue
    if right <= left:
        ans += 1
        right = n
    right = min(right, cut)
    left += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
input = sys.stdin.readline


n, m = map(int, input().split())
path = defaultdict(list)

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

idx = 1
ans = 1
right = n
while idx <= n:
    candidate = path[idx]
    if not candidate:
        idx += 1
        continue
    if right <= idx:
        ans += 1
        right = n
    cut = min(candidate)
    right = min(right, cut)
    idx += 1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# coding: utf-8

# In[ ]:





# In[1]:


import heapq


# In[2]:


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


# In[9]:


ab = []
for _ in range(M):
    a, b = map(int, input().split())
    heapq.heappush(ab, (a, b))


# In[14]:


# temp = ab.copy()
# temp
# ab = temp.copy()
# ab


# In[15]:


R = -1
count = 0
for i in range(M):
    (abl, abr) = heapq.heappop(ab)
    if R <= abl:
        # next
        count += 1
        R = abr
    elif abr < R:
        # R更新
        R = abr


# In[16]:


print(count)


# In[ ]:





# In[ ]:

Submission status: Accepted

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

last_removed = conflicts[0][1]
bridge_removed = 1

for conflict in conflicts[1:]:
    if conflict[0] < last_removed and conflict[1] >= last_removed:
        continue
    else:
        last_removed = conflict[1]
        bridge_removed += 1

print(bridge_removed)

Submission status: Accepted

Solution code:
import numpy as np
N, M=map(int, input().split())
ab=np.array([list(map(int, input().split())) for i in range(M)])
ab-=1
ab=ab[np.argsort(ab[:, 1]), :]

counter=1
x=ab[0, 1]
for i in range(1, M):
  if ab[i, 0]<x:
    pass
  else:
    counter+=1
    x=ab[i, 1]
    
print(counter)

Submission status: Accepted

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

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

ans = 0
right = -1

for a, b in wars:
    if a >= right:
        ans += 1
        right = b
    else:
        right = min(right, b)

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int, input().split())
r_table = [-1]*N
for _ in range(M):
    l_n, r_n = map(int, input().split())
    r_table[r_n-1] = max(l_n-1, r_table[r_n-1])

ret = 0
left = -1
for i in range(N):
    if left < r_table[i]:
        ret += 1
        left = i-1

print(ret)

Submission status: Accepted

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

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


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
def examD():
    N, M = LI()
    right = defaultdict(int)
    for _ in range(M):
        a, b = LI()
        right[b] = max(right[b],a)
    ans = 0; cur = 0
    for i in range(1,N+1):
        if right[i]>cur:
            ans +=1
            cur = i-1
    print(ans)

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Submission status: Accepted

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

    sort_A = sorted(A)
    left = 0
    right = N
    cnt = 1
    for i in range(M):
        left = max(sort_A[i][0],left)
        right = min(sort_A[i][1], right)
        if left >= right:
            cnt += 1
            right = sort_A[i][1]

    print(cnt)


    



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(m)]
ab.sort(key=lambda x:x[1])
x=0
ans=0
for i in range(m):
    a,b=ab[i][0],ab[i][1]
    if a>x:
        x=b-1
        ans+=1
    else:
        continue
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
AB=[list(map(int,input().split())) for _ in [0]*m]
AB.sort(key=lambda x:x[1])
l=-1
ans=0
for i in range(m):
    if AB[i][0]>l:
        ans+=1
        l=AB[i][1]-1

print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
n, m = map(int, input().split())
ab = sorted([ list(map(int, input().split())) for _ in range(m)], key=itemgetter(1) )
x = 0
ans = 0
for a, b in ab:
  if a > x:
    ans += 1
    x = b-1
print(ans)

Submission status: Accepted

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

res = 0
i = 1
for m in range(M):
    if req[m][0] >= i:
        i = req[m][1]
        res += 1

print(res)

Submission status: Accepted

Solution code:



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

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

l,r = 1,N

ans = 1
for a,b in AB:

    if r <= a:
        ans += 1
        l,r = a,b
    else:
        l = max(l,a)
        r = min(r,b)

print(ans)

Submission status: Accepted

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

ans = 0
L,R = 0,n
for a,b in ab:
    if b <= L or a >= R:
        ans += 1
        L,R = a,b
        continue
    L = max(L,a)
    R = min(R,b)
    # print(L,R)
print(ans+1)

Submission status: Accepted

Solution code:
from operator import itemgetter
n,m=map(int,input().split())
a=[]
b=[]
for i in range(m):
    a_,b_=map(int,input().split())
    a.append(a_)
    b.append(b_)
ab=sorted([(a[i],b[i]) for i in range(m)],  key=itemgetter(1))  
removed=-1
ans=0

for i,j in ab:
    if i>removed:
        ans+=1
        removed=j-1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
a = [tuple(map(int, input().split())) for i in range(M)]
a.sort(key=lambda x:x[1])
divided = [0 for i in range(N-1)]

p = 0
for i in a:
    # 分断済みなら次の関係へ
    if p >= i[0]:
        continue
    
    # 分断
    p = i[1]-1
    divided[p -2]=1
    
print(sum(divided))

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

Submission status: Accepted

Solution code:
# ABC103D
# 貪欲法：区間スケジューリング問題に帰着
# ソートして喧嘩している遠い島(b[i])の最も近いところから貪欲に選んでいく
# ex) 1-10, 2-5, 6-8
# なら2-5, 6-8を選ぶ．
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
ab.sort(key=lambda x: x[1])
##print(ab)
ans = 1             # 一つ目分
tmp = ab[0][1] - 0.1      # 一つ目の橋は必ず壊すので
for i in range(1, M):
    if ab[i][0] < tmp < ab[i][1]:   # 直近で壊した橋が喧嘩している島の間にある時は何もしない
        pass
    else:                           # 間にない時は新しく橋を壊す
        ans += 1
        tmp = ab[i][1] - 0.1

print(ans)

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter
sys.setrecursionlimit(10**6)
def MAP(): return [int(s) for s in input().split()]

if sys.platform =='darwin':
	sys.stdin=open('input.txt')
input = sys.stdin.readline

N, M = MAP()
W = [MAP() for _ in range(M)]
W.sort()

low = W[0][0]
high = W[0][1]
cnt = 1

for i in range(1,M):
	low = max(low, W[i][0])
	high = min(high, W[i][1])
	if low < high:
		continue
	else:
		cnt += 1
		low = W[i][0]
		high = W[i][1]

print(cnt)

Submission status: Accepted

Solution code:
def main():
    N, M = (int(i) for i in input().split())
    ab = [tuple(int(i) for i in input().split()) for _ in range(M)]
    ab.sort(key=lambda p: p[1])

    pre_b = 1
    ans = 0
    for a, b in ab:
        if pre_b <= a:
            ans += 1
            pre_b = b
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

ans=0
removed=-1
for i in range(M):
  if A[i][0] > removed:
    ans+=1
    removed=A[i][1]-1
print(ans)

Submission status: Accepted

Solution code:
def main():

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

    ans = 0
    rel.sort()
    a, b = rel[0]
    ans = 1
    for i in range(1, M):
        c, d = rel[i]
        if c < b:
            a = c
            b = min(b, d)
        else:
            ans += 1
            a, b = c, d
    return ans

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

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]
count = 0
current_bridge = float('inf')
AB.sort(key=lambda x:-x[0])

for a,b in AB:
    #print(count,a,b,current_bridge)
    if b < current_bridge:
        count += 1
        current_bridge = a + 0.5
print(count)

Submission status: Accepted

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

wars=[None]*M
for i in range(M):
  a,b=map(int,input().split())
  wars[i]=a-1,b-1

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

ans=0
cut=-1
for i in range(len(wars)):
  a,b=wars[i]
  if a>cut:
    cut=b-1
    ans+=1

print(ans)

Submission status: Accepted

Solution code:
import operator

n, m = map(int, input().split())
bridges = [0]
ms1 = (tuple(map(int, input().split())) for i in range(m))
ms2 = sorted(ms1, key=operator.itemgetter(1))

for i in range(m):
    if ms2[i][0] <= bridges[-1]:
        pass
    else:
        bridges.append(ms2[i][1] - 1)

if __name__ == "__main__":
    print(len(bridges)-1)    # 0 の分を除く

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
li = []
cnt = 0
for i in range(m):
    a,b = map(int,input().split())
    li.append((a,b))
li = sorted(li,key = lambda x:x[1])
prev = -1
for x in li:
    if(prev > x[0]):
        continue
    else:
        cnt += 1
    prev = x[1]
print(cnt)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc103/tasks/abc103_d

# ToDo not yet

# biについて昇順にソートする
# それぞれのbiについて、
# 1: すでに分断されているなら何もしない
# 2: 分断されていないならbi - 1番目の橋を切断する

N, M = map(int, input().split())
demand_list = []
for _ in range(M):
    ai, bi = map(int, input().split())
    demand_list.append([ai, bi])

# ソート
demands = sorted(demand_list, key=lambda d: d[1])

# 分断開始 切断されている橋は1で表現される
# cut_bilagge_list = [0 for _ in range(N)]
cnt = 0
cut_max_len = -1

for demand in demands:
    a, b = demand
    # すでに分断されているのかをチェックする
    if a < cut_max_len:
        continue
    # if len([1 for i in cut_bilagge_list[demand[0] - 1:demand[1] - 1] if i == 1]) > 0:
    #     continue

    # 分断されていないので bi - 2の橋を切断する
    # cut_bilagge_list[demand[1] - 2] = 1
    cut_max_len = b
    cnt += 1

# print(sum(1 for bilagge in cut_bilagge_list if bilagge == 1))
print(cnt)

Submission status: Accepted

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

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

cnt = 0
for itr, ab in enumerate(sAB):
  a, b = ab
  if itr == 0:
    x = b -1
    cnt += 1
  else:
    if a > x:
      x = b -1
      cnt += 1
print(cnt)

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

prev = -1
ans = 0
for a, b in ab:
    if a <= prev < b:
        continue
    else:
        ans += 1
        prev = b - 1

print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter

n, m = map(int, input().split())
ab = []
for _ in range(m):
    ab.append(list(map(int, input().split())))
abs = sorted(ab, key=itemgetter(1))
las = abs[0][1]
count = 1
for i in range(1, m):
    if las - 1 < abs[i][0]:
        las = abs[i][1]
        count += 1
print(count)

Submission status: Accepted

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

abl = []
for _ in range(m):
    a,b = map(int,input().split())
    abl.append((a,b))
    
abl = sorted(abl)

ans = 0
tail = 0
for a,b in abl:
    if tail <= a:
        ans += 1
        tail = b
    else:
        if b < tail:
            tail = b
            
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
import sys
def main():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    a_b = [list(map(int, input().split())) for i in range(m)]
    a_b.sort(key=itemgetter(1))
    end = a_b[0][1]-2
    ans = 1 
    for i in range(m):
        if a_b[i][0]-1 > end:
            end = a_b[i][1]-2
            ans += 1
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from operator import itemgetter
import sys
def main():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    a_b = [list(map(int, input().split())) for i in range(m)]
    a_b.sort(key=itemgetter(1))
    end = a_b[0][1]-2
    ans = 1 
    for i in range(m):
        if a_b[i][0]-1 > end:
            end = a_b[i][1]-2
            ans += 1
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from operator import itemgetter
import sys
def main():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    a_b = [list(map(int, input().split())) for i in range(m)]
    a_b.sort(key=itemgetter(1))
    end = a_b[0][1]-2
    ans = 1 
    for i in range(m):
        if a_b[i][0]-1 <= end:
            continue
        else:
            end = a_b[i][1]-2
            ans += 1
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
x=y=0
lst=sorted([list(map(int,input().split())) for i in range(m)],key=lambda x:x[1])
for a,b in lst:
  if a>x:
    y+=1
    x=b-1
print(y)

Submission status: Accepted

Solution code:
def solve(n, m, war):
    # section scheduling (greedy)
    # 0 ~ n-1
    destroyed = -1
    ans = 0
    for b, a in war:
        if destroyed < a:
            destroyed = b-1
            ans += 1

    return ans


if __name__ == '__main__':
    n, m = map(int, input().split())
    war = []
    for _ in range(m):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        war.append((b, a))
    war.sort()
    print(solve(n, m, war))

Submission status: Accepted

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

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

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

count=0
pre_pos=0
for target in l_target:
    if (target[0]<pre_pos<target[1]):
        continue
    
    count+=1
    pre_pos=target[1]-0.5

print(count)

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],x[0]))

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

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

ok = 0
ans = 0
for a, b in AB:
    if a >= ok:
        ans += 1
        ok = 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])
deleted = ab[0][1]-1
ans = 1
for a, b in ab:
    if a <= deleted < b:
        pass
    else:
        deleted = b - 1
        ans += 1

    
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

n,m = [int(x) for x in stdin.readline().rstrip().split()]
li = [list(map(int,stdin.readline().rstrip().split())) for _ in range(m)]

li.sort()

point = 1
lin = [1,n]
for i in range(m):
    lin = [max(lin[0],li[i][0]),min(lin[1],li[i][1])]
    if lin[1]-lin[0] <= 0:
        point += 1
        lin = li[i]
print(point)

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
R = sorted([tuple(map(int, input().split())) for _ in range(M)])

ir = 0
d = N+1
ans = 0
for i in range(1, N):
    while ir<len(R) and R[ir][0]<=i:
       	d = min(d, R[ir][1])
        ir+=1

    if d==i+1:
        d = N+1
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
#ABC103D - Islands War
from operator import itemgetter
n, m = list(map(int,input().split()))
#keyのitemgetterによって前と後ろどちらの数字でsortするか決まる
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)

Submission status: Accepted

Solution code:
def main():

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

    A.sort()

    a, b = A[0]
    cnt = 1
    for i in range(1, M):
        if A[i][0] <= b:
            a = A[i][0]
            b = min(b, A[i][1])
        else:
            a, b = A[i]
            cnt += 1
    return cnt

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
c = [list(map(int, input().split())) for i in range(M)]
c.sort()
r = 0
bridge = N
for i in range(M):
  a, b = c[M-1-i]
  if(a > bridge or bridge >= b):
    r += 1
    bridge = a
print(r)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    AB=[list(map(int,input().split())) for _ in range(m)]
    AB.sort(lambda x:(x[1],x[0]))
    cnt=0
    L,R=AB[0]
    for a,b in AB:
        L=max(L,a)
        if(L>=R):
            cnt+=1
            L=a
            R=b
    print(cnt+1)
resolve()

Submission status: Accepted

Solution code:
# islands war
n,m=map(int,input().split())
lists=[]
for i in range(m):
    a,b=map(int,input().split())
    lists.append((a,b))
lists=sorted(lists,key=lambda x:(x[0],x[1]))

Uselist=[0 for i in range(n)]
for j in lists:
    if not Uselist[j[0]]:
        Uselist[j[0]]=j
    else:
        continue

uselist=[]
for j in Uselist:
    if j!=0:
        uselist.append(j)
counter=0
inf=0
maxi=10**15
length=len(uselist)
for j in range(length):
    inf=max(inf,uselist[j][0])
    maxi=min(maxi,uselist[j][1])
    if inf<maxi:
        pass
    elif inf>=maxi:
        counter+=1
        inf=maxi
        maxi=uselist[j][1]
print(counter+1)

Submission status: Accepted

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

c,e=0,0
for i in range(m):
  if d[i][0]>e:
    e=d[i][1]-1
    c+=1

print(c)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab_lis = []
for i in range(m):
    ab_lis.append(list(map(int, input().split())))
ab_lis_s = sorted(ab_lis, key = lambda x: x[1])
cnt = 0
endtime = 0
for i in range(m):
    if ab_lis_s[i][0] >= endtime:
        endtime = ab_lis_s[i][1]
        cnt += 1
print(cnt)

Submission status: Accepted

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

'''
tmp_list = [sections[0]]
for i in range(1,len(sections)):
    for j in range(i):
        if sections[i] < tmp_list[j]:
            tmp_list.insert(j,sections[i])
            break
        if j == i -1:
            tmp_list.append(sections[i])
'''
min_end = 10000000000000000
sorted_list = sorted(sections)
cnt = 0
for section in sorted_list:
    if min_end <= section[0]:
        cnt += 1
        min_end = min_end = 10000000000000000
    min_end = min(min_end,section[1])
cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
from operator import itemgetter
bridges = []
for i in range(M):
    bridges.append(list(map(int, input().split())))
bridges.sort(key=itemgetter(1))
b_right = 0
cnt = 0
for a,b in bridges:
    if a > b_right:
        b_right = b - 1
        cnt += 1
print(cnt)

Submission status: Accepted

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

a = -1
ans = 0
for l, r in X:
    if l >= a:
        a = r
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def main():
    n,m = map(int,input().split())
    ab=[]
    for _ in range(m):
        ab.append(list(map(int,input().split())))
    ab.sort()
    Right=ab[0][1]
    cnt=1
    for i in range(m):
        if ab[i][1]<Right:
            Right=ab[i][1]
        if Right<=ab[i][0]:
            cnt+=1
            Right=ab[i][1]
    print(cnt)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[]
for i in range(m):
    l.append(list(map(int,input().split())))
l.sort()
s=l[0][1]
ans=1
for i in range(1,m):
    if l[i][0]>=s:
        ans+=1
        s=l[i][1]
    if l[i][1]<=s:
        s=l[i][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()

ar=N+1
ans=0
for i in reversed(range(M)):
  a,b=AB[i]
  if b<=ar:
    ans+=1
    ar=a
  
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
n,m=map(lambda x: int(x), input().split())
start=[]
end=[]
for i in range(m):
    a,b=map(lambda x: int(x), input().split())
    start.append(a)
    end.append(b)
start=np.array(start)
end=np.array(end)
ans=0
while len(start):
    ans+=1
    idx1=(end==end.min()) ## 終点が最小
    idx2=(start<end.min()) ## idx1で分断される組み合わせ
    idx3=np.logical_or(idx1, idx2)
    idx4=np.logical_not(idx3) ## 残る組み合わせ
    start=start[idx4]
    end=end[idx4]
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
points=[]
for i in range(m):
    a,b=map(int,input().split())
    points.append([a,b-1])
points = sorted(points)
arrow = float('-inf')
res = 0
#print(points)
for l,r in points:
    if l > arrow:
        res += 1
        arrow = r
    elif r < arrow:
        arrow = r
print(res)

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:
import sys
from operator import itemgetter
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, M = map(int, readline().split())
ab = map(int, read().split())
ab = sorted(zip(ab, ab), key=itemgetter(1))

right_island = ab[0][1]
answer = 1

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

print(answer)

Submission status: Accepted

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

N, M = map(int, readline().split())
ab = [tuple(map(int, i.split())) for i in readlines()]

ab.sort(key=itemgetter(1))
right_island = ab[0][1]
answer = 1

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

print(answer)

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))
count = 0
R = 0
for a, b in ab:
     if a >= R:
            count += 1
            R = b
print(count)

Submission status: Accepted

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

AB.sort(reverse=1)

res_L = float('inf')
ans = 0
for a,b in AB:
	cur_R = b
	if cur_R <= res_L:
		res_L = a
		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([a,b])
war.sort()
ans = 1
min_right = war[0][1]
max_left = war[0][0]
for i in range(0,m - 1):
    now_left, now_right = war[i][0], war[i][1]
    next_left , next_right = war[i + 1][0] , war[i + 1][1]
    min_right = min(min_right , next_right)
    max_left = max(max_left,next_left)
    if max_left >= min_right:
        ans += 1
        min_right = next_right
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a_and_b_list = [list(map(int, input().split())) for _ in range(m)]
bridge_broken = [False for _ in range(n-1)]
a_and_b_list.sort(key=lambda x: x[1])
previous_broken_bridge = -1
for a_and_b in a_and_b_list:
    if previous_broken_bridge < a_and_b[0]:
        bridge_broken[a_and_b[1]-2] = True
        previous_broken_bridge = a_and_b[1] - 1
print(bridge_broken.count(True))

Submission status: Accepted

Solution code:
from operator import itemgetter

N,M = map(int,input().split())
AB = sorted([list(map(int,input().split())) for _ in range(M)],key=itemgetter(1))
x, ans = AB[0][1],1
for a,b in AB:
  if a>=x:
    x = b
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(m)]
ab.sort()
inf=float("inf")
t=inf
count=0
for i in range(m):
    a,b=ab[i]
    if a<t:
        t=min(t,b)
    else:
        count+=1
        t=b
count+=1
print(count)

Submission status: Accepted

Solution code:
from operator import itemgetter

n,m=map(int,input().split())
l=sorted([list(map(int,input().split())) for i in range(m)],key=itemgetter(1))
x,cnt=l[0][1],1
for i in l:
    a=i[0]
    b=i[1]
    if a>=x:
        cnt+=1
        x=b
print(cnt)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
for i in l:
    i[0],i[1]=i[1],i[0]
ll=sorted(l)
x,cnt=ll[0][0],1
for i in ll:
    a=i[1]
    b=i[0]
    if a>=x:
        cnt+=1
        x=b
print(cnt)

Submission status: Accepted

Solution code:
from sys import stdin

N, M = [int(x) for x in stdin.readline().rstrip().split()]
D = [[int(x) for x in stdin.readline().rstrip().split()] for _ in range(M)]
for d in D:
    if d[0] > d[1]:
        d[0], d[1] = d[1], d[0]

D.sort(key=lambda x: (x[0], x[1]))
left = -1
right = N
ans = 0

for d in D:
    left = max(d[0], left)
    right = min(d[1], right)
    if left >= right:
        ans += 1
        left = d[0]
        right = d[1]

print(ans + 1)