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:
from operator import itemgetter
N,M=map(int,input().split())
islands=[list(map(int,input().split())) for _ in range(M)]
islands.sort(key=itemgetter(1))

i=0
cnt=0
while i<M:
    j=0
    while i+j<M and islands[i+j][0]<islands[i][1]:
        j+=1
    i+=j
    cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, M = LI()
    ab = [LI_() for _ in range(M)]
    ab.sort(key=lambda x: x[1])

    # 区間スケジューリング
    ans = 0
    # print(ab)
    right = -1
    for a, b in ab:
        if right <= a:
            right = b
            ans += 1

    print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
p=[]
for _ in range(m):
  a,b=map(int,input().split())
  p.append([a,b])
#print(p)
p.sort(key=lambda x:x[1])
#print(p)
ans=0
cur=0
for i in range(m):
  if cur<=p[i][0]:
    #print("i:%d残す,cur:%d,p[i][1]:%d,p[i][0]:%d" % (i,cur,p[i][1],p[i][0]))
    ans+=1
    cur=p[i][1]
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
table = []
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    table.append((a,b))
table = sorted(table,key=lambda x:x[1])
cur_r = table[0][1]
ans = 1
for i in range(1,M):
    l,r = table[i]
    if cur_r <= l:
        ans += 1
        cur_r = r

print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter

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

# 区間の終端でソート
ab = sorted([tuple(map(int, input().split())) for i in range(m)], key=itemgetter(1))
# 前回除いた橋
removed = -1
ans = 0

for a, b in ab:
    # a が removed より大きい = まだ取り除いてない
    if a > removed:
        removed = b - 1
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# 初期入力
import sys
input = sys.stdin.readline  #文字列では使わない

N,M = map(int, input().split())
ans =1
ab =[0]*M
for i in range(M):
    a,b = map(int, input().split()) #争いのある部分
    ab[i] =(a,b)

#abをbでソート
ab.sort(key=lambda x: x[1],reverse=True)
max_a =ab[0][0]
for a,b in ab:
    if max_a < b:
        max_a =max(max_a,a)
        continue
    else:
        max_a =a
        ans +=1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
B = [0] * M
for i in range(M):
  B[i] = list(map(int, input().split()))
  
B = sorted(B, key = lambda x:x[1])
remove = []
#print(B)
for i in range(M):
  a, b = B[i][0], B[i][1]
  if remove == []:
    remove.append(b - 1)
  elif max(remove) >= a:
    continue
  else:
    remove.append(b - 1)
  #print(remove)  
print(len(remove))

Submission status: Accepted

Solution code:
# atcoder -take a rest-(easy)
#typical greedy
def main():
    N, M = map(int, input().split())
    conflict = [tuple(map(int, input().split())) for i in range(M)]
    newest_destroyed = -1
    conflict.sort(key=lambda x: x[1])
    res = 0
    for l, r in conflict:
        if not (l <= newest_destroyed < r):
            res += 1
            newest_destroyed = r-1
    print(res)
    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# atcoder -take a rest-(easy)

def main():
    N, M = map(int, input().split())
    conflict = [tuple(map(int, input().split())) for i in range(M)]
    newest_destroyed = -1
    conflict.sort(key=lambda x: x[1])
    res = 0
    for l, r in conflict:
        if not (l <= newest_destroyed < r):
            res += 1
            newest_destroyed = r-1
    print(res)
    return


if __name__ == "__main__":
    main()

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

def main():
    n, m = map(int, input().split())
    
    ab = [0] * m
    for ind in range(m):
        i, j = map(int, input().split())
        ab[ind] = (i-1, j-1)
    
    ab.sort()

    ans = 1
    right = ab[0][1]
    for ind in range(1, m):
        # ab[ind] ∩ a[ind-1] = Φ
        if right <= ab[ind][0]:
            ans += 1
            right = ab[ind][1]

        # ab[ind] ⊆ ab[ind-1]
        elif ab[ind][1] < right:
                right = ab[ind][1]
        
        # else:
            # pass
    
    print(ans)

