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())
A = [[int(i) for i in input().split()] for i in range(m)]
A.sort(key=lambda x: x[1])

posi = A[0][1]
count = 1
for i in range(m):
    if posi <= A[i][0]:
        count += 1
        posi = A[i][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 = sorted(ab, key=lambda x: x[1])

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

print(ans)

Submission status: Accepted

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

ab = []
for i in range(0,M):
    inp = list(map(int,input().strip().split()))
    ab.append((inp[0],inp[1]))

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

rightest_cut = 0
count = 0

for m in abl:
    if m[0] <= rightest_cut:
        continue
    rightest_cut = m[1] -1
    count += 1

print(count)

Submission status: Accepted

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

Submission status: Accepted

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

c = 0
prevb = 0

for a, b in sorted(ab, key=lambda x: x[1]):
  if a >= prevb:
    c += 1
    prevb = b
print(c)

Submission status: Accepted

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

posi = 0
count = 0
for i in range(m):
    if A[i][0] >= posi:
        count += 1
        posi = A[i][1]

print(count)

Submission status: Accepted

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

posi = 0
count = 0
for a in A:
    if a[0] > posi:
        posi = a[1] - 1
        count += 1
        
print(count)

Submission status: Accepted

Solution code:
N, M = [int(_) for _ in input().split()]
AB = sorted([[int(_) for _ in input().split()] for _ in range(M)])
l = 0
r = N + 1
ans = 1
for i in range(M):
    if AB[i][0] < r:

        r = min(r, AB[i][1])
    else:
        ans += 1
        r = AB[i][1]
    l = AB[i][0]
print(ans)

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
D = []
L = [0] * N
for i in range(M):
  D.append(list(map(int, input().split())))
D.sort(key = lambda x: x[1])

Ans = 0
Re = 0
for i in D:
  if Re < i[0]:
    Re = i[1]-1
    Ans += 1
print(Ans)

Submission status: Accepted

Solution code:
# coding: utf-8

II = lambda: int(input())
MI = lambda: map(int, input().split())


def main():
    N, M = MI()
    ab = [tuple(MI()) for _ in range(M)]

    ab = sorted(ab, key=lambda x:x[1])
    lb = -1
    cnt = 0
    for a, b in ab:
        if lb <= a:
            lb = b
            cnt += 1
    return cnt


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

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:
    if a > removed:
        removed = b - 1
        ans += 1
print(ans)

Submission status: Accepted

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

ab.sort(key = lambda x:x[1])
dropped = [ab[0][1]-1]
for i in range(1, M): #i番目の要望はこたえられている？
    if ab[i][0] > dropped[-1]:
        dropped += [ab[i][1]-1]

print(len(dropped))

Submission status: Accepted

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

cut, ans = 0, 0
for l, r in a:
    if l >= cut:
        ans += 1
        cut = r
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
wars = []
for _ in range(m):
    wars.append(tuple(map(int, input().split())))
wars.sort(key = lambda x: x[1])
last_distruction = -1
distruction = 0
for l, r in wars:
    if l > last_distruction:
        distruction += 1
        last_distruction = r-1
print(distruction)

Submission status: Accepted

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

Submission status: Accepted

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

cut, ans = 0, 0
for l, r in Requests:
    if l >= cut:
        ans += 1
        cut = r

print(ans)

Submission status: Accepted

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


def main():
    n, m = map(int, input().split())
    ab = sorted([list(map(int, input().split())) for _ in range(m)], key=lambda x: x[1])
    ans = 1
    axis = ab[0][1]

    for i in range(1, m):
        if ab[i][0] >= axis:
            ans += 1
            axis = ab[i][1]

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

# bをキーにして昇順にソートする
pair.sort()

ans = 1
y, x = pair[0]

for i in range(1, M):
    b, a = pair[i]
    if y <= a:
        y = b
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
n,m=map(int,input().split())
x=[]
for i in range(m):
    a,b=map(int,input().split())
    x.append([a,b])
x=sorted(x, key=itemgetter(1))
en=x[0][1]
count=1
for i in range(1,m):
    if en<=x[i][0]:
        en=x[i][1]
        count+=1
print(count)

Submission status: Accepted

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

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

cnt = 0
cb = -1
for (a,b) in ab:
    if cb == -1:
        cb = b - 1
        cnt += 1
    elif a<=cb:
        continue
    else:
        cb = b - 1
        cnt += 1

print(cnt)

Submission status: Accepted

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

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

count=0
before=0

for ai,bi in wars:
    if before>ai:
        continue
        
    before=bi
    count=count+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[0], reverse=True)
