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:
n, m = map(int, input().split())
bri_list=[0]
s = [[]]*m
for i in range(m):
    s[i] = list(map(int, input().split()))
s.sort(key=lambda x :x[1])

for i in range(m):
    if s[i][0]>bri_list[-1]:
        bri_list.append(s[i][1]-0.5)
print(len(bri_list)-1)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
l = [list(map(int,input().split())) for _ in range(M)]
l.sort(key= lambda x: x[1])
removed = 0
ans = 0
for i in l:
  s = i[1]
  if removed<i[0]:
    removed = s-1
    ans+=1

print(ans)

Submission status: Accepted

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

 
def main():
    N,M = map(int,input().split())
    ab = [list(map(int,input().split())) for _ in range(M)]
    ab.sort(key= lambda x: x[1])
    removed_bridge = 0
    answer = 0
    for aabb in ab:
        b = aabb[1]
        if removed_bridge<aabb[0]:
            removed_bridge = b-1
            answer+=1
    
    print(answer)
        



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m = LI()
    v = LIR(m)
    v.sort(key = lambda x:x[1])
    ans = 0
    r = 0
    for a,b in v:
        if r < a:
            ans += 1
            r = b-1
        else:
            continue
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
a=[tuple(map(int,input().split()))for i in range(m)]
a.sort()
l,r=0,n+1
x=1
for i,j in a:
  if j<=l or r<=i:
    x+=1
    l,r=i,j
  else:
    l,r=max(l,i),min(r,j)
print(x)

Submission status: Accepted

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

war = [10**10 for i in range(n)]


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

a = []
b = []

for ai,bi in enumerate(war):
    if bi<10**9:
        a.append(ai)
        b.append(bi)


bridge = []
i=0
l = len(a)
while i<l:#iを固定して、一緒に切るwarのうちbが最小のものがb_dum
    b_dum = b[i]
    while i+1<l and a[i+1]<b_dum:
        b_dum = min(b_dum,b[i+1])
        i+=1
    bridge.append(b_dum-1)
    i += 1    

print(len(bridge))

Submission status: Accepted

Solution code:


def resolve():
    (N,M)=map(int,input().split())
    querys=[[int(j) for j in input().split()] for i in range(M)]
    querys.sort()
    now=[querys[0][0],querys[0][1]]
    count=1

    for i in range(1,len(querys)):
        
        if querys[i][0]<now[1]:
            now[1]=min(now[1],querys[i][1])
            now[0]=querys[i][0]

        else:
            now=[querys[i][0],querys[i][1]]
            count+=1

    print(count)



if __name__ == "__main__":
    resolve()

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 = 0
m = 0
for ab in AB:
    if not ab[0] < m <= ab[1]:
        m = ab[1]
        ans += 1
print(ans)

Submission status: Accepted

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

B_A = [[] for i in range(N + 1)]
for ab in AB:
    B_A[ab[1]].append(ab[0])
for b_a in B_A:
    b_a.sort()


right = 0
ans = 0
for i in range(N + 1):
    if len(B_A[i]):
        if B_A[i][-1] > right:
            ans += 1
            right = i - 1

print(ans)

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    D = [list(map(int, input().split())) for _ in range(m)]
    D.sort()
    result = 1
    checker = D[0][1]
    for i in range(m):
        if checker <= D[i][0]:
            result += 1
            checker = D[i][1]
        elif checker > D[i][1]:
            checker = D[i][1]
    print(result)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
D = [list(map(int, input().split())) for _ in range(m)]
D.sort()
result = 1
checker = D[0][1]
for i in range(m):
    if checker <= D[i][0]:
        result += 1
        checker = D[i][1]
    elif checker > D[i][1]:
        checker = D[i][1]
print(result)

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

br = -1
for i in range(m):
    if ab[i][0] < br < ab[i][1]:
        continue
    else:
        br = ab[i][1] - 0.5
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
requests = []
for _ in range(m):
    requests.append(tuple(map(int, input().split())))
requests.sort(key=lambda x: x[1])
cutcount = 0
lastcut = 0
for request in requests:
    if request[0] >= lastcut:
        lastcut = request[1]
        cutcount += 1
print(cutcount)

Submission status: Accepted

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

banned_list = []
for i in range(M):
    banned_list.append(tuple(map(int,input().split())))
banned_list = sorted(banned_list,key=lambda x:x[1])
#status = [1 for _ in range(N-1)]
status = set()
counter = 0
for i in range(M):
    a = banned_list[i][0]
    b = banned_list[i][1]
    if len([one for one in status if (one >= a-1 and one < b-1)]) == 0:
        status  |= {b-2}
        counter += 1