main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = map(int, input().strip().split())
ab_list = [list(map(int, input().strip().split())) for _ in range(m)]
ab_list.sort(key=lambda x: x[1])

res = 0
min_r = 0
for ab in ab_list:
    if min_r <= ab[0]:
        res += 1
        min_r = ab[1]
print(res)

Submission status: Accepted

Solution code:
N,M=list(map(int,input().split()))
ans=0
l=[]
for i in range(M):
   a,b=(map(int,input().split()))
   l.append((a,b))
l.sort(key=lambda x:x[1])
cut=-1
for i,j in l:
   if cut>=i:
      continue
   else:
      ans+=1
      cut=j-1
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
ls = [tuple(map(int,input().split())) for _ in range(M)]
ls.sort(key=lambda x:x[1],reverse=True)
ls.sort(key=lambda x:x[0],reverse=True)
r = N
cnt = 0
for i in range(M):
    a,b = ls[i]
    if b <= r:
        cnt += 1
        r = a
print(cnt)

Submission status: Accepted

Solution code:
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n, m = LI()
    span = [None for _ in range(m)]
    for i in range(m):
        a, b = LI()
        span[i] = [a,b]
    span.sort(key=lambda x: x[1])
    choice = [0, 0]
    ans = 0
    for each_span in span:
        if choice[1]<=each_span[0]:
            choice = each_span
            ans += 1
    print(ans)
main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
W = sorted([list(map(int,input().split())) for m in range(M)],key=lambda x:x[1])
c = 0
x = 0

for a,b in W:
   if x<a:
      x=b-1
      c+=1

print(c)

Submission status: Accepted

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

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 I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,m=LI()
  l=[LI() for _ in range(m)]
  l=sorted(l,key=lambda x:x[1])

  ans=1
  kiru=l[0][1]-0.1
  for x,y in l[1:]:
    if x<kiru<y:
      continue
    ans+=1
    kiru=y-0.1

  return ans

# main()
print(main())

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ans=0
head=1
from operator import itemgetter as it
for x,y in sorted([list(map(int,input().split()))for i in range(m)],reverse=0,key=lambda x:(it(1)(x)*(n+1)*10-it(0)(x))):
    if not(x<head <=y):
        head=y
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
warzones = [[] for i in range(M)]
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -=1
    warzones[i] = [a,b]
warzones = sorted(warzones,key=lambda x:x[0])
#print(warzones)
shaku = warzones[0]
cnt = 1
for i in range(1,M):
    #print(shaku)
    #尺継続条件
    if(warzones[i][0] < shaku[1]):
        shaku[0] = max(warzones[i][0],shaku[0])
        shaku[1] = min(warzones[i][1],shaku[1])
    else:
        cnt += 1
        shaku = warzones[i]

print(cnt)

'''尺取法の初期化
最初に配列のlists[0]で初期化
for i in range(1,M):でまわして
okの場合lists[i]を代入
ngのときはカウントを増やしてngで再初期化
'''

Submission status: Accepted

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

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

Rsort = sorted(AB, key=lambda x: x[1])
cnt = 0
R = 0

for a, b in Rsort:
  if a <= R:
    continue
  else:
    cnt += 1
    R = b-1

print(cnt)

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
ab = [list(map(int, input().split())) for i in range(m)]
ab.sort()
ans = 0
now = 1
for i in range(m):
	if now <= ab[i][0]:
		ans += 1
		now = ab[i][1]
	now = min(now, ab[i][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])
ans = 0
s = 0 #最新の切断点
for i in range(M):
    a, b = ab[i]
    if a >= s: # aを今の最新の切断点で対処できないなら、
        #そのaに対するb(これは必ず対処できる)で切る
        s = b
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m  = map(int, input().split())
a = [list(map(int, input().split())) for i in range(m)]
a = sorted(a, key=lambda x :x[1])
bridge = a[0][1] - 1
ans = 1

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

