Problem:


Score : 400 points

Problem Statement

There are N islands lining up from west to east, connected by N-1 bridges.

The i-th bridge connects the i-th island from the west and the (i+1)-th island from the west.

One day, disputes took place between some islands, and there were M requests from the inhabitants of the islands:

Request i: A dispute took place between the a_i-th island from the west and the b_i-th island from the west. Please make traveling between these islands with bridges impossible.

You decided to remove some bridges to meet all these M requests.

Find the minimum number of bridges that must be removed.

Constraints

All values in input are integers.

2 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq a_i < b_i \leq N

All pairs (a_i, b_i) are distinct.

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
a_2 b_2
:
a_M b_M

Output

Print the minimum number of bridges that must be removed.

Sample Input 1

5 2
1 4
2 5

Sample Output 1

1

The requests can be met by removing the bridge connecting the second and third islands from the west.

Sample Input 2

9 5
1 8
2 7
3 5
4 6
7 9

Sample Output 2

2

Sample Input 3

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

Sample Output 3

4



Sample input:
5 2
1 4
2 5


Sample output:
1

Submission status: Accepted

Solution code:
import sys
from operator import itemgetter

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    Cut = [[int(i) - 1 for i in input().split()] for _ in range(M)]
    Cut.sort(key = itemgetter(1))
    count = 1
    cindex = 1
    cutPlace = Cut[0][1]
    while cindex < M:
        if Cut[cindex][0] < cutPlace: cindex += 1
        else:
            count += 1
            cutPlace = Cut[cindex][1]
            cindex += 1
    print(count)

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def main():
    N, M = (int(i) for i in input().split())
    AB = [[int(i) for i in input().split()] for j in range(M)]
    AB.sort(key=lambda p: p[1])
    ma = AB[0][1]
    ans = 1
    for a, b in AB[1:]:
        if a < ma:
            continue
        else:
            ma = b
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import heapq

def main():
    n, m = map(int, input().split())
    ab = [None] * m
    for i in range(m):
        ab[i] = list(map(int, input().split()))

    ab.sort()

    que = []
    cut_front = 0
    for x in ab:
        if que:
            if que[0] <= x[0]:
                cut_front += 1
                que.clear()
        heapq.heappush(que, x[1])
    if que:
        cut_front += 1
        que.clear()

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

    cut_back = 0
    for x in ab:
        if que:
            if x[1] <= -que[0]:
                cut_back += 1
                que.clear()
        heapq.heappush(que, -x[0])
    if que:
        cut_back += 1
        que.clear()

    print(min(cut_front, cut_back))

if __name__ == '__main__':
    main()

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

count = 1
B = 10 ** 9
for a, b in AB:
    if a < B:
        B = min(B, b)
    else:
        count += 1
        B = b

print (count)

Submission status: Accepted

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

ab.sort()

ans = 0
for i, (ai, bi) in enumerate(ab):
    if i == 0:
        ans += 1
        l = ai
        r = bi
    else:
        l_tmp = max(l, ai)
        r_tmp = min(r, bi)
        if l_tmp < r_tmp:
            l = l_tmp
            r = r_tmp
        else:
            ans += 1
            l = ai
            r = bi

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.sort()
l=1
r=N
ans=1
for a,b in ab:
  l=max(a,l)
  r=min(b,r)
  if l>=r:
    ans+=1
    l=a
    r=b
print(ans)

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    requests = [list(map(int, input().split())) for _ in range(m)]
    requests.sort(key=lambda x: x[1])
    bridge = [-1]
    for begin, end in requests:
        if begin <= bridge[-1] < end:
            continue
        else:
            bridge.append(end - 1)
    print(len(bridge) - 1)


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()
l,r=ab[0]
ans=1
for a,b in ab[1:]:
  if r<=a:
    ans+=1
    l,r=a,b
  else:
    l=max(l,a)
    r=min(r,b)
print(ans)

Submission status: Accepted

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

AB = [tuple(map(int, input().split())) for _ in range(M)]
AB.sort(key=lambda a: (a[0], -a[1]))