last_removed = 1000000
ans = 0
for i in range(m):
	if ab[i][1] <= last_removed:
		last_removed = ab[i][0]
		ans += 1
print(ans)

Submission status: Accepted

Solution code:
import bisect
iipt=lambda:int(input())
miipt=lambda:list(map(int,input().split(" ")))
n, m=miipt()
a=[]
done=[0]*m
for i in range(m):
    a.append(miipt())
b=sorted(a, key=lambda x:x[1])
c=0
d=-1
for p, q in b:
    if not p<=d<q:
        c+=1
        d=q-1
print(c)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    N, M = list(map(int, input().split(" ")))

    temp = [list(map(int, input().split(" "))) for i in range(M)]
    s_list = [temp[i][0] for i in range(M)]
    t_list = [temp[i][1] for i in range(M)]

    ans = 0
    bridge = 0
    for ele in sorted(enumerate(t_list), key=lambda x: x[1]):
        if s_list[ele[0]] > bridge:
            bridge = ele[1]-1
            ans += 1

    print(ans)

Submission status: Accepted

Solution code:
from operator import attrgetter


class Line:
    def __init__(self, a, b):
        self.a = a
        self.b = b


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

lines = sorted(lines, key=attrgetter("a"))

start_num = lines[0].a
min_num = 1000000
cnt = 0

for line in lines:
    if line.a != start_num:
        if min_num <= line.a:
            cnt += 1
            min_num = line.b
        start_num = line.a
    if line.b < min_num:
        min_num = line.b
cnt += 1
print(cnt)

Submission status: Accepted

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

N, M = (int(i) for i in input().split())

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

cc = 0
now = 0
temp = 0
for hasi in hasis:
    now = hasi[0]
    if hasi[1] <= temp < hasi[0]:
        pass
    else:
        temp = now -1
        cc += 1

print(cc)

Submission status: Accepted

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

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

removed = -1
ret = 0

for e in E:
    if e[0] > removed:
        ret += 1
        removed = e[1] - 1

print(ret)

Submission status: Accepted

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


ans = 0
AB = sorted(AB, key=lambda x: x[1])
last = 0
for i, v in enumerate(AB):
    if last < v[0]:
        last = v[1]-1
        ans += 1


print(ans)

Submission status: Accepted

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

for a,b in x:
    if a>=m:
        ans += 1
        m = b
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
N, M = map(int, input().split())
abn = [list(map(int, input().split())) for _ in range(M)]

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

ans = 0
bnum = -1
for a,b in abn:
    if bnum == -1:
        bnum = b - 1
        ans += 1
    elif a <= bnum < b:
        continue
    else:
        bnum = b - 1
        ans += 1

print(ans)

Submission status: Accepted

Solution code:

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

b_list = [0 for i in range(N)]
count=0   
for i in range(N):
    if b_list[i]==1:
        b_list=[0 for i in range(N)]
        count+=1
    for j in Map[i]:
        b_list[j]=1

print(count)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
p = list()
for i in range(m):
    a, b = map(int, input().split())
    p.append((b, a))