Submission status: Accepted

Solution code:
import sys


def main():
    input = sys.stdin.buffer.readline
    n, m = map(int, input().split())
    demand = [tuple(map(int, input().split())) for _ in range(m)]
    demand.sort(key=lambda x: x[1])
    prev_cut = 0
    ans = 0
    for a, b in demand:
        if prev_cut < a:
            ans += 1
            prev_cut = b - 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from operator import itemgetter

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

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

# 前回除いた橋
removed = -1
ans = 0

for a, b in ab:
    # a が removed より大きい = まだ取り除いてない
    if a > removed:
        removed = b - 1
        ans += 1

print(ans)

Submission status: Accepted

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

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

ans = 0
current = 0
for a, b in instructions:
    if current < a: #過去の条件ではまだ満たしてない
        current = b-1
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
n,m = map(int,input().split())
lis = []
for _ in range(m):
    lis.append(list(map(int,input().split())))
lis.sort(key = itemgetter(1))
ans = 0
last = 0
for i in range(m):
    if last <= lis[i][0]:
        ans += 1
        last = lis[i][1]
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 = sorted(l, key = lambda x:(x[1], x[0]))
cnt = m
 
for i in range(1, m):
    if l[i-1][1] > l[i][0]:
        l[i][1] = l[i-1][1]
        cnt -= 1
 
print(cnt)

Submission status: Accepted

Solution code:

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

l = sorted(l, key = lambda x:(x[1], x[0]))
cnt = 0
con_l = 0

for i in range(m):
    if con_l <= l[i][0]:
        cnt += 1
        con_l = l[i][1]

print(cnt)

Submission status: Accepted

Solution code:
n_node, Q = map(int,input().split())
Q_ls = [[0,0] for _ in range(Q)]
for i in range(Q):
    a,b = map(int,input().split())
    Q_ls[i] = [a-1,b-1]
Q_ls.sort(key=lambda x: x[1])

last_r = -1
ans = 0
for i in range(Q):
    if Q_ls[i][1] > last_r and Q_ls[i][0] >= last_r:
        ans += 1
        last_r = Q_ls[i][1]
print(ans)

Submission status: Accepted

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

# bについて昇順ソート
ab_list.sort(key=lambda x: x[1])

ans = 0

# 直前に切断した橋のindex
# 0や適当な負の値で初期化しておくと1回目の判定で都合が良い
pre_x = 0

for a, b in ab_list:
    # 直前の切断で条件が満たせる場合
    if pre_x >= a:
        continue
    # 新たに切断する必要がある場合
    else:
        pre_x = b - 1
        ans += 1
print(ans)

Submission status: Accepted

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

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

ans = 0
pre_x = -1
for a, b in ab_list:
    # 直前の切断で条件が満たせる場合
    if pre_x >= a:
        continue
    # 新たに切断する必要がある場合
    else:
        pre_x = b - 1
        ans += 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 = sorted(ab, key=lambda x: x[1])
s = ab[0][1]
ans = 1
for i in ab:
    if s <= i[0]:
        ans += 1
        s = i[1]
print(ans)

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 = sorted(ab, key=itemgetter(1))

# 前回取り除いた橋
removed = -1
ans = 0

for a, b in ab:
    # a が removed より大きい = まだ取り除いていない
    if a > removed:
        removed = b - 1
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
def Schedule(schedule):
    """
    :return: 複数の区間が与えられた時の重複の無い区間の選び方の最大数
    """
    schedule = sorted(schedule, key=lambda x: x[1])
    N = len(schedule)
    res = 0
    end = -float("inf")

    for i in range(N):
        if end <= schedule[i][0]:  # 重複がダメならば等号を消す
            end = schedule[i][1]  # 終点でソートされているので、自動的に可能な中で最速の終点が選ばれている
            res += 1
    return res

