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())
pairs = []
for i in range(m):
  ai,bi = map(int,input().split())
  pairs.append([ai,bi])

pairs.sort(key=itemgetter(1))

ans = 0
curr = [0,0]
for pair in pairs:
  if not curr[1] > pair[0]:
    ans += 1
    curr = pair

print(ans)

Submission status: Accepted

Solution code:
def ck(a,b,arr):
  if arr >= a and arr < b:
    return 0
  else:
    return 1

N,M=map(int,input().split())
List=[list(map(int,input().split())) for i in range(M)]
List_2 = [0] * M
arr = 0
cnt = 0

for i in range(M):
  a = List[i][1]
  b = List[i][0]
  List_2[i] = [a,b]
  
List_2.sort()
  
for i in range(M):
  a = List_2[i][1]
  b = List_2[i][0]

  hantei = ck(a,b,arr)
  if hantei == 1:
    arr = b-1
    cnt += 1
  
print(int(cnt))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
sp=[None for i in range(m)]
for i in range(m):
  l,r=map(int,input().split())
  sp[i]=[l,r]
sp.sort(key=lambda x:x[1])
sp.sort(key=lambda x:x[0])
s=[sp[0]]
for i in sp:
  if i[0]!=s[-1][0]:
    s.append(i)
ans=1
c=s[0]
if len(s)==1:print(1)
else:
  for i in range(1,len(s)):
    if c[1]<=s[i][0]:
      ans+=1
      c=s[i]
    if c[1]>s[i][1]:
      c=s[i]
    else:
      c[0]=s[i][0]
  print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
last=0
x=[-1]*n
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    x[b]=max(a,x[b])
ans=0
for i in range(0,n):
    if last<=x[i]:
        ans+=1
        last=i
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
s = [list(map(int, input().split())) for i in range(m)]
s.sort(key=lambda x: x[1])
tmp = 0
ans = 0
for si in s:
    if tmp == 0:
        ans += 1
        tmp = si[1]
        continue
    if tmp <= si[0]:
        ans += 1
        tmp = si[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])
broken = -1
ans = 0
for a, b in ab:
    if broken < a:
        broken = b - 1
        ans += 1
print(ans)

Submission status: Accepted

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

for i in range(M):
  a,b = map(int,input().split())
  table.append((a,b))
  
table.sort()
r = N
for a,b in table:
  if r <= a:
    ans += 1
    r = N
  r = min(b,r)
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
requests = [tuple(map(int, input().split())) for _ in range(M)]
requests.sort(key=lambda x: x[1])
counts = 0
left = 0
for a, b in requests:
    if a >= left:
        left = b
        counts += 1
print(counts)

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


ans = 1
l = 1
r = N
for a,b in ab:
    if a < r:
        l = a
        r = min(r,b)
    else:
        ans += 1
        l = a
        r = b
print(ans)

Submission status: Accepted

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

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

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

cnt = 1
cutting = requests[0][1]-1
for i in range(1, m):
    if not requests[i][0] <= cutting <= requests[i][1]:
        cnt += 1
        cutting = requests[i][1]-1

print(cnt)

Submission status: Accepted

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

Submission status: Accepted

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

itv = [[0 for i in range(2)] for j in range(m)]
for i in range(m):
    itv[i][0] = b[i]
    itv[i][1] = a[i]
itv.sort()

ans = 0
curx = 0

for i in range(m):
    if curx <= itv[i][1]:
        curx = itv[i][0]
        ans += 1
        
print(ans)

Submission status: Accepted

Solution code:

N, M = map(int, input().split())
xs = []
for i in range(M):
    a, b = map(int, input().split())
    xs += [(a, 1, i), (b, 0, i)]
xs.sort()
d = set()
r = 0
for x, s, i, in xs:
    if s == 1:
        d.add(i)
    else:
        if i not in d:
            continue
        r += 1
        d = set()
print(r)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
R = [tuple(map(int, input().split())) for _ in range(M)]
R.sort(key=lambda x: x[0], reverse=True)
count = 0
broke = 10**6
for a, b in R:
    if b <= broke:
        count += 1
        broke = a

print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from operator import itemgetter

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

res = 0
s = 0
for a,b in ab:
    if a<=s<b:
        continue
    s = b-1
    res += 1

print(res)

Submission status: Accepted

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

arr=[]

for i in range(m):
    b = list(map(int,input().split()))
    arr.append(b)

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