p = sorted(p)
broken = -1
ans = 0
for item in p:
    a = item[1]
    b = item[0]
    if a >= broken:
        ans += 1
        broken = b
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
c = []
for i in range(m):#h:高さ
    c.append([int(m) for m in input().split()])
c.sort(key=lambda x:(x[0], x[1]))
p = []
q = []
for i in range(n):
    p.append(0)
    q.append(0)
j = 0
count = 0
for i in range(m):
    if i == 0:
        p[j] = c[i][0]
        q[j] = c[i][1] - 1
    elif i != 0:
        if c[i][0] != c[i - 1][0]:
            j += 1
            p[j] = c[i][0]
            q[j] = c[i][1] - 1
            if q[j - 1] < p[j]:
                count += 1
            else:
                if p[j] < p[j - 1]:
                    p[j] = p[j - 1]
                if q[j] > q[j - 1]:
                    q[j] = q[j - 1]
count += 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])

count = 0
before = 0
for a_i, b_i in ab:
	if before > a_i:
		continue
	before = b_i
	count += 1

print(count)

Submission status: Accepted

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

cut=0
ans=0
for i in range(M):
  if War[i][0]>=cut:
    ans+=1
    cut=War[i][1]
print(ans)

Submission status: Accepted

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

cut = 0
ans = 0
for i in range(m):
    if connections[i][0] >= cut:
        ans += 1
        cut = connections[i][1]

print(ans)

Submission status: Accepted

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

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

count = 0
x = 0
for a_i, b_i in ab:
	if a_i <= x < b_i:
		continue
	x = b_i-1
	count += 1

print(count)

Submission status: Accepted

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

ab.sort()
op_sum = 1
left = ab[0][0]
right = ab[0][1]

for a, b in ab:
    if right <= a:
        op_sum += 1
        left = a
        right = b
    else:
        left = a
        right = min(right, b)

print(op_sum)

Submission status: Accepted

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

ans = 0
cut = -1
src.sort(key=lambda x:x[1])
for a,b in src:
    if a < cut: continue
    cut = b
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,m = li()
ab = []
for _ in range(m):
    a,b = li_()
    ab.append(tuple([a,b]))
    
ab.sort(key=lambda x:x[1])
ans = 0
cur = -1

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

Submission status: Accepted

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

claims = []
for i in range(M):
  claims.append(list(map(int,input().split())))
  
claims.sort()

killed = 0
last_killed = [-1,-1]
for claim in claims:
  if (last_killed[1] < claim[0] or last_killed[0] >= claim[1]):
    last_killed = [claim[0],claim[1] -1]
    killed += 1
  last_killed = [max(last_killed[0],claim[0]),min(last_killed[1],claim[1] -1)]
print(killed)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
dem = [[0, 0] for i in range(M)]
for i in range(M):
    dem[i][0], dem[i][1] = map(int, input().split())
dem.sort(key=lambda x: (x[1]))
br_flag = [False for i in range(N-1)]
count = 0
a = 0
for i in range(M):
    if a < dem[i][0]:
        br_flag[dem[i][1]-2] = True
        a = dem[i][1] - 1
        count += 1
print(count)

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:
n,m=map(int,input().split())

data=[10**5+1]*(n+1)
for _ in range(m):
    l,r=map(int,input().split())
    if(r < data[l]):
        data[l]=r
    

ans=1
i=1
tmpr=data[1]
while(1):
    i+=1
    if(n<i):
        break
    if(data[i] < tmpr):
        tmpr=data[i]
    if(tmpr <= i):
        if(data[i]!=10**5+1):
            ans+=1
            tmpr=data[i]

print(ans)

Submission status: Accepted

Solution code:
#島数と要望数を入力
n_island, n_demand = map(int, input().split())

#要望を取得
demand_list = [list(map(int, input().split())) for i in range(n_demand)]

#右側の島についてソート
demand_list = sorted(demand_list, key=(lambda x:x[1]))