################################################################################

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
schedule = []
for i in range(M):
    start, end = map(int, input().split())
    schedule.append((start, end))               # schedule = (始点、終点)

print(Schedule(schedule))

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
ab = [tuple(map(int, input().split())) for _ in range(m)]
from heapq import heappop as hpp, heappush as hp
h = []
for i,(a,b) in enumerate(ab):
    hp(h, (a,i,0))
ans = 0
m = -1
while h:
    val,ind,c = hpp(h)
    if c==0:
        hp(h, (ab[ind][1],ind,1))
    else:
        if m>=0 and ab[ind][0]<=m<val:
            pass
        else:
            m = ab[ind][1]-1
            ans += 1
#             print(val,ind,c)
print(ans)

Submission status: Accepted

Solution code:
# ABC 103 D - Islands War
f=lambda:map(int,input().split())
N,M=f()
wars=[]
for i in range(M):
    l,r=f()
    wars.append((r,l))
wars.sort()

res=M
r,l=wars.pop(0)
for nr,nl in wars:
    if nl<r:
        res-=1
    else:
        r=nr
print(res)

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    X = []
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        X.append([a,b])
    
    X.sort(key=lambda x: x[1])
    cnt = 1
    now = X[0][1]
    for a, b in X:
        if now <= a:
            cnt += 1
            now = b

    print(cnt)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    AB = [None] * M
    for i in range(M):
        AB[i] = tuple(map(int, input().split()))

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

    ans = 0
    prev_x = -1
    for a, b in AB:
        if a <= prev_x < b:
            pass
        else:
            ans += 1
            prev_x = b - 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