print(counter)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from operator import itemgetter

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

answer = 0
x = 0
for a,b in AB:
    if a <= x:
        continue
    x=b-1
    answer += 1

print(answer)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
mp=[ tuple(map(int,input().split())) for _ in range(M)]
#ソート。O(nlogn)
mp_=sorted(mp,key=lambda x: x[1])

ans=0
cut_bridge=0
#最後に切った橋がaより大きいかどうかさえ見ればいい。
for n in range(M):
    if mp_[n][0]>cut_bridge:
        ans+=1
        cut_bridge=mp_[n][1]-1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
youbou = [list(map(int,input().split())) for i in range(m)]
youbou.sort(key = lambda x: x[1])
ans,prev = 0,-1
for i in range(m):
	if prev < youbou[i][0]:
		prev = youbou[i][1] - 1
		ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
youbou = [list(map(int,input().split())) for i in range(m)]
youbou.sort(key = lambda x: x[1])
ans,prev = 0,-1
for p in youbou:
	if prev < p[0]:
		prev = p[1] - 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])
tmp_end = ab[0][1]
n_remove_bridge = 1

for idx in range(1,M):
    if tmp_end <= ab[idx][0]:
        tmp_end = ab[idx][1]
        n_remove_bridge += 1

print(n_remove_bridge)

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 j in range(M)]

    dist = 1
    ans = 0
    ab.sort(key=lambda p: p[1])
    for a,b in ab:
        if dist <= a:
            ans += 1
            dist = b
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
l = [[0]*2 for i in range(M)]
sum = 0
for i in range(M):
    l[i][0],l[i][1] = map(int,input().split())
l.sort(key=lambda l:l[1])
x = 0
for i in range(M):
    if x<=l[i][0]:
        x=l[i][1]
        sum+=1
print(sum)

Submission status: Accepted

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

ans=0
count=0

for i in range(m):
  if count<l[i][0]:
    ans+=1
    count=l[i][1]-1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
bridges = [list(map(lambda x: int(x)-1, input().split())) for i in range(M)]
l = [None for i in range(N)]
for a, b in bridges:
  if l[b] is None:
    l[b] = a
  else:
    l[b] = max(l[b], a)

now = 0
res = 0
for dist in range(N):
  src = l[dist]
  if src is None:
    continue
  if src >= now:
    now = dist
    res += 1

print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
count = 0
s = [[]*2]*m
for i in range(0, m):
  s[i] = list(map(int, input().split()))
s.sort()
r = s[0][1] - 1
count += 1
for i in range(1, m):
  if s[i][1] - 1 < r:
    r = s[i][1] - 1
  if r < s[i][0]:
    r = s[i][1] - 1
    count += 1
print(count)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
count = 0
s = [[]*2]*m
for i in range(0, m):
  s[i] = list(map(int, input().split()))
s.sort()
r = s[0][1] - 1
count += 1
for i in range(1, m):
  if s[i][1] < r + 1:
    r = s[i][1] - 1
  if s[i][0] > r:
    r = s[i][1] - 1
    count += 1
print(count)

Submission status: Accepted

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

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:
# coding: utf-8
# 貪欲法で解く
N, M = map(int, input().split()) # N, Mの入力
ab = [list(map(int, input().split())) for i in range(M)] # ai, biをlistで管理
ans = 0 # 解答の初期化
left = 1 # 左限を定義
ab.sort(key = lambda x: x[1]) # 要望をbiの昇順で並べる
for request in ab:
    if left <= request[0]: # 左限よりもaiが大きいならば分断の必要があるので分断
        ans += 1
        left = request[1] # 左限を新たに分断後の左限にする
print(ans) # 解答の出力

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
import heapq

n, m = [ int(v) for v in input().split() ]
demand = []
for i in range(m):
    l, r = [ int(v) for v in input().split() ]
    demand.append( (r,l) )
demand.sort()

right, left = heapq.heappop(demand)
ans = 1

for i in range(m-1):
    ri, li = heapq.heappop(demand)
    if li >= right:
        ans += 1
        right = ri

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
spans = sorted([list(map(int, input().split())) for _ in range(m)], key=lambda x: x[1])
cnt = 0
x = 0

for span in spans:
    if span[0] > x:
        x = span[1] - 1
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
N, M = map(int, input().split())

ab = [[int(i) for i in input().split()] for _ in range(M)]

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