ans = 1
right = 10**18
for l, r in AB:
    if l >= right:
        ans += 1
        right = 10**18
    right = min(right, r)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    brs = sorted(zip(a, b), key=lambda br: br[1])
    last = -1
    ans = 0
    for ai, bi in brs:
        if ai <= last:
            continue
        ans += 1
        last = bi - 1
    print(ans)


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

N, M = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(M)]
ab.sort(key=lambda t: t[1])
ans = 0
now_r = 0

for a, b in ab:
    if now_r<=a:
        ans += 1
        now_r = b

print(ans)

Submission status: Accepted

Solution code:
def resolve():
    n, m = map(int, input().split())
    troubles = []
    for _ in range(m):
        a, b = map(int, input().split())
        troubles.append((a, b))

    ans = 0
    saw = 0

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

    for a, b in troubles:
        if saw <= a:
            saw = b
            ans += 1

    print(ans)
    
resolve()

Submission status: Accepted

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

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

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

ans = 0
for i in range(M):
  if i == 0:
    temp = R[i][1]-1 #0個目の終点。この直前で切ればよい。
    ans += 1
  else:
    if R[i][0] > temp:
      temp = R[i][1]-1
      ans += 1
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])

count=1
mae=s[0][1]
for i in range(1,M):
    if s[i][0]>=mae:
        count+=1
        mae=s[i][1]

print(count)

Submission status: Accepted

Solution code:
INF = 10 ** 9
MOD = 10 **9 + 7
import sys
sys.setrecursionlimit(100000000)
dy = (-1,0,1,0)
dx = (0,1,0,-1)
from  collections import deque
from math import factorial

def main():
    n,m = map(int,input().split())
    War = [tuple(map(int,input().split())) for _ in range(m)]
    War.sort(key = lambda x:x[1])

    last_cut = 0
    ans = 0
    for a,b in War:
        if last_cut < a:
            last_cut = b - 1
            ans += 1
    print(ans)
if __name__=='__main__':
    main()

Submission status: Accepted

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

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

kijun=warlist[0][0]-1
bukkowashi=0

for war in warlist:
	if war[0] >= kijun:
		bukkowashi += 1
		kijun = war[1]

print(bukkowashi)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, m = map(int, readline().split())
ab = [tuple(map(int, readline().split())) for _ in range(m)]
ab.sort(key=lambda x: x[1])
cnt = 0
check = -1
for a, b in ab:
    if a <= check < b:
        continue
    check = b - 1
    cnt += 1
print(cnt)

Submission status: Accepted

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

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

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

MAX = 10 ** 9

count = 1
min_ = MAX
for a, b in AB:
    if a < min_:
        min_ = min(min_, b)
    else:
        count += 1
        min_ = b

print (count)

Submission status: Accepted

Solution code:
def main():
    N,M=map(int,input().split())
    a=[0]*M
    b=[0]*M
    r=[0]*M
    for i in range(M):
        a[i],b[i]=map(int,input().split())
        r[i]=[a[i],b[i]]
    r.sort(key=lambda x:x[1])
    point=float("-inf")
    pyout=0
    for fight in r:
        if fight[0]>point:
            point=fight[1]-1
            pyout+=1
    print(pyout)
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
L = [LIST() for i in range(M)]
L = sorted(L, key=lambda x: x[1])
tmp = L[0][1]

ans = 1

for a, b in L:
    if a < tmp <= b:
        continue
    else:
        ans += 1
        tmp = b
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    AB = [[int(i) for i in input().split()] for j in range(M)]
    AB.sort(key=lambda p: p[1])
    mx_b = AB[0][1]
    ans = 1
    for a, b in AB[1:]:
        if a < mx_b:
            continue
        else:
            mx_b = b
            ans += 1
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

a.sort()

ans=1
# 落とす橋の左端、右端を記録
l=a[0][0]
r=a[0][1]
for i in range(1,m):
    l = a[i][0]
    if l>=r:
        r=a[i][1]
        ans+=1
    else:
        r= min(a[i][1],r)

print(ans)