#直前に壊した橋番号を保持
b_0 = 0 #島i-1と島i間の橋
count = 0
for i in range(n_demand):
    #直前の橋を越えた場合
    if demand_list[i][0] >= b_0:
        #次の橋を壊す
        count += 1
        b_0 = demand_list[i][1]

#出力
print(count)

Submission status: Accepted

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

AB.sort(key=lambda x:x[1])
for (a,b) in AB:
    if a>=request_max:
        request_num +=1
        request_max = b
print(request_num)

Submission status: Accepted

Solution code:
import sys

N, M = map(int, input().split())
ab = [list(map(int, line.split())) for line in sys.stdin.readlines()]
ab.sort(key = lambda x : x[1])

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

print(ans)

Submission status: Accepted

Solution code:
import sys

N, M = map(int, input().split())
ab = [tuple(map(int, line.split())) for line in sys.stdin.readlines()]
ab.sort(key = lambda x : x[1])

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

print(ans)

Submission status: Accepted

Solution code:
import sys

N, M = map(int, input().split())
ab = [tuple(map(int, sys.stdin.readline().split())) for _ in range(M)]
ab.sort(key = lambda x : x[1])

ans = 0
last = -1
for a, b in ab:
    if a < last:
        continue
    else:
        ans += 1
        last = 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 x : x[1])

ans = 0
last = -1
for a, b in ab:
    if a < last:
        continue
    else:
        ans += 1
        last = 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])

ans = 0
last = -1
for a, b in ab:
    if a < last:
        continue
    else:
        ans += 1
        last = 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])

ans = 0
last = -1
for abTemp in ab:
    if abTemp[0] < last:
        continue
    else:
        ans += 1
        last = abTemp[1]

print(ans)

Submission status: Accepted

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

last = 100000000
count = 0
for i in hope:
    if(i[0]<=last<i[1]):
        continue
    else:
        last = i[1]-1
        count += 1
        
print(count)

Submission status: Accepted

Solution code:
import numpy as np
N, M = map(int, input().split())
a = np.zeros([M], dtype=int)
b = np.zeros([M], dtype=int)
for i in range(M):
    a[i], b[i] = map(int, input().split())
idx = np.argsort(b)
a = a[idx]
b = b[idx]
c = b[0] - 1
ans = 1
for i in range(1, M):
    if a[i] <= c:
        continue
    else:
        c = b[i] - 1
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
_, M = map(int, raw_input().split())
lst = []

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

lst.sort()
pos = 0
ans = 0

for p in lst:
    if p[1] >= pos:
        ans += 1
        pos = p[0]

print ans

Submission status: Accepted

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

b=[]
for i in m:
    if len([tmp for tmp in b if tmp>=i[1]])==0:
        b.append(i[0]-1)
print(len(b))

Submission status: Accepted

Solution code:
islands = []
bridges = []

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

for i in range(M):
    a, b = map(int, input().split())
    islands.append({'a': a, 'b': b})

islands.sort(key=lambda x: x['b'])
# print(islands)

for i in islands:
    b = [j for j in bridges if j >= i['a']]
    if len(b) == 0:
        bridges.append(i['b'] - 1)

# print(bridges)
print(len(bridges))

Submission status: Accepted

Solution code:
from operator import itemgetter

N,M=map(int,input().split())
ab=[[int(i) for i in input().split()] for j in range(M)]
ab=sorted(ab, key=itemgetter(1))
ans=0
k=0
for i in ab:
    if i[0]>k:
        k=i[1]-1
        ans+=1
print(ans)

Submission status: Accepted

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

r = 0  # いま切ってる一番右端
ans = 0
for a, b in X:
    if r < a:
        r = 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)]
x = 0
ab.sort(key = lambda x:x[1])
ans = 0
for a,b in ab:
  if x <= a:
    ans += 1
    x = b
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M = [int(i) for i in input().split()]
d = []
for i in range(M):
    d.append(list(map(int, input().split())))