ret = 1
end = float('inf')
for a, b in ab :
    if a >= end :
        ret += 1
        end = b
    else :
        end = min(end, b)

print(ret)

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]))
end=AB[0][1]
ans=1
for a,b in AB[1:]:
  if end<=a:
    end=b
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
def run():
  N, M = map(int, input().split())
  land_li = [list(map(int, input().split())) for m in range(M)]
  sorted_li = sorted(land_li, key=lambda x:(x[1], x[0]))
  #print(sorted_li)
  end = sorted_li[0][1]
  num = 1
  for batle_li in sorted_li[1:]:
    if end <= batle_li[0]:
      end = batle_li[1]
      num += 1
  print(num)
  
if __name__ == '__main__':
  run()

Submission status: Accepted

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

bridge = [1]*(n-1)
x = -1
for a_b in ab:
  if a_b[0] <= x:
    pass
  else:
    x = a_b[1]-1
    bridge[x-1]=0

print(bridge.count(0))

Submission status: Accepted

Solution code:
def log(s):
    # print("| " + str(s), file=sys.stderr)
    pass


def output(x):
    print(x, flush=True)


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


def main():
    num_nodes, num_regions = tuple(input_ints())
    regions = [tuple(input_ints()) for _ in range(num_regions)]
    regions.sort(key=lambda r: r[1])

    edges = []
    for r in regions:
        if not edges or edges[-1] < r[0]:
            edges.append(r[1] - 1)

    print(len(edges))


main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
C = []
for i in range(M):
    C.append(list(map(int, input().split())))
C.sort(key=lambda x:x[0])
ans = 1
l = 0
r = N-1
for c in C:
    if r<=c[0]-1 or c[1]-1<=l:
        ans += 1
        l = c[0]-1
        r = c[1]-1
        continue
    l = max(l, c[0]-1)
    r = min(r, c[1]-1)
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 _ in range(M)], key=itemgetter(1))

removes = -1
answer = 0
#print(AB)
for a, b in AB:
    if a > removes:
        removes = b - 1
        answer += 1
print(answer)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
bridge = [0] * M
for i in range(M):
    bridge[i] = [0] * 2
    bridge[i][0], bridge[i][1] = map(int, input().split())
ans = 1
bridge = sorted(bridge, reverse=True)
# print(bridge)
nowcut = bridge[0][0]
for k in range(1, M):
    if bridge[k][1] <= nowcut:
        # print(nowcut)
        nowcut = bridge[k][0]
        ans += 1
print(ans)

Submission status: Accepted

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

ab=sorted(ab,reverse=True)

ans=0
check=float('inf')
for a,b in ab:
    if b<=check:
        check=a
        ans+=1
print(ans)

Submission status: Accepted

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

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

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

e = 0
ans = 0
for i in range(M):
    a, b = q[i]
    if a >= e:
        ans += 1
        e = b
    elif b < e:
        e = b

print(ans)

Submission status: Accepted

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

lst.sort()
d = []
d.append(lst[0])
for i in range(1, M):
    if lst[i][0] != lst[i-1][0]:
        flag = 0
        for j in range(len(d)):
            if d[j][1] > lst[i][0]:
                d[j][0] = lst[i][0]
                if d[j][1] > lst[i][1]:
                    d[j][1] = lst[i][1]
                flag += 1
                break
        if flag == 0:
            d.append(lst[i])
print(len(d))

Submission status: Accepted

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

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

    min_ptr = N 
    counter = 0
    for i,c in enumerate(cmap):
        if i == min_ptr:
            counter += 1
            min_ptr = N
        min_ptr = min(cmap[i],min_ptr)
    print(counter)
resolve()

Submission status: Accepted

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

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

ans = 1
s = -10**9
t = 10**9
for a, b in ab:
    if a >= t:
        ans += 1
        t = b
    else:
        t = min(t, b)

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.sort(key=lambda x:x[1])
ans = 0
x=-1
for i in range(m):
    if a[i][0]>x:
        x=a[i][1]-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)]
a = sorted(a,key=itemgetter(1))
removed = -1
count = 0
for x,y in a:
    if x > removed :
        removed = y-1
        count += 1
print(count)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ab = sorted([list(map(int, input().split())) for _ in range(M)], key=lambda x: x[1])
x = l = 0
for a, b in ab:
    if x < a:
        x = b - 1
        l += 1
print(l)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
A = [list(map(int,input().split())) for _ in range(M)]
A = sorted(A,key=lambda x:x[0])
cnt = 0
bmin = 10**6
for i in range(M):
    a,b = A[i][0],A[i][1]
    if a>=bmin:
        cnt += 1
        bmin = b
    else:
        bmin = min(bmin,b)
cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
vs = []
for i in range(M):
    a, b = map(int, input().split())
    vs.append((b, a))
vs.sort()
end = 0
ans = 0
for b, a in vs:
    if end<=a:
        ans += 1
        end = 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])
c = 0
d = 0
for t in ab:
  if d < t[0]:
    c += 1
    d = t[1]-1
print(c)

Submission status: Accepted

Solution code:
(n,m), *d = [list(map(int, s.split())) for s in open(0)]

s = [n+1]*(n+1)
for x,y in d:
    if s[x] > y:
        s[x] = y

ans = 0
_min = n+1
for i, x in enumerate(s):
    if _min == i:
        _min = n+1
        ans += 1
    
    if _min > x:
        _min = x

print(ans)

Submission status: Accepted

Solution code:
# ABC103d
import sys
from operator import itemgetter
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
span = [list(map(int, input().split())) for _ in range(m)]
span.sort(key=itemgetter(1))

setudan = span[0][1]
ans = 1
for i in span:
    if (i[0] >= setudan):
        setudan = i[1]
        ans += 1
print(ans)

Submission status: Accepted

Solution code:

def main():
    # * - * - *
    n, m = [int(i) for i in input().split()]
    abc = []
    for i in range(m):
        a, b  = [int(j) for j in input().split()]
        abc.append([a,b])
    abc.sort(key=lambda x:x[1])
    i = 1
    ans = 1
    now = abc[0]
    while i < m:
        if now[1] <= abc[i][0]:
            ans += 1
            now = abc[i]
        i += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def solve():
	n,_,*t=map(int,open(0).read().split());r=[n+1]*(n+1)
	for a,b in zip(*[iter(t)]*2):
		r[a]=min(r[a],b)
	a=0;cur=n+1
	for i in range(n+1):
		cur=min(cur, r[i])
		if i==cur:
			#追いついた
			cur=r[i]
			a+=1
	print(a)
if __name__=="__main__":
	solve()

Submission status: Accepted

Solution code:
n,m,*t=map(int,open(0).read().split());r=[n+1]*(n+1)
for a,b in zip(*[iter(t)]*2):
	r[a]=min(r[a],b)
a=0;cur=n+1
for i in range(n+1):
	cur=min(cur, r[i])
	if i==cur:
		cur=r[i]
		a+=1
print(a)

Submission status: Accepted

Solution code:
n,m,*t=map(int,open(0).read().split())
c=d=0
for b,a in sorted([(b,a)for a,b in zip(*[iter(t)]*2)]):
	if a>d:c+=1;d=b-1
print(c)

Submission status: Accepted

Solution code:
def solve():
	n,m,*t=map(int,open(0).read().split())
	r=sorted([(b,a)for a,b in zip(*[iter(t)]*2)])
	c=bef=0
	for b,a in r:
		if a>bef:
			c+=1
			bef=b-1
	print(c)
if __name__=="__main__":solve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n, m = map(int, input().split())
ab = [0]*m
for i in range(m):
    a, b = map(int, input().split())
    ab[i] = (b, a)
ab.sort()
count = 0
last_break = n
for abi in ab:
    if not ((count != 0) & (abi[1] <= last_break)):
        count += 1
        last_break = abi[0] - 1
print(count)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ls = [-1]*N
ans = 0
for i in range(M):
  a, b = map(int, input().split())
  ls[b-1] = max(ls[b-1], a-1)

ps = -1
for i in range(N):
  if ls[i]==-1:
    continue
  if ls[i]>=ps:
    ans += 1
    ps = i
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(M)]
lst.sort(key = lambda x: x[1])
div = 0
cnt = 0
for a, b in lst:
  if a > div:
    div = b-1
    cnt += 1