#print(arr)

ans=1
start=0
fin=10**10
for i,j in arr:
    if fin > i >= start:
        start = max(i,start)
        if j<=fin:
            fin = min(j,fin)
            #print(i,j)
    elif i >= fin:
        ans+=1
        start = i
        fin = j

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
ab = []
for i in range(M):
    ab.append(list(map(int,input().split())))
ab.sort(key = lambda ab:ab[1])
count = 0
now = 0
for a,b in ab:
    if a >= now:
        count += 1
        now = b
print(count)

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
AB=sorted([list(map(int,input().split())) for i in range(M)],key=lambda x:x[1])
hasi=0
count=0
for a,b in AB:
    if a>=hasi:
        hasi=b
        count+=1
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())
    if a in ab:
        ab[a]=min(ab[a],b)
    else:
        ab[a]=b
ab = sorted(ab.items(), key=lambda x:x[0])

ans=1
min_end=10**10
for i in range(len(ab)):
    if ab[i][0]>=min_end:
        ans+=1
        min_end=ab[i][1]
    else:
        min_end=min(ab[i][1], min_end)
print(ans)

Submission status: Accepted

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

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

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())
info = []
for _ in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    info.append([a, b])
info.sort()
tmp = []
for i, j in enumerate(info):
    if i == 0:
        tmp.append(j[1])
    elif j[0] > tmp[-1]-1:
        tmp.append(j[1])
    else:
        if j[1] < tmp[-1]:
            tmp[-1] = j[1]
print(len(tmp))

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
table = [0 for _ in range(n-1)]
info = []
for _ in range(m):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    info.append([a, b])
info = sorted(info, key=lambda x:x[1])
for i, tap in enumerate(info):
    a, b = tap
    if i == 0:
        c = [b-1]
    elif a > c[-1]:
        c.append(b-1)
    else:
        pass
print(len(c))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc103/tasks/abc103_d
N, M = map(int, input().split(' '))

I = []
for _ in range(M):
    I.append(tuple(map(int, input().split(' '))))

# bが小さい順にソート
I = sorted(I, key=lambda x:x[1])
for i, tup in enumerate(I):
    a, b = tup
    if i == 0:
        bb = [b-1]
    elif a > bb[-1]:
        bb.append(b-1)
    else:
        pass
print(len(bb))

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.sort()
for i in range(M):
    a,b = Q[i]
    Q[i] = (b,a)
Q.sort()
B = 0
ans = 0
for i in range(M):
    b,a = Q[i]
    if a >= B:
        B = b
        ans += 1
print(ans)

Submission status: Accepted

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

ab = sorted(ab, key=lambda x: (x[0], x[1]))
cnt = 1
left, right = ab[0]
for a, b in ab[1:]:
    if b <= left or right <= a:
        cnt += 1
        left, right = a, b
    else:
        left = max(left, a)
        right = min(right, b)
print(cnt)

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])
count = 1
broken = ab[0][1]-1
for i in range(m):
    if ab[i][0] <= broken:
        continue
    else:
        count += 1
        broken = ab[i][1]-1
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])
ans = 0
x = 0
for a,b in AB:
    if a <= x:
        continue
    x = b-1
    ans += 1
print(ans)

Submission status: Accepted

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

Q.sort(key=lambda x: x[1])
ans = 0
prev = 0
for ai, bi in Q:
    if prev < ai:
        ans += 1
        prev = bi - 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
lst = []
for _ in range(m):
    a, b = map(int, input().split())
    lst.append((a, b))
sor = sorted(lst, key=lambda x:x[1])
spl = -1
cnt = 0
for a, b in sor:
    if a<=spl:
        continue
    else:
        spl = b-1
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ab=[]
for _ in range(m):
  ab.append(tuple(map(int,input().split())))
ab=sorted(ab, key=lambda x: x[1])
lastbridge=0
cnt=0
for i in range(m):
  st=ab[i][0]
  go=ab[i][1]
  if st<=lastbridge<go:
    continue
  else:
    cnt+=1
    lastbridge=go-1
  #print(lastbridge)

print(cnt)

Submission status: Accepted

Solution code:

"""
できるだけ右端に寄せればいいのでは？
区間の終わりが来た時にキューの中身を空にして全部終わりにする
"""
from collections import deque

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

a = []
b = []