Submission status: Accepted

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

ans = 0
ab.sort()
for i, (ai, bi) in enumerate(ab):
    if i == 0:
        l = ai
        r = bi - 1
        ans += 1
    else:
        l_tmp = max(l, ai)
        r_tmp = min(r, bi - 1)
        if l_tmp > r_tmp:
            l = ai
            r = bi - 1
            ans += 1
        else:
            l = l_tmp
            r = r_tmp

print(ans)

Submission status: Accepted

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

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

def main():
    mod=10**9+7
    #左から見て，できるだけ右できる
    N,M=MI()
    ab=[[0,0]for _ in range(M)]
    for i in range(M):
        ab[i][0],ab[i][1]=MI()
        
    ab.sort(key=lambda x:(x[0],-1*x[1]))
    ans=0
    
    left=-1
    right=N+1
    for i in range(M):
        if ab[i][0]>=right:
            left=ab[i][0]
            right=ab[i][1]
            ans+=1
        else:
            left=ab[i][0]
            right=min(right,ab[i][1])
            
    print(ans+1)
            

main()

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 - 1, b - 1])

lst.sort(key=lambda x: x[1])
end = -1
ctr = 0
for a, b in lst:
    if a < end: continue
    end = b
    ctr += 1

print(ctr)

Submission status: Accepted

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

X.sort(key= lambda x:x[1])
#print(X)

t = -1
ans = 0
for i in range(m):
    a, b = X[i]
    if a >= t:
        ans += 1
        t = b
    else:
        continue
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
AB.sort(reverse=True, key=itemgetter(1))

ans = 1
left, right = AB.pop()
while AB:
    a, b = AB.pop()
    if a >= right:
        ans += 1
        left, right = a, b
    else:
        right = min(right, b)
        left = max(left, a)
print(ans)

Submission status: Accepted

Solution code:
from heapq import heappush, heappop

N, M = map(int, input().split())
LR = [tuple(map(int, input().split())) for _ in range(M)]
LR.sort(key=lambda a: (a[0], -a[0]))

R = 10**18
ans = 0
for l, r in LR:
    if R <= l:
        ans += 1
        R = 10**18
    R = min(R, r)

print(ans + 1)

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N,M=map(int, input().split())
    AB=[tuple(map(int, input().split())) for _ in range(M)]
    from operator import itemgetter
    AB.sort(key=itemgetter(1))
    ans=0
    last=-1
    for a,b in AB:
        if last<=a:
            ans+=1
            last=b
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

broken = [False] * (N - 1)

right = -1
for a,b in AB:
    if a > right:
        broken[b - 1] = True
        right = b - 1

print(broken.count(True))

Submission status: Accepted

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

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

r = -1
cnt = 0
for a, b in AB:
    if r <= a:
        cnt += 1
        r = b
    else:
        r = min(r, b)
print(cnt)

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    query = [[int(x) for x in input().split()] for _ in range(m)]
    break_bridges = [-1]
    query.sort(key=lambda x: x[1])
    for begin, end in query:
        if not (begin <= break_bridges[-1] < end):
            break_bridges.append(end - 1)
    print(len(break_bridges) - 1)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
AB = [tuple(map(int,input().split())) for i in range(M)]
AB.sort(key=lambda x:x[1])
last = -1
ans = 0
for a,b in AB:
    if a <= last < b: continue
    last = 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.sort()
l,r=ab[0]
ans=1
for i,j in ab[1:]:
  if j<=l or r<=i:
    ans+=1
    l,r=i,j
  l=max(l,i)
  r=min(r,j)
print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
war=[list(map(int,input().split())) for _ in range(M)]
war=sorted(war,key=lambda x:x[1],reverse=True)
war.sort(key=lambda x:x[0],reverse=True)
#print(war)
cnt=0
flag=0
ma=war[0][0]
for i in range(M):
    if war[i][1]<=ma:
        cnt=cnt+1
        flag=0
        ma=war[i][0]
print(cnt+1)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
Bridge = []
for i in range(M):
    a, b = map(int, input().split())
    Bridge.append((a, b))