right_end = 0
ans = 0
for c in condition:
    if c[0] >= right_end:
        ans += 1
        right_end = c[1]
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab = sorted([tuple(map(int, input().split())) for _ in range(m)], key = lambda x:x[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:
N, M = map(int, input().split())
AB = sorted([list(map(int, input().split())) for _ in range(M)])

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

last_b = AB[0][1] - 1  # 最初に潰す橋
cnt = 1  # 上で一つ壊してるので+1
for a, b in AB:
    if a <= last_b:
        continue
    else:
        last_b = b - 1
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N, M = map(int, input().split())
items = [list(map(int, input().split())) for i in range(M)]
items = sorted(items, key=lambda x: x[1])
last = 0
res = 0
for a, b in items:
    if last <= a:
        res += 1
        last = b
print(res)

Submission status: Accepted

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

ls = []
for i in range(m):
    x,l = map(int,input().split())
    ls.append([x,l])
    
ls = sorted(ls, key=lambda x: x[1])
ans =m
for i in range(1,m):
    if ls[i][0] < ls[i-1][1]:
      ls[i][1] = ls[i-1][1]
      ans -=1
        
print(ans)

Submission status: Accepted

Solution code:
_,*l = [list(map(int,i.split())) for i in open(0)]
l.sort(key=lambda x:x[1])
A=S=0
for s,t in l:
    if S<=s:
        A+=1
        S=t
print(A)

Submission status: Accepted

Solution code:
_,*li = [list(map(int,i.split())) for i in open(0)]
li.sort(key=lambda x:x[1])
A = 0
S = 0
for s,t in li:
    if S<=s:
        A+=1
        S=t
print(A)

Submission status: Accepted

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

N,M=map(int,input().split())
#- 1要望 a→c,b→c分断要望に対して、a<bならb→cだけ考慮すればいい -#
want_list = [0]*(N+1)
for _ in range(M):
    a,b = map(int,input().split())
    want_list[b]=max(want_list[b],a)


#-分断した時の橋とindexと要望を見比べて、要望を満たしていないならカウントする-#
cnt = 0
cutNo = 0
for idx,val in enumerate(want_list):
    if val >cutNo:
        cutNo = idx-1
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

N,M=list(map(int,input().split()))
#- 1要望 a→c,b→c分断要望に対して、a<bならb→cだけ考慮すればいい -#
want_list = [0]*(N+1)
for _ in range(M):
    a,b = map(int,input().split())
    want_list[b]=max(want_list[b],a)


#-分断した時の橋とindexと要望を見比べて、要望を満たしていないならカウントする-#
cnt = 0
cutNo = 0
for idx,val in enumerate(want_list):
    if val >cutNo:
        cutNo = idx-1
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import sys
import math
import itertools
import collections
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    N, M = NMI()
    ab = [NLI() for _ in range(M)]
    
    ENDsorted_sections= sorted(ab, key=lambda x: x[1])
    
    ans = 1
    dropped_bridge = ENDsorted_sections[0][1]

    for m in range(M):
        if ENDsorted_sections[m][0] >= dropped_bridge:#新しく橋を落とさないといけない
            ans += 1
            dropped_bridge = ENDsorted_sections[m][1]
    print(ans)    

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M,*A=map(int,open(0).read().split());c=0
for a,b in sorted(zip(*[iter(A)]*2))[::-1]:
	if b<=N:c+=1;N=a
print(c)

Submission status: Accepted

Solution code:
N, M, *A = map(int, open(0).read().split())
*A, = zip(*[iter(A)]*2)
A.sort()
cnt = 0
R = 0
for a, b in A:
    if R <= a:
        cnt += 1
        R = b
    elif b < R:
        R = b
print(cnt)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ba = []
for i in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    ba.append((b,a))
ba.sort()
count = 0
prev_b = -1
for b, a in ba:
    if a < prev_b:
        continue
    prev_b = b
    count += 1
print(count)

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter

read = sys.stdin.buffer.read
INF = 1 << 60


def main():
    N, M, *AB = map(int, read().split())

    Q = list(zip(*[iter(AB)] * 2))
    Q.sort(key=itemgetter(1))

    ans = 0
    last = 0
    for a, b in Q:
        if last < a:
            last = b - 1
            ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter

read = sys.stdin.buffer.read
INF = 1 << 60


def main():
    N, M, *AB = map(int, read().split())

    Q = [0] * M
    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
        Q[i] = (a - 1, b - 1)

    Q.sort(key=itemgetter(1))

    ans = 0
    last = -1
    for a, b in Q:
        if last < a:
            last = b - 1
            ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
INF = 1 << 60


def main():
    N, M, *AB = map(int, read().split())

    Q = [[] for _ in range(N - 1)]
    for a, b in zip(*[iter(AB)] * 2):
        Q[a - 1].append(b - 2)

    min_y = INF
    ans = 0
    for i, ys in enumerate(Q):
        if ys:
            min_y = min(min_y, min(ys))
        if i == min_y:
            ans += 1
            min_y = INF

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *AB = map(int, read().split())

    Q = [[] for _ in range(N - 1)]
    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
        Q[a - 1].append(b - 2)

    min_y = INF
    ans = 0
    for i, ys in enumerate(Q):
        if ys:
            min_y = min(min_y, min(ys))
        if i == min_y:
            ans += 1
            min_y = INF

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
'''
自宅用PCでの解答
'''
import math
#import numpy as np
import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

class Binary_Indexed_Tree:
    #Binary_Indexed_Tree
    #A1 ... AnのBIT(1-indexed)
    def __init__(self,n):
        self.N = n
        self.BIT = [0]*(n+1)
        self.l2 = 2**(len(format(n,'b'))-1)

    #A1 ~ Aiまでの和 O(logN)
    def query(self,idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def update(self,idx,x):
        while idx <= self.N:
            self.BIT[idx] += x
            idx += idx&(-idx)
        return

    def lower_bound(self,w):
        if w <= 0:
            return 0
        x = 0
        k = self.l2
        while k > 0:
            if x+k <= self.N and self.BIT[x+k] < w:
                w -= self.BIT[x+k]
                x += k
            k //= 2
        return x+1

    def upper_bound(self,w):
        x = 0
        k = self.l2
        while k > 0:
            if x+k <= self.N and self.BIT[x+k] <= w:
                w -= self.BIT[x+k]
                x += k
            k //= 2
        return x


def main():
    n,m = map(int,ipt().split())
    nms = []
    for i in range(m):
        a,b = map(int,ipt().split())
        nms.append(b*(10**6)+a)
    nms.sort()

    ans = 0
    bt = Binary_Indexed_Tree(n)

    for i in nms:
        a = i%(10**6)
        b = i//(10**6)
        if bt.query(b)-bt.query(a):
            continue
        else:
            bt.update(b,1)
            ans += 1

    print(ans)



    return None

if __name__ == '__main__':
    main()

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])  # Sort the list of (a, b) by b

ans = 0
cur = -1
for i in range(M):
    a, b = ab[i]
    if a < cur:
        continue
    ans += 1
    cur = b

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

cd = sorted(ab, key=itemgetter(1))
#print(cd)
removed = -1
ans = 0

for a, b in cd:
  if a > removed:
    removed = b - 1
    ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter

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

b = sorted(a, key=itemgetter(1))
#print(b)
removed = -1
ans = 0

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

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
lis = [[] for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    lis[a].append(i+1)
    lis[b].append(-(i+1))
for i in range(N):
    lis[i].sort()

ans = 0
d = set()
for i in range(N):
    for j in range(len(lis[i])):
        if lis[i][j] < 0:
            if -lis[i][j] in d:
                d = set()
                ans += 1
        else:
            d.add(lis[i][j])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

count = 1
left = data[0][1]
for i in range(1, M):
    if data[i][0] < left:
        left = max(data[i][0], left)
    else:
        count += 1
        left = data[i][1]
print(count)

Submission status: Accepted

Solution code:
import sys
import math
import collections
import bisect
import copy

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, m = ns()
    d = []
    for _ in range(m):
        a, b = ns()
        d.append([a - 1, b - 1])

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

    down = -1
    ans = 0
    for a, b in d:
        if down < a:
            down = b-1
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math
import collections
import bisect
import copy

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))