for i in range(M):

    A,B = map(int,input().split())
    a.append([A-1,i])
    b.append([B-1,i])

q = deque([])
end = [False] * (M)
ans = 0

ai = 0
bi = 0
a.sort()
b.sort()
a.append([float("inf"),0])
b.append([float("inf"),0])

for i in range(2*M):

    #print (a[ai],b[bi])

    if a[ai][0] < b[bi][0]:
        q.append(a[ai][1])
        ai += 1
    else:
        if end[b[bi][1]]:
            bi += 1
        else:
            loop = len(q)
            ans += 1
            for j in range(loop):

                now = q.popleft()
                end[now] = True
            bi += 1

print (ans)

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

N, M = list(map(int, sys.stdin.buffer.readline().split()))
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]

AB.sort()

counts = np.zeros(N, dtype=int)
stack = []
ans = 0
p = 0
for a, b in AB:
    a -= 1
    b -= 1
    while True:
        if counts[p] > 0:
            while stack:
                r = stack.pop()
                counts[r] -= 1
            ans += 1
        if p >= a:
            break
        p += 1
    stack.append(b)
    counts[b] += 1
    # print(a, b, p, ans)
if stack:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:

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

ab = [tuple(map(int, input().split())) for i in range(M)]

ab = [tuple([ab[i][0], ab[i][1], i]) for i in range(M)]
ans = 1
tmp = 0

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

checked = set()

for i in range(M):
    if b[tmp][1] <= a[i][0]:
        ans += 1
        while(b[tmp][1] <= a[i][0] or b[tmp][2] in checked):
            tmp += 1
    checked.add(a[i][2])

print(ans)

Submission status: Accepted

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


ab = [tuple(map(int, input().split())) for i in range(M)]
ab = [tuple([ab[i][0], ab[i][1], i]) for i in range(M)]

ans = 1
tmp = 0

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

checked = set()

for i in range(M):
    if b[tmp][1] <= a[i][0]:
        ans += 1
        while(b[tmp][1] <= a[i][0] or b[tmp][2] in checked):
            tmp += 1
    checked.add(a[i][2])


print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = [list(map(int,input().split())) for i in range(m)]
a.sort(key=lambda x:x[1])
bridge = [a[0][1]-1]
for i in range(1,m):
    if a[i][0] > bridge[-1]:
        bridge.append(a[i][1]-1)
print(len(bridge))

Submission status: Accepted

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(10**9)
INF=10**18
def input():
    return sys.stdin.readline().rstrip()

def main():
    N,M=map(int,input().split())
    a,b=[0]*M,[0]*M
    for i in range(M):
        a[i],b[i]=map(int,input().split())
    a_argsorted=np.argsort(a)
    a_max=0
    b_min=INF
    ans=1
    for i in a_argsorted:
        a_max=a[i]
        b_min=min(b_min,b[i])
        if a_max>=b_min:
            ans+=1
            b_min=b[i]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M=[int(x) for x in str(input()).split()]
X=[]
for i in range(M):
  t=[int(x) for x in str(input()).split()]
  X.append(t)

X.sort()
#print(X)
temp=N+1
ans=0
for j in range(1,M+1):
  if not (X[-j][0]<=temp and temp<=X[-j][1]):
    temp=X[-j][0]+1
    #print(temp)
    ans+=1

print(ans)

Submission status: Accepted

Solution code:
def solve():
    from sys import stdin
    f_i = stdin
    
    N, M = map(int, f_i.readline().split())
    ab = [tuple(map(int, f_i.readline().split())) for i in range(M)]
    ab.sort()
    
    ans = 1
    t = N
    for a, b in ab:
        if a >= t:
            ans += 1
            t = N
        t = min(t, b)
    
    print(ans)

solve()

Submission status: Accepted

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

for x in island:
    x.sort()
island.sort(key = lambda t: t[0], reverse = True)

ans = 0
broken = island[0][1]
for x in island:
    if x[0] <= broken < x[1]:
        pass
    else:
        ans += 1
        broken = x[0]
print(ans)

Submission status: Accepted

Solution code:
import sys

n, m, *ab = map(int, sys.stdin.read().split())
ab = sorted(zip(*[iter(ab)] * 2))

def main():
    r = ab[0][1]
    cnt = 0
    for a, b in ab[1:]:
        if a < r:
            if b < r:
                r = b
            continue
        else:
            cnt += 1
            r = b
    cnt += 1
    return cnt

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