now = -10000000000
Bridge.sort(key=lambda x: x[1])
ans = 0

for i in range(M):
    if Bridge[i][0] >= now:
        ans += 1
        now = Bridge[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.sort(key=lambda x:x[1])
lb=0
c=0
for a,b in l:
    if a>=lb:
        lb=b
        c+=1
print(c)

Submission status: Accepted

Solution code:
from operator import itemgetter

n,m = map(int, input().split())
ab = sorted([list(map(int, input().split())) for i in range(m)], key=itemgetter(1,0))
end = 1
ans = 0
for s,e in ab:
  if s >= end:
    ans += 1
    end = e
print(ans)

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.readline

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

bomb.sort()

count=0
last=-1
for i in range(0,len(bomb)):
    b,a=bomb[i]
    if b-1>=last and last>=a:
        continue
    else:
        count+=1
        last=b-1

print(count)

Submission status: Accepted

Solution code:
nim,mike = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(mike)]
ab.sort()
result = 1
l, r = ab[0][0], ab[0][1]

for a,b in ab[1:]:
    if a < r:
        l = max(l,a)
        r = min(r,b)
    else:
        result += 1
        l = a
        r = b 

print(result)

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 x: x[1])
# print(AB)
base = AB[0][1]
ans = 1
for ab in AB[1:]:
    if ab[0] < base <= ab[1]:
        continue
    else:
        ans += 1
        base = ab[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])

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

q = -1
ctr = 0

for i in range(M):
    if lst[i][0] < q: continue
    ctr += 1
    q = lst[i][1]

print(ctr)

Submission status: Accepted

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

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

bridge=0
count=0
for wish in sorted_wish:
  left=wish[0]
  right=wish[1]
  if left>=bridge and right>bridge:
    count+=1
    bridge=right
print(count)

Submission status: Accepted

Solution code:
import sys

def main():
    N, M = map(int, input().split())
    LR = [tuple(map(int, input().split())) for _ in range(M)]
    RL = sorted([(R, L) for L, R in LR])

    now = 0
    ans = 0
    for R, L in RL:
        if L > now:
            now = R-1
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

war.sort(key=lambda x: x[1])
ans = 0
tmp = -1
for l, r in war:
    if tmp <= l:
        ans += 1
        tmp = r
print(ans)

Submission status: Accepted

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

l,r = ab[0][0],ab[0][1]-1

ans = 1

for i in range(1,m):
    l = max(l,ab[i][0])
    r = min(r,ab[i][1]-1)
    if l > r:
        ans += 1
        l,r = ab[i][0],ab[i][1]-1

print(ans)

Submission status: Accepted

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

A = [0]*(N+1)

for i in range(M):
    A[data[i][1]] = max(A[data[i][1]],data[i][0])

ans = 0
a = 0
for i in range(1,N+1):
    if A[i] == 0:
        continue
    else:
        if A[i] >= a:
            ans += 1
            a = i

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 x: x[1])

cnt=0
border=0

for item in ab:
    if item[0]>=border:
        border=item[1]
        cnt+=1

print(cnt)

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

ll=ab[0][0]
rr=ab[0][1]

cnt=1
#print(ab[0],ll,rr,cnt)
for item in ab[1:]:
    l=item[0]
    r=item[1]
    if l>=rr:
        cnt+=1
        ll=l
        rr=r
    else:
        if r<rr:
            rr=r
        if ll<l:
            ll=l
    #print(item,ll,rr,cnt)

print(cnt)

Submission status: Accepted

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

L_new=sorted(L,key=lambda x:x[1])
#print(L_new)
T=L_new[0][1]-1
count=1
for j in range(1,M):
    if L_new[j][0]<=T:
        pass
    else:
        count+=1
        T=L_new[j][1]-1

print(count)

Submission status: Accepted

Solution code:
def main():
    islands, request_num = map(int, input().split())
    demolition = []
    requests = []
    for _ in range(request_num):
        requests.append(list(map(int, input().split())))
    requests.sort(key=lambda x: x[1], reverse=False)
    for begin, end in requests:
        if 0 < len(demolition) and begin <= demolition[-1] < end:
            continue
        else:
            demolition.append(end - 1)
    print(len(demolition))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

