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:
#a = int(input())
#b,c = map(int,input().split())
#s = input()
#list_s = list(input())
#list_int = list(map(int,input().split()))

#list = [0 for i in range(n)]
#dp = [[0 for i in range(A)] for j in range(B)]

#list_int 並べて出力 print (' '.join(map(str,ans_li)))
#list_str 並べて出力 print (' '.join(list))

# 2進数 format(10, 'b') # '1010'

# aa=[int(input()) for i in range(n)]

#for i,name in enumerate(list)

''' 二次元配列を一列ずつ
for i in ans:
	print(*i)
'''
''' heapq
queue = []
heapq.heapify(queue) #heapqの作成
heapq.heappush(queue,num) #numのpush(値の追加)
pop = heapq.heappop(queue) #numのpop(最小値の出力)
pop = heapq.heappushpop(queue,num) #push -> pop

'''

from collections import defaultdict
import sys,heapq,bisect,math,itertools,string
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7


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

left = 0
ans = 0
for q in queue:
	if q[0] >= left:
		ans += 1
		left = q[1]

print(ans)

Submission status: Accepted

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

reg = 0
counter = 0

for ab in ass:
    if ab[0]>=reg:
        counter = counter+1
        reg=ab[1]

print(counter)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
G=[list() for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
ans=0
index=-1
for i in range(1,N):
    for p in G[i]:
        if index<p<i:
            ans+=1
            index=i-1
import time
time.sleep(1)
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int,input().split()) 
a = []
for i in range(M):
    l, r = map(int,input().split())
    a.append((r, l))
a.sort()
ans = 0
last = -1
for i in range(0, M):
    r, l = a[i]
    if last <= l:
        ans = ans + 1
        last = r