print(cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
AB = []
for i in range(M):
    a,b = map(int,input().split())
    AB.append([a,b])
AB.sort()
cnt = 1
r_min = float('inf')
for l,r in AB:
    if l>=r_min:
        cnt += 1
        r_min = r
    else:
        r_min = min(r_min,r)
print(cnt)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ab_s = [list(map(int, input().split())) for _ in range(M)]
bridges = [0] * N
ab_s = sorted(ab_s, key=lambda x: x[1])
for ab in ab_s:
    if bridges[ab[1]-1] - bridges[ab[0]-1] == 0:
        for i in range(ab[1]-1, N):
            bridges[i] += 1
print(bridges[-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b, c = LI()
    ans = 10 ** 5
    ans = min(ans, abs(a - b) + abs(b - c))
    ans = min(ans, abs(a - c) + abs(b - c))
    ans = min(ans, abs(a - c) + abs(a - b))
    print(ans)
    return

#B
def B():
    s, t = S(), S()
    f = 0
    for i in range(len(s)):
        f = f or s[i:] + s[:i] == t
    print(["No","Yes"][f])
    return

#C
def C():
    return

# D
# 解説AC
# 貪欲かよ
# 言われればその通りでbi昇順でソートしていれば
# 直前で取り除いたものに関してはその橋より左側
# の街について絶対に橋が途切れているからね
# fuck!!! 
def D():
    n, m = LI()
    d = defaultdict(int)
    for _ in range(m):
        a, b = LI_()
        if d[a] < n - b:
            d[a] = n - b
    mi = 0
    ans = 0
    for i in range(n - 1):
        if mi < d[i]:
            mi = d[i]
        if i == n - mi - 1:
            mi = 0
            ans += 1
    print(ans)
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b, c = LI()
    ans = 10 ** 5
    ans = min(ans, abs(a - b) + abs(b - c))
    ans = min(ans, abs(a - c) + abs(b - c))
    ans = min(ans, abs(a - c) + abs(a - b))
    print(ans)
    return

#B
def B():
    s, t = S(), S()
    f = 0
    for i in range(len(s)):
        f = f or s[i:] + s[:i] == t
    print(["No","Yes"][f])
    return

#C
def C():
    return

# D
# 解説AC
# 貪欲かよ
# 言われればその通りでbi昇順でソートしていれば
# 直前で取り除いたものに関してはその橋より左側
# の街について絶対に橋が途切れているからね
# fuck!!! 
def D():
    n, m = LI()
    d = defaultdict(int)
    for _ in range(m):
        a, b = LI_()
        d[a] = max(d[a], n-b)
    mi = 0
    ans = 0
    for i in range(n - 1):
        if mi < d[i]:
            mi = d[i]
        if i == n - mi - 1:
            mi = 0
            ans += 1
    print(ans)
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b, c = LI()
    ans = 10 ** 5
    ans = min(ans, abs(a - b) + abs(b - c))
    ans = min(ans, abs(a - c) + abs(b - c))
    ans = min(ans, abs(a - c) + abs(a - b))
    print(ans)
    return

#B
def B():
    s, t = S(), S()
    f = 0
    for i in range(len(s)):
        f = f or s[i:] + s[:i] == t
    print(["No","Yes"][f])
    return

#C
def C():
    return

# D
# 解説AC
# 貪欲かよ
# 言われればその通りでbi昇順でソートしていれば
# 直前で取り除いたものに関してはその橋より左側
# の街について絶対に橋が途切れているからね
# fuck!!! 
def D():
    n, m = LI()
    d = defaultdict(int)
    for _ in range(m):
        a, b = LI_()
        d[a] = max(d[a], n-b)
    mi = 0
    ans = 0
    for i in range(n-1):
        mi = max(mi, d[i])
        if i == n - mi - 1:
            mi = 0
            ans += 1
    print(ans)
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b, c = LI()
    ans = 10 ** 5
    ans = min(ans, abs(a - b) + abs(b - c))
    ans = min(ans, abs(a - c) + abs(b - c))
    ans = min(ans, abs(a - c) + abs(a - b))
    print(ans)
    return

#B
def B():
    s, t = S(), S()
    f = 0
    for i in range(len(s)):
        f = f or s[i:] + s[:i] == t
    print(["No","Yes"][f])
    return

#C
def C():
    return

# D
# 解説AC
# 貪欲かよ
# 言われればその通りでbi昇順でソートしていれば
# 直前で取り除いたものに関してはその橋より左側
# の街について絶対に橋が途切れているからね
# fuck!!! 
def D():
    n, m = LI()
    ab = LIR(m)
    ab.sort(key=lambda x: x[1])
    before = 0
    ans = 0
    for a, b in ab:
        if a < before <= b:
            continue
        else:
            before = b
            ans += 1
    print(ans)
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Accepted

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


def main():
    N, M = map(int, input().split())
    Q = []
    for _ in range(M):
        a, b = map(int, input().split())
        heapq.heappush(Q, [b, a])
    
    cnt = 0
    x = 0
    while len(Q)!=0:
        b, a = heapq.heappop(Q)
        if x<a:
            cnt += 1
            x = b-1

    print(cnt)


if __name__ == '__main__':
    main()