ba.sort()
bridge = [ba[0][0] - 1]


for i in range(1, m):
    if ba[i][1] > bridge[-1]:
        bridge.append(ba[i][0] - 1)

print(len(bridge))

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
#ABC103-D Islands War
"""
問題：
一列にn個の島があり、n-1本の橋で左右の島がつながっている。
m個のクエリが与えられ、aとbの島を橋を取り除くことにより行き来できないようにしたい。
取り除かなければならない橋の本数の最小値を出力

解法：
橋をかけても良い島を探す。
クエリをソートしておいて、左端が入ったものから右端をheapに入れる。heapqで取り出したものが右端であるならば、
そこに橋をかけないものとして、heapをリセットする。(heapに入っている全ての条件がクリアされる為)
"""
import sys
import heapq
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

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

g = []
for i in range(m):
    a,b = map(int,readline().split())
    a,b = a-1,b-1
    g.append((a,b))
g.sort()
heap = []
heapq.heapify(heap)
now = 0
count = 0
for i in range(n-1): #橋の数はn-1個
    while now < m:
        if g[now][0] == i: #クエリが左端に入った場合
            heapq.heappush(heap,g[now][1]) #右端をプッシュ
            now += 1
        else:
            break
    
    if len(heap):
        res = heapq.heappop(heap)
        if res == i+1: #橋を取り除く必要があるなら
            count += 1
            heap = []
            heapq.heapify(heap)
        else:
            heapq.heappush(heap,res)
    

print(count)

Submission status: Accepted

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

Submission status: Accepted

Solution code:

n,m = list(map(int,input().split()))
d = [0]*m
spr = [True]*m
ma = 0
mi = 0
for i in range(m):
    a,b = list(map(int,input().split()))
    d[i] = [a,b]

d = sorted(d)
pre = d[0][1]
ans = 1
for i,(a,b) in enumerate(d):
  if a < pre:
    if b < pre:
      pre = b
  else:
    ans += 1
    pre = b

print(ans)

Submission status: Accepted

Solution code:
import sys
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
def main():
    n, m = MII()
    ab = sorted([(MII()) for _ in range(m)], key=lambda x: x[1])
    pre = -1
    cnt = 0
    for a, b in ab:
        a -= 1; b-= 1
        if a>=pre: cnt+=1; pre=b
    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split(" "))
prohibit = {i: set() for i in range(N)}

for _ in range(M):
    a, b = map(int, input().split(" "))
    prohibit[b - 1].add(a - 1)
    prohibit[a - 1].add(b - 1)

now = set([0])
ans = 0
for i in range(1, N):
    if len(now & prohibit[i]) > 0:
        now = set([i])
        ans += 1
    else:
        now.add(i)
print(ans)

Submission status: Accepted

Solution code:
n, m = [int(x) for x in input().split()]
lr = [[int(x) for x in input().split()] for _ in range(m)]

lr.sort(key = lambda x : x[1])
ans = 0
rm = 0 # 最初のループで必ずif文がFalseになる値
for i in range(m):
    if lr[i][0] <= rm: # 取り除いた橋でカバー可能
        continue
    rm = lr[i][1] - 1  # 取り除く橋の番号
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
n, m = [int(x) for x in input().split()]
lr = [[int(x) for x in input().split()] for _ in range(m)]

lr.sort(key = lambda x : x[1])
ans = 0
rm = 0 # 最初のループで必ずif文がFalseになる値
for i in range(m):
    if lr[i][0] <= rm and lr[i][1] >= rm + 1: # 取り除いた橋でカバー可能
        continue
    rm = lr[i][1] - 1  # 取り除く橋の番号
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
NumIslands, NumRequest = map(int, input().split())
ListConflict = [[int(_) for _ in input().split()] for i in range(NumRequest)]

ListConflict = sorted(ListConflict, key=lambda x: x[1])
right_island_compare = ListConflict[0][1]
total_remove = 1