d = sorted(d, key=lambda x: x[0])
X=[-2,-1]
D = 0
for i in range(M):
    if X[0] < d[i][1] and d[i][0] < X[1]:
        X = [d[i][0],min(X[1],d[i][1])]
    else:
        D += 1
        X = d[i]
print(D)

Submission status: Accepted

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

n,m = map(int, input().split())
ab = []
for _ in range(m):
    line = list(map(int, input().split()))
    ab.append(line)

ab = sorted(ab, key=itemgetter(1))

cnt = 1
bridge = ab[0][1]-1
for i in range(1,m):
    if ab[i][0]<=bridge and bridge<ab[i][1]:
        continue
    else:
        cnt += 1
        bridge = ab[i][1]-1
print(cnt)

Submission status: Accepted

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

elmd = -1
ans = 0
for a, b in X:
    if a <= elmd < b:
        pass
    else:
        elmd = 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)]

def islands_war(AB):
    AB.sort(key=lambda x: x[1])
    ans = 1
    bridge = AB[0][1] - 1
    for ab in AB:
        if bridge < ab[0]:
            bridge = ab[1] - 1
            ans += 1
    return ans

ans = islands_war(AB)
print(ans)

Submission status: Accepted

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

ans=0
st = [[] for _ in range(N+1)]
goal = [0 for _ in range(N+1)]

for _ in range(M):
    a,b = list(map(int,input().split()))
    st[a] += [b]
    goal[b] += 1

stack = []
for i in range(1,N+1):
    if goal[i]>0:
        ans+=1
        for x in stack:
            goal[x] -= 1
        stack=[]
    if len(st[i])>0:
        stack += st[i]

print(ans)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
invs = []
for _ in range(M):
    L,R = map(int,input().split())
    invs.append((L,R-1)) #R<N
invs.sort(key=lambda inv: inv[0])
x = N
ans = 0
#walls = []
for (a,b) in invs:
    if a > x:
        ans += 1
        #walls.append(x)
        x = b
    else:
        x = min(x,b)
#walls.append(x)
ans += 1
#print(walls)
print(ans)

Submission status: Accepted

Solution code:
# ABC103-D

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

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

ans = 1
bridge = ab[0][1] - 1

for pair in ab:
    if bridge < pair[0]:
        bridge = pair[1] - 1
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
il = lambda: list(map(int, input().split()))
ils = lambda n, s="int(input())": [eval(s) for _ in range(n)]

n, m = il()
l = ils(m, "il()")
l.sort(key=lambda x: x[1])
ans = 0
cur = 0
for i in range(m):
    if l[i][0] >= cur:
        cur = l[i][1]
        ans += 1
print(ans)

Submission status: Accepted

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

ab_array = []

for i in range(m):
    ab = list(map(int,input().split(" ")))
    ab_array.append(ab)

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

ans = [ab_array[0][1]]

for i in ab_array:
    if not i[0] < ans[-1] <=i[1]:
        ans.append(i[1])
print(len(ans))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
D - Islands War
https://beta.atcoder.jp/contests/abc103/tasks/abc103_d