Submission status: Accepted

Solution code:
import sys

n, m, *ab = map(int, sys.stdin.read().split())
ab = sorted(zip(*[iter(ab)] * 2))

def main():
    r = -1
    cnt = 0
    for a, b in ab:
        if a < r:
            if b < r:
                r = b
            continue
        else:
            cnt += 1
            r = b
    return cnt

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ablist = sorted([tuple(map(int, input().split())) for _ in range(M)], key=lambda x: x[1])
broken = 0
ans = 0
for a, b in ablist:
    if a > broken:
        ans += 1
        broken = b - 1
print(ans)

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



check = -1
count = 0
for a,b in l:
  if a > check:
    count += 1
    check = b-1

print(count)

Submission status: Accepted

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

a_b_list.sort(key=lambda x: x[0])

max_a = a_b_list[0][0]
min_b = a_b_list[0][1]
count = 1
# print(a_b_list[0], a_b_list[0][0], min_b, count)
for a_b in a_b_list[1:]:
    # print(a_b, a_b[0], min_b, count)

    if a_b[0] < min_b:
        min_b = min(min_b, a_b[1])
    else:
        count += 1
        min_b = a_b[1]

print(count)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

def greedy():
    cnt = 0
    while len(E) > 0:
        edge = E.pop()
        cnt += 1
        while len(E) > 0 and E[-1][0] < edge[1]:
            E.pop()
    
    return cnt
    

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

result = greedy()
print(result)

Submission status: Accepted

Solution code:
from operator import itemgetter

n, m = map(int, input().split())
r = sorted([list(map(int, input().split())) for _ in range(m)], key = itemgetter(0))


last = 0
count = 0
for i in range(m):
    if last > r[i][1]:
        last = r[i][1]
    elif last <= r[i][0]:
        count += 1
        last = r[i][1]

print(count)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
H=[list(map(int,input().split()))for _ in range(M)]
H.sort()
a=H[-1][0]
s=1
for i in range(M-2,-1,-1):
 if H[i][1]<=a:
  s+=1
  a=H[i][0]
print(s)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
H=[list(map(int,input().split()))for _ in range(M)]
H.sort()
a=H[-1][0]
s=1
for i in range(M-2,-1,-1):
    if H[i][1]<=a:
        s+=1
        a=H[i][0]
print(s)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
H=[list(map(int,input().split())) for _ in range(M)]
H.sort(key=lambda x:x[1])
b=H[0][1]
ans=1
for i in range(M):
    if H[i][0]>=b:
        ans+=1
        b=H[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())
ls = [list(map(int, input().split())) for i in range(m)]
ls.sort(key=lambda x: x[1])

ans = 0
idx = 0
for l in ls:
    if idx <= l[0]:
        idx = l[1]
        ans += 1

print(ans)

Submission status: Accepted

Solution code:

from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations
import sys
import bisect
import string
import math
import time
from fractions import gcd
#import random


def I(): return int(input())


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


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['Yes', 'No']
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)


# show_flg = False
show_flg = True


def main():
    N, M = MI()
    ab = [None] * M

    for i in range(M):
        a, b = MI()
        ab[i] = (a, b)

    ab = sorted(ab, key=lambda x: x[1])
    # print(ab)
    bridge = [(ab[0][1]-1, ab[0][1])]

    for i in range(1, len(ab)):
        # print(ab[i], bridge[-1])
        if ab[i][0] <= bridge[-1][0] and ab[i][1] >= bridge[-1][1]:
            pass
        else:
            bridge.append((ab[i][1]-1, ab[i][1]))

    print(len(bridge))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

#「共通の範囲」を記録した配列作り、答えはその長さ
common=[[bri[0][0],bri[0][1]]]
j=0 #今、何番目のcommonを調べてるか

for i in range(1,m):
  a,b=bri[i]
  c,d=common[j] #変数に分解したら、流石にその中身は参照渡しにならない模様
  if d<=a:
    common.append([a,b])
    j+=1
  else:
    c=a
    d=min(b,d)
    common[j][0]=c
    common[j][1]=d

#print(common)
print(len(common))

Submission status: Accepted

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

AB.sort()
INF = 10 ** 10

B_min = INF
answer = 0
for A, B in AB:
  if A >= B_min:
    answer += 1
    B_min = B
  else:
    B_min = min(B_min, B)