for i_left_island, i_right_island in ListConflict[1:]:
    if i_left_island < right_island_compare:
        continue

    right_island_compare = i_right_island
    total_remove += 1

print(total_remove)

Submission status: Accepted

Solution code:
##### ABC103-D-Islands War
n,m = map(int,input().split())
l = [list(map(int,input().split())) for _ in range(m)]

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


#c -> 区切り
c = 0

ans = 0

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
w = [list(map(int, input().split())) for _ in range(m)]
w.sort(key=lambda x: x[1])
f = -float('inf')
ans = 0
for p, q in w:
    if p >= f:
        ans += 1
        f = q
print(ans)

Submission status: Accepted

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

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

ans = 1
start = s[0][1]
end = s[0][0]
for i in range(1,m):
    temp_start = s[i][1]
    temp_end = s[i][0]
    if temp_start >= end:
        ans += 1
        end = temp_end
    
print(ans)

Submission status: Accepted

Solution code:

def submit():
    n, m = map(int, input().split())
    
    dislike = [tuple(map(int, input().split())) for _ in range(m)]
    dislike.sort(key=lambda x: x[1])

    cnt = 0
    prev_cut = -1
    for da, db in dislike:
        if da <= prev_cut < db:
            continue
        else:
            cnt += 1
            prev_cut = db - 1

    print(cnt)


submit()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    islands, request_num = map(int, input().split())
    demolition = []
    requests = []
    for _ in range(request_num):
        requests.append(list(map(int, input().split())))
    requests.sort(key=lambda x: x[0], reverse=True)
    for begin, end in requests:
        if 0 < len(demolition) and begin <= demolition[-1] < end:
            continue
        else:
            demolition.append(begin)
    print(len(demolition))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    n,m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(m)]
    ab.sort(key=lambda a: a[1])
    res = 0
    cur = 0
    for i in range(m):
        if cur <= ab[i][0]:
            res += 1
            cur = ab[i][1]
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

rightest_bridge = -1
ans = 0
for a, b in query:
    if a > rightest_bridge:  # 現状切られている橋の中で最も右の橋よりも右にあるなら、区間の最も右の橋を切って要望を満たす
        ans += 1
        rightest_bridge = b-1
print(ans)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    N, M = map(int, input().split())
    hopes = []
    for _ in range(M):
        a, b = map(int, input().split())
        hopes.append([b, a])
    hopes.sort()
    ans = 0
    pos = -1
    for idx, (e, s) in enumerate(hopes):
        if idx == 0 or pos <= s:
            ans += 1
            pos = e
    print(ans)

Submission status: Accepted

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

ab.sort(key = lambda x:x[1])
#print(ab)
end = ab[0][1]
cursol = 0
end = ab[0][1]
cnt = 1
while cursol < M -1:
    cursol += 1
    if end <= ab[cursol][0]:
        end = ab[cursol][1]
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
Alist = []
for i in range(M):
    array = list(map(int, input().strip().split()))
    Alist.append(array)
Alist.sort()
q = 0
p = [Alist[0][0],Alist[0][1]]
for i in range(len(Alist)-1):
    if p[0] < Alist[i+1][0]:
        p[0] = Alist[i+1][0]
    if p[0] >= p[1]:
        q = q+1
        p = [Alist[i+1][0],Alist[i+1][1]]
    if p[1] > Alist[i+1][1]:
        p[1] = Alist[i+1][1]
print(q+1)

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 ab:ab[1])
ans=[ab[0]]
for i in range(1,m):
    if ans[-1][1]<=ab[i][0]:
        ans.append(ab[i])
print(len(ans))

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


def main():
    N, M = [int(x) for x in input().split()]
    AB = [[int(x) for x in input().split()] for _ in range(M)]

    AB.sort()

    ans = 1
    right = AB[0][1]
    left = AB[0][0]
    for a, b in AB[1:]:
        if a >= right:
            ans += 1
            right = b
            left = a
        else:
            left = max(left, a)
            right = min(right, b)

    print(ans)


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

print(ans)