print (ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力

def get_list():
    return list(map(int, input().split()))

N, M = map(int, input().split())
war = []
for i in range(M):
    war.append(get_list())
war.sort()

cnt = 1
west, east = war[0]
# スペース区切りの整数の入力
for i in range(1, len(war)):
    west_chk, east_chk = war[i]
    if west_chk < east and east <= east_chk:
        pass
    elif east <= west_chk:
        cnt += 1
        east = east_chk
    elif east_chk < east:
        east = east_chk
        
print(cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力

def get_list():
    return list(map(int, input().split()))

N, M = map(int, input().split())
war = []
for i in range(M):
    war.append(get_list())
war.sort()

cnt = 1
west, east = war[0]
# スペース区切りの整数の入力
for i in range(1, len(war)):
    west_chk, east_chk = war[i]
    if west_chk < east and east <= east_chk:
        pass
    elif east <= west_chk:
        cnt += 1
        east = east_chk
    elif west_chk < east:
        east = east_chk
        
print(cnt)

Submission status: Accepted

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

A = []
for i in range(0, M):
    l, r = (int(i) for i in input().split())
    A.append((r, l))

A.sort()

ans = 0
last = -1
for i in range(0, M):
    r, l = A[i]
    if last <= l:
        ans = ans + 1
        last = r

print (ans)

Submission status: Accepted

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

ans = []

# 全てのlist[1]を基準にソートしていく
num_list.sort(key=lambda x: x[1])
# print(num_list)
# print(num_list[0][1] - 1)
cnt = 0
ans.append(num_list[0][1] - 1)
for i in num_list:
    cnt += 1
    last = ans[-1]
    # print('比較対象', last, " と ", i[1])
    if last not in range(i[0], i[1] + 1):
        # print(cnt, "番目")
        # print(i[1] - 1)
        # print('')
        ans.append(i[1] - 1)

print(len(ans))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
n, m = map(int, input().split())
demands = [
    tuple(map(int,
              line.strip().split())) for line in sys.stdin.readlines()
]
demands.sort(key=lambda demand: demand[1])

x = -1
cnt = 0
for ai, bi in demands:

    if ai <= x:
        continue

    else:
        x = bi - 1
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
n, m = map(int, input().split())
demands = [
    tuple(map(int,
              line.strip().split())) for line in sys.stdin.readlines()
]
demands.sort(key=lambda demand: demand[1], reverse=True)

x = -1
cnt = 0
while demands:
    ai, bi = demands.pop()

    if ai > x:
        x = bi - 1
        cnt += 1

else:
    print(cnt)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a = []
for _ in range(m):
    a.append(list(map(int, input().split())))
a.sort(reverse=True)

ans = 1
p = n+1
for i in range(m):
    if p == n+1:
        p = a[i][0]

    elif p < a[i][1]:
        pass
    else:
        p = a[i][0]
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
s=input().split()
n=int(s[0])
m=int(s[1])
l=[]
for i in range(m):
    s=input().split()
    l.append((int(s[1]),int(s[0])))
l.sort()
o=[]
for p in l:
    if len(o)>0 and p[0]>=o[-1]>p[1]:
        continue
    else:
        o.append(p[0])
print(len(o))

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
v,r,ans=[float('inf') for i in range(n)],float('inf'),0
for i in range(m):
	a,b=map(lambda x:int(x)-1,input().split())
	v[a]=min(v[a],b)
for i in range(n-1):
	r=min(r,v[i])
	if r-i==1:
		ans+=1
		r=float('inf')
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
a=[list(map(int, input().split())) for i in range(m)]
a.sort()
end=n
ans=0
for i in range(m):
    if a[i][0]>=end:
        ans+=1
        end=n
    end=min(a[i][1],end)
print(ans+1)

Submission status: Accepted

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

requests.sort(key=lambda x:x[1])
answer=1
pulldown=(requests[0][1]-1)-1
for i in range(1,M):
    if requests[i][0]-1 <= pulldown:
        pass
    else:
        pulldown=(requests[i][1]-1)-1
        answer+=1
print(answer)

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([a,b-1])
s.sort(key=lambda x:x[1])
ans=0
t=None
for i,j in s:
    if(t is None or t<i):
        t=j
        ans+=1

print(ans)

Submission status: Accepted

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


if __name__ == '__main__':
    n, m = list(map(int, input().split()))
    ab = sorted([tuple(map(int, input().split())) for _ in range(m)],
                key=lambda x: x[1])
    count = 1

    # See:
    # https://www.youtube.com/watch?v=nVSWen0oM38
    b = ab[0][1]

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

    print(count)

Submission status: Accepted

Solution code:
N, M = map( int, input().split())
Q = [[int(s) for s in input().split()] for _ in range(M)]
Q = sorted(Q)
ans = 1
LQ = len(Q)
stan = Q[0][1]
while LQ != 0:
    k = 1
    if Q[0][0] < stan:
        stan = min(stan,Q.pop(0)[1])
        LQ -= 1
    else:
        ans += 1
        stan = Q[0][1]
print(ans)

Submission status: Accepted

Solution code:
N, M = map( int, input().split())
Q = []
for i in range(M):
    a,b = map(int,input().split())
    Q.append([a,b])
Q = sorted(Q)
ans = 1
LQ = len(Q)
stan = Q[0][1]
while LQ != 0:
    k = 1
    if Q[0][0] < stan:
        stan = min(stan,Q.pop(0)[1])
        LQ -= 1
    else:
        ans += 1
        if LQ == 0:
            break
        else:
            stan = Q[0][1]
print(ans)

Submission status: Accepted

Solution code:

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(key=lambda x: x[1]) # sort by b
    cut = []
    for a, b in ab:
        c = False
        for x, y in cut:
            if a <= x:
                c = True
                break
        if not c:
            cut.append((b-1, b))

    print(len(cut))
        
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
m = []
for i in range(M):
    a, b = map(int, input().split())
    m.append((a,b-1))
ans = 0
t = None
for l,r in sorted(m, key=lambda x:x[1]):
    if t is None or l > t:
        t = r
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
l = [200000 for i in range(0, n-1)]

for i in range(0, m):
    a, b = list(map(int, input().split()))
    l[a-1] = min([l[a-1], b-2])

right = -1
count = 0

for i in range(0, n-1):
    if i > right and not l[i] == 200000:
        count += 1
        right = l[i]
    elif i <= right and not l[i] == 200000:
        right = min([l[i], right])

print(count)

Submission status: Accepted

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

for i in range(0,M):
    a = list(map(int,input().split()))
    problems.append(a)

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

x = 0
ans = 0

for j in range(0,len(problems)):
    if problems[j][0] <= x:
        continue
    else:
        x = problems[j][1] - 1
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys

def na(): return map(int,sys.stdin.readline().split())
def ns(): return sys.stdin.readline().strip()

n,m=na()

a=[]
for i in range(m):
    a.append(list(na()))

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

inf = 10000000000
end = inf
ptr = 0
count = 0
for i in range(1,n+1):
    if end == i:
        count += 1
        end = inf
    while ptr < m and a[ptr][0] == i:
        end = min(end, a[ptr][1])
        ptr += 1

print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
n, m = map(int, input().split())
demands = [
    tuple(map(int,
              line.strip().split())) for line in sys.stdin.readlines()
]
demands.sort(key=lambda demand: demand[1])

bridge = -1
cnt = 0
for ai, bi in demands:

    if ai <= bridge:
        continue

    else:
        bridge = bi - 1
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
n, m = map(int, input().split())
ary = [tuple(map(int, line.strip().split())) for line in sys.stdin.readlines()]

demands = sorted(ary, key=lambda x: x[1])[::-1]
compressed = []
while demands:
    a, b = demands.pop()

    for i, (ai, bi) in enumerate(compressed):
        if bi <= a:
            continue

        else:
            if ai < a:
                compressed[i] = (a, min(b, bi))
            break

    else:
        compressed.append((a, b))

print(len(compressed))

Submission status: Accepted

Solution code:
a,b = map(int,input().split())

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

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

s = c[0][0]
l = c[0][1]
re = 1

for i in range(1,b):
  if l <= c[i][0]:
    re += 1
    l = c[i][1]
    
print(re)

Submission status: Accepted

Solution code:
#coding:utf-8

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

cnt = 1
maxa = 0
b = List[0][1]
for i in range(1,M):
    newB = List[i][1]
    maxa = max(maxa,List[i][0])
    if newB > b:
        if maxa >= b:
            cnt += 1
            b = newB
        maxa = 0
        
print(cnt)

Submission status: Accepted

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


if __name__ == '__main__':
    n, m = list(map(int, input().split()))
    ab = list()
    count = 1

    # See:
    # https://www.youtube.com/watch?v=nVSWen0oM38
    for i in range(m):
        ab.append(tuple(map(int, input().split())))

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

    for i in range(1, m):
        if sorted_ab[i][0] < b <= sorted_ab[i][1]:
            pass
        else:
            b = sorted_ab[i][1]
            count += 1

    print(count)

Submission status: Accepted

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

a = [0] * m

for i in range(m):
    a[i] = tuple(map(int, input().split()))

a.sort(reverse=True)

c = n + 1
ret = 0
for i in range(m):
    lft, rgt = a[i]
    if rgt <= c:
        c = lft
        ret += 1

print(ret)

Submission status: Accepted

Solution code:
from operator import itemgetter
n, m = (int(i) for i in input().split())
e = [[int(i) for i in input().split()] for i in range(m)]
g = 1
e.sort(key = itemgetter(1))
for i in range(m):
    if i == 0:
        a = e[0][1] - 1
    else:
        if a >= e[i][0]:
            pass
        else:
            g += 1
            a = e[i][1] - 1
print(g)

Submission status: Accepted

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

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

last  = -1
count = 0
for a, b in R:
    if last < a:
        last = b - 1
        count += 1
print(count)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jul 21 21:41:43 2018
ABC103D
@author: maezawa
"""

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

w = []
cnt = 1

for i in range(m):
    ai, bi = list(map(int, input().split()))
    w.append([ai, bi])

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

cnt = 1
icut = w[0][1]-1 
for bs in w:
    if bs[0] > icut:
        cnt += 1
        icut = bs[1]-1

print(cnt)

Submission status: Accepted

Solution code:
from operator import itemgetter
from collections import deque

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

bridge = [0 for i in range(n-1)]

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

cut_cnt = 1
cut_bridge = deque()
cut_bridge.append(query[0][1] - 2)

for i in range(1, m):
    a, b = query[i]
    if a - 1 > cut_bridge[-1]:
        cut_bridge.append(b - 2)
        cut_cnt += 1


print(cut_cnt)

Submission status: Accepted

Solution code:
from sys import stdin, stdout
input = lambda: stdin.readline()
write = stdout.write

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

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

main()

Submission status: Accepted

Solution code:
w = [int(i) for i in input().split()]
N = w[0]
M = w[1]
A = {tuple([int(j) for j in input().split()]) for i in range(M)}

A_ = sorted(A, key=lambda x: x[1])
bridge = 0
c = 0
for i in A_:
    if i[0] > bridge:
        bridge = i[1]-1
        c += 1
print(c)

Submission status: Accepted

Solution code:
class cxn():
    def __init__(self,start,end):
        self._start = start
        self._end = end
        self._removed = False

    def getStart(self):
        return self._start

    def getEnd(self):
        return self._end

    def isRemoved(self):
        return self._removed

    def remove(self):
        self._removed = True

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

starts = []
ends = []
for i in range(M):
    s,e = map(int,input().split())
    c = cxn(s,e)
    starts.append(c)
    ends.append(c)

starts = sorted(starts,key = cxn.getStart)
ends = sorted(ends,key = cxn.getEnd)

ans = 0
temp = 0

p = 0
for i in range(M):
    rs = False
    while p < M and (not ends[i].isRemoved()) and starts[p].getStart() < ends[i].getEnd():
        temp += 1
        if starts[p] == ends[i]:
            rs = True
        else:
            starts[p].remove()
        p += 1

    if temp != 0:
        ans += 1

    if rs:
        ends[i].remove()

    temp = 0

print(ans)

Submission status: Accepted

Solution code:
'''
https://beta.atcoder.jp/contests/abc103/submissions/2888942
'''

n, m = map(int, input().split())
M = list(tuple(map(int, input().split())) for _ in range(m))#各クエリの(a,b)タプルのリスト
M_b_asc = sorted(M, key=lambda x: x[1])#Mをb昇順でソート

cnt = 0
c = -1
for a, b in M_b_asc:
    #print(a,b,c)
    if a <= c < b:
        continue
    else:
        cnt += 1
        c = b - 1   

print(cnt)

Submission status: Accepted

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

arr = [[] for i in range(n)]

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

cnt = 0	
sting = n+1
for i,isl in enumerate(arr):
	isl.sort()
	if sting == i+1:
		cnt += 1
		sting = n+1

	if len(isl) == 0:
		continue
		
	if isl[0] < sting:
		sting = isl[0]
print(cnt)

Submission status: Accepted

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

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

count = 0
current = float('inf')

for island in islands:
    if island[0] <= current < island[1]:
        continue

    count += 1
    current = island[1] - 1

print(count)

Submission status: Accepted

Solution code:
def d_islands_war(N, M, Demands):
    demands = sorted(Demands, key=lambda x: x[1])
    ans = 1
    _, previous_cut = demands.pop(0)  # previous_cut番目のすぐ西の橋を切る
    for a, b in demands:
        if a >= previous_cut:
            # これが成り立つとき、まだこの要望を満たしていない
            ans += 1
            previous_cut = b
    return ans

N, M = [int(i) for i in input().split()]
Demands = [[int(i) for i in input().split()] for j in range(M)]
print(d_islands_war(N, M, Demands))

Submission status: Accepted

Solution code:

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

a = [None] * M
b = [None] * M

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

p = [[] for i in range(N + 1)]

for i in range(M):
    p[b[i]].append(M + i)

for i in range(M):
    p[a[i]].append(i)

ok = [False] * M
nx = []
ans = 0

for i in range(1, N + 1):
    for j in p[i]:
        if j < M:
            nx.append(j)
        else:
            if ok[j - M]:
                continue

            while nx:
                ok[nx[-1]] = True
                nx.pop()

            ans += 1

print(ans)

Submission status: Accepted

Solution code:
n , m = map(int, input().split())
l = [list(map(int,input().split())) for _ in range(m)]
l.sort()
l = l[::-1]
cnt = 1
key = l[0][0]
for i in range(1,m):
    if key >= l[i][1]:
        cnt += 1
        key = l[i][0]
print(cnt)

Submission status: Accepted

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

war = {}
for i in range(M):
    a, b = map(int, input().split())
    if(b in war):
        if(a > war[b]):
            war[b] = a
    else:
        war[b] = a

ans = 1
b_list = list(war.keys())
b_list = sorted(b_list)
r_bridge = b_list[0] - 1

for b in b_list:
    a = war[b]
    if(a <= r_bridge):
        continue
    else:
        r_bridge = b - 1
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
nm=[int(x) for x in input().split()]
N=nm[0]
M=nm[1]

to=[N]*N
for _ in range(M):
    nm=[int(x) for x in input().split()]
    A=nm[0]-1
    B=nm[1]-1
    if to[B]==N or to[B]<A:
        to[B]=A

last=0
ans=0
for i in range(N):
    if to[i]==N:
        continue
    if to[i]>=last:
      last=i
      ans+=1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
AB = []
for _ in range(m):
    a, b = map(int, input().split())
    AB.append((a, b))
C = [10**6] * n
for a, b in AB:
    C[a-1] = min(C[a-1], b-1)

count = 0
for i in range(n-1):
    if C[i] == i+1:
        count += 1
    else:
        C[i+1] = min(C[i+1], C[i])
print(count)

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(reverse = True)

bridge = [float("inf")]
for i in range(m):
    if ab[i][0] <= min(bridge) < ab[i][1]:
        continue
    else:
        bridge.append(ab[i][0])
print(len(bridge) - 1)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

n, m = map(int, input().split())
disputes = defaultdict(int)
for line in sys.stdin.readlines():
    a, b = map(int, line.split())
    if disputes[b] < a:
        disputes[b] = a
ans = 0
most_right_bridge = 0
for b in sorted(disputes.keys()):
    if most_right_bridge <= disputes[b]:
        ans += 1
        most_right_bridge = b
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

n, m = map(int, input().split())
disputes = defaultdict(int)
for i in range(m):
    a, b = map(int, input().split())
    disputes[b] = max(disputes[b], a)
ans = 0
most_right_bridge = 0
for b in sorted(disputes.keys()):
    if most_right_bridge <= disputes[b]:
        ans += 1
        most_right_bridge = b
print(ans)

Submission status: Accepted

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

disputes.sort()

ans=0
flag=0
for b,a in disputes:
    if flag<=a:
        ans+=1
        flag=b

print(ans)

Submission status: Accepted

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

dp = [0]*(N+1)
for i in range(N):
    dp[i+1] = max(dp[i+1], dp[i])
    for j in T[i]:
        dp[j] = max(dp[i]+1, dp[j])
print(dp[N])

Submission status: Accepted

Solution code:
import bisect

N,M = [int(x) for x in input().split()]

l = [[int(x) for x in input().split()] for _ in range(M)]



def do(l):

    count = 1

    l.sort()
    right = l[0][1]


    for i in range(len(l)):
        if l[i][0] >= right:
            right = l[i][1]
            count+=1
            continue
        if l[i][1] < right:
            right = l[i][1]
    return count

testl = [[x,x+1] for x in range(1)]

result = do(l)
print(result)

Submission status: Accepted

Solution code:
import sys

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

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

count = 0
pb = AB[0][1]
for a, b in AB[1:]:
    if a >= pb:
        count += 1
        pb = b
count += 1
print(count)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
disputes = []
for i in range(m):
    a, b = map(int, input().split())
    disputes.append((b, a))
disputes.sort()
ans = 0
most_right_bridge = 0
for b, a in disputes:
    if most_right_bridge <= a:
        ans += 1
        most_right_bridge = b
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ab=sorted([list(map(int,input().split()))for _ in[0]*m],key=lambda x:x[1])
cnt=0
x=0
for a,b in ab:
   if x<a:x=b-1;cnt+=1
print(cnt)

Submission status: Accepted

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

A = sorted(A, key=lambda x: x[1])
count = 0
x = 0
for a in A:
    if a[0] > x:
        x = a[1] - 1
        count += 1
        
        
print(count)

Submission status: Accepted

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

acum = []

def ifsatisfied(ab):
    for x in acum:
        if ab[0]<x <=ab[1]:
            return(True)
    return(False)

for ab in ass:
    if (acum == [] or ab[0]>=acum[-1]):
        acum.append(ab[1])

print(len(acum))

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

ans = 1
requests = sorted(requests, key=lambda x:(x[1],x[0]))
b = requests[0][1]
for i in range(M):
        if requests[i][0] < b:
                continue
        else:
                ans += 1
                b = requests[i][1]

print(ans)

Submission status: Accepted

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

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

re = 1
x, y = ab[0]
for i in range(1, M):
    a, b = ab[i]
    if b <= x or y <= a: # 切ったとこの範囲外だったら
        re += 1
        x, y = a, b
    else:
        x = max(x, 1)
        y = min(y, b)
print(re)

Submission status: Accepted

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

for _ in range(m):
    l.append(list(map(int, input().split())))

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

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

print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
listAB = [list(map(lambda x:int(x),input().split())) for i in range(M)]
# 要素の2番目でソート
listAB.sort(key=lambda x: x[1])
# 最後に切った橋の位置
last = -1
ans = 0
for a,b in listAB:
    # 切った橋より右側に依頼があるか
    if last <= a:
        ans += 1
        # 切った位置はbの位置
        last = b

print(ans)

Submission status: Accepted

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

acum = []

def ifsatisfied(ab):
    for x in acum:
        if ab[0]<x <=ab[1]:
            return(True)
    return(False)

for ab in ass:
    if not ifsatisfied(ab):
        acum.append(ab[1])

print(len(acum))

Submission status: Accepted

Solution code:
#!/usr/bin/env python

import sys
import math
import itertools as it
from collections import deque

sys.setrecursionlimit(10000000)

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

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

lst.sort()
pos = 0
ans = 0

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

print ans

Submission status: Accepted

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

for _ in range(m):
    l.append(list(map(int, input().split())))

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

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

print(ans)

Submission status: Accepted

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

break_list = [list(map(int, input().split(' '))) for _ in range(M)]
break_list = sorted(break_list, key = lambda key:key[1])

result = 1
most_min_right = break_list[0][1]

for i in range(1, M):
    if most_min_right <= break_list[i][0]:
        most_min_right = break_list[i][1]
        result += 1

print(result)

Submission status: Accepted

Solution code:
import numpy as np
n,m = map(int,input().split())
a = np.zeros(m)
b = np.zeros(m)
for i in range(m):
    a[i] , b[i] = map(int ,input().split())

a -= 1
b -= 1 
cnt = 0

while(a.shape[0]):
    out_of_task = (a >= np.min(b)).astype(np.bool)
    cnt += 1
    a = a[out_of_task]
    b = b[out_of_task]
    
print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python

import sys
import math
import itertools as it
from collections import deque

sys.setrecursionlimit(10000000)

_, 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] - 1

print ans

Submission status: Accepted

Solution code:
import numpy as np
n,m = map(int,input().split())
a = np.zeros(m)
b = np.zeros(m)
for i in range(m):
    a[i] , b[i] = map(int ,input().split())

a -= 1
b -= 1 
cnt = 0

while(a.shape[0]):
    min_b = np.min(b)
    in_task = (a < min_b).astype(np.bool)
    cnt += 1
    tmp = np.logical_not(in_task)
    a = a[tmp]
    b = b[tmp]
    
print(cnt)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
I = [[N + 1] for i in range(N)]
for i in range(M):
  a, b = map(int, input().split())
  I[a - 1].append(b - 1)
cut = 0
for i in range(N - 1):
  if min(I[i]) == i + 1:
    cut += 1
  else:
    I[i + 1].append(min(I[i]))
print(cut)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
tasks = []
for i in range(m):
    a, b = map(int, input().split())
    tasks.append([a, b])
tasks = sorted(tasks, key=lambda x:x[1])
cnt = 1
r = tasks[0][1]
for task in tasks:
    if task[0] >= r:
        cnt +=1
        r = task[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])

ans = 1
requests = sorted(requests, key=lambda x:x[1])
b = requests[0][1]
for i in range(M):
        if requests[i][0] < b:
                continue
        else:
                ans += 1
                b = requests[i][1]

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ab=sorted([list(map(int,input().split()))for _ in[0]*m],key=lambda x:x[1])
x=l=0
for(a,b)in ab:
   if a>x:x=b-1;l+=1
print(l)

Submission status: Accepted

Solution code:
from operator import itemgetter
N,M=map(int,input().split())
table=[]
for i in range(M):
    a,b=map(int,input().split())
    table.append((a,b))
table=sorted(table, key=itemgetter(1))
ans=0
t=0
for a,b in table:
    if t<a:
        ans+=1
        t=b-1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ab=sorted([list(map(int,input().split()))for _ in[0]*m],key=lambda x:x[1])
x=0
l=[0]*n
for(a,b)in ab:
   if a>x:x=b-1;l[x]=1
print(sum(l))

Submission status: Accepted

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

    arr.append([a,b])

#arr.sort(key=lambda x:x[0])
arr.sort(key=lambda x:(x[0],x[1]))
left=0
num=0
count=0
for i in range(len(arr)):
    if arr[i][0]==left:
        pass
    if arr[i][1]<=num:
        num=arr[i][1]
    if arr[i][0]-num>=0:
        count+=1
        num=arr[i][1]
        left=arr[i][0]
    #print(arr[i],count)
print(count)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=[list(map(int,input().split()))for _ in range(m)]
s.sort(key=lambda x:x[0])
c=a=0
while c<m:
    i=1
    t=s[0][1]
    while i<len(s)and s[i][0]<t:
        t=min(t,s[i][1])
        i+=1
    c+=i
    s=s[i:]
    a+=1
print(a)