answer += 1

print(answer)

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  # これでb-1からbには行けないようにする
        ans += 1  # 取り除いた分カウント

print(ans)

Submission status: Accepted

Solution code:
def remove_path(islands,x,N):
    if x==0:
        islands[0].remove(1)
    elif x==N-1:
        islands[N-1].remove(N-2)
    else:
        islands[x].remove(x-1)
        islands[x-1].remove(x)

if __name__ == '__main__':
    N,M=list(map(int,input().split()))
    orders=[tuple(map(int,input().split())) for i in range(M)]
    islands={i:[i-1,i+1] for i in range(1,N-1)}
    islands[0]=[1]
    islands[N-1]=[N-2]

    orders.sort(key=lambda x:x[1])
    flag=False
    last=None
    count=0

    for order in orders:
        a,b=order[0],order[1]
        if flag and a<=last:
            continue
        else:
            remove_path(islands,b-1,N)
            last = b - 1
            count += 1
            flag = True

    print(count)

Submission status: Accepted

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

from collections import deque

def main():
    n,m = map(int, input().split())
    qp = [tuple(map(int, input().split())) for _ in range(m)]

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

    qp = deque(qp)

    ans = 0
    pre = 0

    while qp:
        a,b = qp.popleft()
        if pre<a:
            ans += 1
            pre = b-1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

from collections import deque

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

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

qp = deque(qp)

ans = 0
pre = 0

while qp:
    a,b = qp.popleft()
    if pre<a:
        ans += 1
        pre = b-1
print(ans)

Submission status: Accepted

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

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

ans = 0
pre = 0

while qp:
    a,b = qp.pop(0)
    if pre<a:
        ans += 1
        pre = b-1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

temp=list(map(int, input().split()))
N=temp[0]
M=temp[1]

A=np.zeros((M,2)).astype(int)

for i in range(M):
  temp=list(map(int, input().split()))
  temp[0]-=1
  temp[1]-=1
  A[i]=temp
idx=A[:,1].argsort()
a=[0]*M
b=[0]*M
for i in range(M):
  a[i]=A[idx[i],0]
  b[i]=A[idx[i],1]
flag=False
x=-1
ans=0
for i in range(M):
  if a[i]>x:
    x=b[i]-1
    ans+=1
print(ans)

Submission status: Accepted

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

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

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

for a,b in bridge:
    if len(cut)==0:
        cut.append(b-1)
    else:
        c = cut[-1]
        if a > c:
            cut.append(b-1)

print(len(cut))

Submission status: Accepted

Solution code:
from functools import reduce
import sys
input = sys.stdin.readline

N, M = map(int, input().split(" "))
disputes = list()
current = 0
for _ in range(M):
    a, b = map(int, input().split(" "))
    disputes.append((a, b))

disputes = sorted(disputes, key=lambda x: x[1])
count = 1
most_recently_removed = disputes[0][1] - 1
for i, dispute in enumerate(disputes[1:]):
    a, b = dispute
    if a <= most_recently_removed <= b-1:
        pass
    else:
        most_recently_removed = b-1
        count += 1

print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from operator import itemgetter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = MAP()
edges = []
for i in range(M):
    a, b = MAP()
    edges.append((a, b))
# 右端でソート
edges.sort(key=itemgetter(1))

nxt = cnt = 0
for a, b in edges:
    # 左端が切る位置より先にあったらもう1回切る
    if a > nxt:
        # 次に切る位置
        nxt = b - 0.5
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,M=MI()
    AB=LLIN_(M)
    AB.sort(key=lambda x: x[1])
    before = -1
    ans=0
    for a,b in AB:
        if before<=a:
            before=b
            ans+=1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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


def solve():
    # b[i]の値でソートする
    bridges = sorted(list(zip(a, b)), key=lambda tup: tup[1])

    ans, tmp = 0, 1

    for bi in range(0, len(bridges)):
        # まだ橋を撤去していなかったら
        # 最も右端の端を撤去する
        if tmp <= (bridges[bi])[0]:
            tmp = (bridges[bi])[1]
            ans += 1


    print(ans)

def main():
    solve()

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



n, m = LI()
L = sorted(LIR(m), key=lambda x:x[1])
pre_end = 0
cnt = 0
for start, end in L:
    if start < pre_end:
        continue
    else:
        cnt += 1
        pre_end = end


print(cnt)