"""
import sys
from sys import stdin
input = stdin.readline


def solve(N, M, data):
    ans = 0
    data.sort(key=lambda x: x[1])
    removed = -1
    for a, b in data:
        if not a <= removed < b:
            ans += 1
            removed = b - 1
    return ans


def main(args):
    N, M = map(int, input().split())
    data = [list(map(int, input().split())) for _ in range(M)]
    ans = solve(N, M, data)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

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

ab = []

for i in range(m):
    ab.append(tuple(map(int, input().split())))

ab.sort(reverse = True)

ans = 0
last = n

for elm in ab:
    a = elm[0]
    b = elm[1]
    if b <= last:
        ans += 1
        last = a

print(ans)

Submission status: Accepted

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

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

	b = -1
	cnt = 0
	
	for x in rqs:
		if b < x[0]:
			b = x[1] - 1
			cnt += 1

	print(cnt)

if __name__ == '__main__':
	main()

Submission status: Accepted

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

rec = sorted(rec, key=lambda s: s[1])
pre = -1
num = 0
for x, y in rec:
    if pre == -1:
        pre = y - 1
        num += 1
    elif x <= pre:
        continue
    else:
        pre = y - 1
        num += 1

print(num)

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

print(ans)

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
AB=list(sorted([list(map(int, input().split())) for _ in range(M)], key=lambda x :x[1]))
ans=1
A=[AB[0]]
for i in range(1,M):
    if AB[i][0]>=A[-1][1]:
        ans+=1
        A.append(AB[i])
print(ans)

Submission status: Accepted

Solution code:
m = lambda: map(int,input().split())
N,M = m()
l = [tuple(m()) for _ in range(M)]
ans = []
l.sort(key=lambda x: x[1])
for i in range(M):
    if not ans or ans[-1]<l[i][0]:
        ans.append(l[i][1]-1)
print(len(ans))

Submission status: Accepted

Solution code:
# encoding: utf-8
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(M)]

# find maximum a for each b
max_as = [0] * N
for a, b in ab:
    if max_as[b - 1] < a: max_as[b - 1] = a

# count num. of valid bridges (bm = b - 1)
ans = 0
last_bridge = -1
for bm, max_a in enumerate(max_as):
    if max_a < 1: continue
    elif max_a <= last_bridge: continue
    ans += 1
    last_bridge = bm
        
# WA

# # check value exists in [a] and [b]
# a_exists = [False] * N
# b_exists = [False] * N
# for a, b in ab:
#     a_exists[a - 1] = True
#     b_exists[b - 1] = True

# # find minimum a -> find minimum b (> a) -> find minimum a (> =b) -> ...
# state = 1
# ans = 0
# for a_exist, b_exist in zip(a_exists, b_exists):
#     print("#", state, ans,  a_exist, b_exist)
#     # search minimum b
#     if state == 1 and b_exist:
#         ans += 1
#         state = 0
#     # search minimum a (can occur immediately after state = 0)
#     if state == 0 and a_exist:
#         state = 1

print(ans)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(m)]
ab.sort(key=lambda tup: tup[1])
bridge,ans=-1, 0
for a,b in ab:
    if a <= bridge:
        continue
    else:
        bridge = b - 1
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split(" "))
pair = []
for i in range(M):
    a,b = map(int,input().split(" "))
    pair.append((a,b))
pair.sort(key=lambda x:x[1])

cur = (-1)
cnt = 0
for i in range(M):
    if pair[i][0] <= cur and cur < pair[i][1]:
        pass
    else:
        cur = pair[i][1] - 1
        cnt += 1

print(cnt)

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((i, a, b))

rm = []
for i, a, b in sorted(ab, key=lambda x:x[2]):
    pre = ab[rm[-1]][2] - 1 if len(rm) else 0
    if a <= pre:
        continue
    else:
        rm.append(i)
print(len(rm))

Submission status: Accepted

Solution code:
from pprint import pprint
n, m = map(int, input().split())
ab = []
for i in range(m):
    a, b = map(int, input().split())
    ab.append((i, a, b))

rm = []
for i, a, b in sorted(ab, key=lambda x:x[2]):
    pre = ab[rm[-1]][2] - 1 if len(rm) else 0
    if a <= pre:
        continue
    else:
        rm.append(i)
print(len(rm))

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])
a=0
b=0
for x in l:
  if x[0]>=b:
    b=x[1]
    a+=1
print(a)

Submission status: Accepted

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

now = 0
ans = 0
for i in shima:
    if now < i[0]:
        now = i[1]-1
        ans += 1
print(ans)

Submission status: Accepted

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

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

r = 0
ans = 0
for a, b in E:
    if a >= r:
        ans += 1
        r = b

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