# ===CODE===


def main():
    n, m = ns()
    d = []
    for _ in range(m):
        a, b = ns()
        d.append([a - 1, b - 1])

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

    down = []

    for a, b in d:
        idx = bisect.bisect_left(down, a)
        if idx == len(down):
            down.append(b - 1)
    print(len(down))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect
N, M, *AB = [int(_) for _ in open(0).read().split()]
AB = sorted(zip(AB[::2], AB[1::2]))
l, r = AB[0]
ans = 1
for a, b in AB[1:]:
    if r <= a:
        l, r = a, b
        ans += 1
    else:
        r = min(r, b)
print(ans)

Submission status: Accepted

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

A=sorted(A, key=lambda x:x[1])
ans=0
last=-5000
for l in A:
    #print(a,b)
    if last<l[0]:
        ans+=1
        last=l[1]-1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
itv=[]
for i in range(m):
  a,b=map(int,input().split())
  itv+=[(b,a)]
itv=sorted(itv)
cnt=0
l=1
for t,s in itv:
  if l<=s:
    l=t
    cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
from sys import maxsize
N, M = map(int, input().split())
bridges = []
for i in range(M):
    a, b = map(int, input().split())
    bridges.append((a, b))

res = 0
end = -maxsize

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

for bridge in bridges:
    if end <= bridge[0]:
        res += 1
        end = bridge[1]
print(res)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N, M = map(int, input().split(' '))

a_b_pairs = [list(map(int, input().split(' '))) for _ in range(M)]
a_b_pairs.sort(key=lambda x: x[1])
right = a_b_pairs[0][1] - 1

ans = 1
for a, b in a_b_pairs[1:]:
    if a > right:
        right = b - 1
        ans += 1

print(ans)