Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

Find the minimum number of bridges that must be removed.

Constraints

All values in input are integers.

2 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq a_i < b_i \leq N

All pairs (a_i, b_i) are distinct.

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
a_2 b_2
:
a_M b_M

Output

Print the minimum number of bridges that must be removed.

Sample Input 1

5 2
1 4
2 5

Sample Output 1

1

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

Sample Input 2

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

Sample Output 2

2

Sample Input 3

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

Sample Output 3

4



Sample input:
5 2
1 4
2 5


Sample output:
1

Submission status: Accepted

Solution code:
from operator import itemgetter
n,m=map(int,input().split())
a=[""]*m
b=[""]*m
for i in range(m):
    x,l=map(int,input().split())
    a[i]=x*10+5
    b[i]=l*10-5
st=sorted([(a[i],b[i]) for i in range(m)], key=itemgetter(1))
ans=0
last=0
last=-float("inf")
for i in range(m):
    if last<st[i][0]:
        ans+=1
        last=st[i][1]
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
from collections import deque
def main():
    n, m = map(int, input().split())
    ab = [tuple(map(int, input().split())) for _ in range(m)]

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

    cnt = 1
    me = ab.popleft()
    while ab:
        me_n = ab.popleft()
        if me_n[0] < me[1]:
            continue
        else:
            cnt += 1
            me = me_n
    print(cnt)


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(key=lambda x: [x[1]])
migi = 0
cnt = 0
for i in range(m):
    a, b = AB[i]
    if migi <= a:
        cnt += 1
        migi = b

print(cnt)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
intervals = []
for _ in range(M):
    a,b = map(int,input().split())
    intervals.append([a,b])
intervals.sort()
ans = [intervals[0]]
for i in range(len(intervals)):
    if ans[-1][1]>intervals[i][0]:
        if ans[-1][1]>intervals[i][1]:
            ans[-1][1]=intervals[i][1]
        ans[-1][0] = intervals[i][0]
    else:
        ans.append(intervals[i])
print(len(ans))

Submission status: Accepted

Solution code:
def resolve():
    '''
    code here
    '''

    N, M = [int(item) for item in input().split()]
    bridges = [[int(item) for item in input().split()] for _ in range(M)]

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

    prev = bridges[0][1]
    for a, b in bridges:
        if a >= prev:
            res +=1
            prev = b

    print(res)    



if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
B = []
for _ in range(M):
    a, b = map(int, input().split())
    B.append([b, a])
B.sort()
C = []
i = 0
while True:
    C.append(B[i])
    if i == M - 1:
        break
    j = 1
    while True:
        if B[i][0] > B[i + j][1]:
            j += 1
            if i + j == M:
                break
            continue
        else:
            break
    if i + j == M:
        break
    i = i + j
print(len(C))

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
W = [list(map(int, input().split())) for _ in range(M)]
W.sort()
C = [0 for i in range(N-1)]
r = W[0][1]-1
for i in range(1, M):
    r = min(W[i][1]-1, r)
    if r <= W[i][0]-1:
        C[W[i-1][0]-1] = 1
        r = W[i][1]-1
C[W[-1][0]-1] = 1
print(sum(C))

Submission status: Accepted

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


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')


#import numpy as np

def main():
	n,m=MI()
	li=[LI() for _ in range(m)]
	#print(li)
	li.sort(key=lambda x:x[1])
	#print(li)
	
	now=0
	ans=0
	
	for a,b in li:
		if now<=a:
			ans+=1
			now=b
	
	print(ans)
	
	

if __name__ == "__main__":
	main()

Submission status: Accepted

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

l_end = -1
ans = 0
for i in range(m):
    a,b = query[i]
    if a>=l_end:
        l_end = b
        ans+=1
print(ans)

Submission status: Accepted

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

l_end = -1
ans = 0
for i in range(m):
    a,b = query[i]
    if a+1>l_end:
        l_end = b
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
import heapq
import math
import fractions
import bisect
import itertools
from collections import Counter
from collections import deque
from operator import itemgetter
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,m=mp()
ab=sorted([lmp() 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:
def main():
    N,M = map(int, input().split())
    req = [[0,0] for i in range(M)]
    for i in range(M):
        a,b = map(lambda x:x-1, map(int, input().split()))
        req[i] = [b,a]
    # bの昇順にソートして小さいbから叶えていく
    req = sorted(req)
    ans = 1
    pos = req[0][0]-1
    for i in range(1,M):
        b,a = req[i]
        if pos<a:
            # できるだけ右の橋を取り除く
            ans += 1
            pos = b-1
    print(ans)

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:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from operator import itemgetter
N,M = map(int,readline().split())
m = map(int,read().split())
AB = zip(m,m)
AB = [(a,b) for a,b in AB]
AB.sort(key = itemgetter(1))
INF = 10 ** 18
prev_cut = -INF
cnt = 0
for a,b in AB:
    if a<=prev_cut:
        continue
    cnt += 1
    prev_cut = b-1
print(cnt)

Submission status: Accepted

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

li2=[input() for i in range(m)]
ab = []
for i in range(m):
    ab.append( [int(x.strip()) for x in li2[i].split()])

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

ans_last = ab[0][1]
ans = 1

for i in range(1,m):
    a = ab[i][0]
    b = ab[i][1]
    if b > ans_last and a >= ans_last:
        ans_last = b
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
bridge = [list(map(int, input().split())) for i in range(M)]
bridge = sorted(bridge, key = lambda x:x[1])
ans = 1
edge = bridge[0][1]
for i in range(1,M):
    if bridge[i][0] < edge:
        continue
    else:
        edge =bridge[i][1]
        ans += 1
print(ans)

Submission status: Accepted

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

N,M = list(map(int, input().rstrip().split()))
ab_list = [list(map(int, input().rstrip().split())) for i in range(M)]
#-----

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

prev_tail = -float("inf")
cnt = 0

for left,right in ab_list:
    if prev_tail <= left:
        cnt += 1
        prev_tail = right

print(cnt)

Submission status: Accepted

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

g_bridge_start = 0
g_bridge_end = 0
total = 0

for i in range(m):
    bridge_start = Island[i][0]
    bridge_end = Island[i][1] - 1
    #print(bridge_start, bridge_end, g_bridge_start, g_bridge_end)
    if bridge_start <= g_bridge_end:
        g_bridge_start = max(g_bridge_start, bridge_start)
        g_bridge_end = min(g_bridge_end, bridge_end)
    else:
        g_bridge_start = bridge_start
        g_bridge_end = bridge_end
        total += 1
print(total)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

n, m = map(int, input().split())
sg_list = []
for i in range(m):
    start, goal = map(int, input().rstrip().split())
    sg_list.append([start, goal])


# 区間スケジューリング
# 終端箇所でソート
sg_list.sort(key=lambda x: x[1])

break_bridge_num = 0
past_goal = 0

for sg in sg_list:
    start, goal = sg
    if start >= past_goal:
        past_goal = goal
        break_bridge_num += 1

print(break_bridge_num)

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

min_island = -float('inf')
ans = 0
for i in ab:
    if min_island <= i[0]:
        ans += 1
        min_island = i[1]
print(ans)

Submission status: Accepted

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

# print(array)
count = 0
position = -float("inf")
for i in range(M):
    if array[i][0] < position:
        pass
    else:
        position = array[i][1]
        count += 1
print(count)

Submission status: Accepted

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

left = 0
right = N
cnt = 0
for i,(a,b) in enumerate(AB):
    if right <= a:
        cnt += 1
        right = N
        left = 0

    left = max(a,left)
    right = min(b,right)

print(cnt+1)

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

Submission status: Accepted

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

ans = 1
now = line[0][1]
for s, g in line[1:]:
    if s >= now:
        ans += 1
        now = g
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

pairs.sort(key=lambda x: x[1])  # 右端の値でソート
current_right = 0
ans = 0
for (l, r) in pairs:
    if l >= current_right:
        current_right = r
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,M= map(int,input().rstrip().split())
island = []
for _ in range(M):
  a, b = map(int,input().rstrip().split())
  island.append((a,b))
end_sort = sorted(island,key = lambda x:x[1])
ans = 0
cut = -float('inf')
for i in range(M):
  if cut <= end_sort[i][0]:
    ans += 1
    cut = end_sort[i][1]
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
ab = [0] * m
for i in range(m):
    aa, bb = map(int, input().split())
    ab[i] = (aa, bb)

ab.sort()
ans = 1
prev_left, border = ab[0][0], ab[0][1]
for i in range(1, m):
    if prev_left == ab[i][0]:
        border = min(border, ab[i][1])
    else:
        if border <= ab[i][0]:
            ans += 1
            border = ab[i][1]
        prev_left = ab[i][0]
        border = min(border, ab[i][1])
print(ans)

Submission status: Accepted

Solution code:
import bisect
import collections
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

N,M = map(int,(input().split()))
c = []
bridge = []
nax = 0
for i in range(M):
    a,b = map(int,(input().split()))
    c.append((a,b))
c.sort(key=lambda x:x[1])

for i in range(M):
    if c[i][0] > nax:
        bridge.append(c[i][1]-1)
        nax = c[i][1]-1

print(len(bridge))

Submission status: Accepted

Solution code:
N, M = [int(s) for s in input().split()]
query = []
for _ in range(M):
    x, y = input().split()
    query.append((int(x), int(y)))

query = sorted(query, key=lambda x: x[1])
b_prev = 0
cnt = 0
for a, b in query:
    if b_prev <= a:
        cnt += 1
        b_prev = b

print(cnt)

Submission status: Accepted

Solution code:
import sys
N, M = map(int, sys.stdin.readline().rstrip().split())

bridge = [
    tuple(map(int,
              sys.stdin.readline().rstrip().split())) for _ in range(M)
]
bridge = sorted(bridge, key=lambda x: x[1])

ans = 0
t = 0
for a, b in bridge:
    if a >= t:
        ans += 1
        t = b
print(ans)

Submission status: Accepted

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

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

res = [lis[0]]
for i in range(1, m):
    if res[-1][0] < lis[i][1] and lis[i][0] < res[-1][1]:
        continue
    else:
        res.append((lis[i][0], lis[i][1]))
print(len(res))

Submission status: Accepted

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

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

ab.sort(key= lambda x: x[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 _ in range(m)]
ab.sort(key=lambda x:(x[1], x[0]))

ans = 0
pre_bridge = 0
for i in range(m):
    a, b = ab[i]
    if pre_bridge < a:
        ans += 1
        pre_bridge = b-1
print(ans)

Submission status: Accepted

Solution code:
# Segment tree
class SegmentTree():
    _data = []
    _offset = 0
    _size = 0

    def __init__(self, size):
        _size = size
        t = 1
        while t < size:
            t *= 2
        self._offset = t - 1
        self._data = [0 for _ in range(t * 2 - 1)]

    def update(self, index, value):
        i = self._offset + index
        self._data[i] = value
        while i >= 1:
            i = (i - 1) // 2
            self._data[i] = self._data[i * 2 + 1] + self._data[i * 2 + 2]

    def query(self, start, stop):
        result = 0
        l = start + self._offset
        r = stop + self._offset
        while l < r:
            if l & 1 == 0:
                result = result + self._data[l]
            if r & 1 == 0:
                result = result + self._data[r - 1]
            l = l // 2
            r = (r - 1) // 2
        return result


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

ab.sort(key=lambda x: x[1])
st = SegmentTree(N - 1)

result = 0
for a, b in ab:
    a, b = a - 1, b - 1
    if st.query(a, b) != 0:
        continue
    result += 1
    st.update(b - 1, 1)
print(result)

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

result = 0
t = -1
for a, b in ab:
    a, b = a - 1, b - 1
    if a <= t < b:
        continue
    result += 1
    t = b - 1
print(result)

Submission status: Accepted

Solution code:
from collections import namedtuple

def main():
    n,m = map(int,input().split())
    Req = namedtuple("Req","a b")
    requests = []
    for _ in range(m): #m個の要望
        a,b = map(int,input().split())
        requests.append(Req(a,b))

    requests.sort(key=lambda x:x.b)
    pre_cut = -1 #前回切断した端の左側の位置
    counter = 0 #切断の回数
    for i,req in enumerate(requests):
        if not req.a <= pre_cut < req.b:
            counter += 1
            pre_cut = req.b - 1
        else:
            continue
    print(counter)







if __name__ == '__main__':
    main()

Submission status: Accepted

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

sels = sorted(sels, key = lambda x:x[1])
start = sels[0][0]
end = sels[0][1]
ans = 1

for item in sels:
    if end <= item[0]:
        start = item[0]
        end = item[1]
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N, M =  map(int, input().split())
X = np.zeros([M,2], dtype=int)

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

col_num = 1
X = X[np.argsort(X[:, col_num])]
cnt = 1
r_min = X[0,1]
for i in range(1,M):
    if X[i,0] >= r_min:
        cnt += 1
        r_min = X[i,1]
print(cnt)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
h = []
for i in range(m):
    a, b = map(int, input().split())
    a, b = min(a, b), max(a, b)
    h.append((a,b))
h = sorted(h, key=lambda x: (x[0], x[1]))
r = 0
l = 0
cnt = 0
for a, b in h:
    if a >= r:
        cnt += 1
        l = a
        r = b
    elif b < r:
        r = b
    else:
        continue        
print(cnt)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
x=[[0 for i in range(2)] for i in range(M)]
for i in range(M):
  a,b=map(int,input().split())
  x[i][0]=b
  x[i][1]=a
x.sort()
count=0
bmax=-1
for i in range(M):
  if(bmax<=x[i][1]):
    count+=1
    bmax=x[i][0]
#print(x)
print(count)

Submission status: Accepted

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

ab = []

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

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

left = 0
ans = 0


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

Submission status: Accepted

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

query = []
bridge = [1 for _ in range(N-1)]

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

#街が左にある方を優先
query = sorted(query, key=lambda x: x[1])
#喧嘩する街が近い方を優先
# query = sorted(query, key=lambda x: x[2])

ans = 0
left = 0
for i, j in query:
    if left < i:
        left = j-1
        ans += 1

# print(bridge)
print(ans)

Submission status: Accepted

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

#入力
# s = input()
# n = int(input())
n,m = map(int, input().split())
# a = list(map(int,input().split()))
# a = [int(input()) for i in range()]

ab=[]
for i in range(m):
    a,b = map(int, input().split())
    ab.append((a,b))
ab = sorted(ab, key = lambda x: x[1])

     
def main():
    left = 0
    ans = 0
    for a,b in ab:

        if left < a:
            left = b-1
            ans +=1
    print(ans)


    
    

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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))
removed = -1
ans = 0

for a, b in ab:
    # a が removed より大きい = まだ取り除いてない
    if a > removed:
        removed = b - 1
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    N, M = map(int,input().split())
    ab = [None] * M
    for m in range(M):
        a, b = map(int,input().split())
        ab[m] = [a,b]
    ab.sort(key=lambda x:x[1])
    ret = 1
    TMP = ab[0][1]
    for x in ab[1:]:
        if TMP<=x[0]:
            TMP = x[1]
            ret += 1
    print(ret)

if __name__ == '__main__':
    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())
l=[]
l=sorted([list(map(int,input().split())) for i in range(m)],key=lambda x:x[1])
ans=1
now=l[0][1]-1

for x,y in l[1:]:
    if x<=now<=y-1:continue
    ans+=1
    now=y-1
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
AB = [lr() for _ in range(M)]
AB.sort(key=lambda x: x[1])
cur = 0
answer = 0
for a, b in AB:
    if a >= cur:
        answer += 1
        cur = b

print(answer)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
AB = [lr() for _ in range(M)]
AB.sort(key=lambda x: [x[0], x[1]])
cur = 0
answer = 0
for a, b in AB:
    if a >= cur:
        answer += 1
        cur = b
    if b < cur:
        cur = b

print(answer)

Submission status: Accepted

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

lists = []
for i in range(M):
    lists.append(list(map(int,input().split())))
lists.sort(key=lambda x: x[1])
ans = 0
min_b = 0
for a, b in lists:
    if min_b <= a:
        min_b = b
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m = (int(x) for x in input().split())

sec = []

for i in range(m):
    list = [int(i) for i in input().split()]
    list.reverse()
    sec.append(list)

sec.sort()
left = sec[0][0]
right = sec[0][1]
x = right - 1
ans = 0

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

print(ans)

Submission status: Accepted

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

sys.setrecursionlimit(10 ** 7)

# 1 ✕ N
N, M = list(map(int, input().rstrip().split()))

# N ✕ M
A = list(tuple(map(int, input().rstrip().split())) for _ in range(M))

array = []
for x, y in A:
    array.append((y, x))

array.sort()

ans = 0
t = 0
for e, s in array:
    if t <= s:
        ans += 1
        t = e

print(ans)

Submission status: Accepted

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

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

ans = 1
end = A[0][1]
for i in range(1,M):
    if A[i][0]>=end:
        ans += 1
        end = A[i][1]
print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline
from operator import itemgetter

def main():
    N, M = map(int, readline().rstrip().split())
    AB = [tuple(map(int, readline().rstrip().split())) for _ in range(M)]
    AB.sort(key=itemgetter(1))
    res = 1
    x = AB[0][1] - 2
    for a, b in AB[1:]:
        if a - 1 <= x:
            continue
        res += 1
        x = b - 2
    
    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
L = list()
for i in range(m):
    x, y = map(int, input().split())
    if x > y:
        x, y = y, x
    L.append([x, y])
L = sorted(L, key=lambda x: x[1])
A = L[0]
i = 1
for v in L:
    if v[0] >= A[1]:
        A = v
        i += 1
print(i)

Submission status: Accepted

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

Submission status: Accepted

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

for i in range(M): 
    flag = 1
    for bridge in bridges:
        if a[i][0] <= bridge and bridge < a[i][1]:
            flag = 0
            break 
    if flag:	bridges.append(a[i][1] - 1)   
print(len(bridges))

Submission status: Accepted

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

conflict.sort(key=lambda x: x[1])
count = 0
t = -1
for a,b in conflict:
    if t <= a:
        count += 1
        t = b
print(count)

Submission status: Accepted

Solution code:

n,m=map(int,input().split())
q=[]
import heapq
for i in range(m):
    a,b=map(int,input().split())
    heapq.heappush(q,(b,a))

largest=-10
c=0
while q:
    b,a=heapq.heappop(q)
    if largest-1<a:
        largest=b
        c+=1
print(c)

Submission status: Accepted

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

routes = []

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

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

cut = 0
ans = 0

for route in routes:
    if route[0] >= cut:
        cut = route[1]
        ans += 1

print(ans)

Submission status: Accepted

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

ans=0
cnt=0
while(1):
    if len(G[cnt])==0:
        cnt+=1
        continue
    m=min(G[cnt])
    break

while(1):
    cnt+=1
    if cnt>=N:
        break
    if cnt==m:
        #print(cnt,m)
        ans+=1
        while(1):
            if cnt==N:
                break
            if len(G[cnt])==0:
                cnt+=1
                continue
            m=min(G[cnt])
            break
    else:
        if len(G[cnt])==0:
            continue
        val=min(G[cnt])
        if val<m:
            m=val

print(ans)

Submission status: Accepted

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

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

cnt = 0
last = 0

for item in ablis:
    if item[0] >= last:
        cnt += 1
        last = item[1]

print(cnt)

Submission status: Accepted

Solution code:
a,b=map(int,input().split())
List=[]
for i in range(b):
  p,q=map(int,input().split())
  List.append([p,q])
List=sorted(List,key=lambda x:x[1])
ans=0
l=1
for i in range(b):
  if List[i][0]>=l:
    ans+=1
    l=List[i][1]
print(ans)

Submission status: Accepted

Solution code:
a,m = map(int,input().split())
hl = [tuple(map(int,input().split())) for i in range(m)]
hl.sort()
l,r = -1,a+1
c = 0
for i in hl:
  l = i[0]
  r = min(r,i[1])
  if l >= r:
    c += 1
    r = i[1]
print(c+1)

Submission status: Accepted

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

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

cnt = 1
for i in range(1,M):
  if remove[i-1][1] > remove[i][0]:
    remove[i][1] = remove[i-1][1]
  else:
    cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
import numpy as np

n,m = map(int,input().split())
arr = np.array([list(map(int,input().split())) for i in range(m)])
arr = arr[ arr[:,1].argsort(), :] #各行の1列目だけみて、行インデックスをソート
A = arr.T[0]
B = arr.T[1]

ans = 0
start,end = 0,0
for a,b in zip(A,B):
    if a < end: continue
    start,end = a,b
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

n,m = map(int,input().split())
arr = np.array([list(map(int,input().split())) for i in range(m)])
arr = arr[ arr[:,1].argsort(), :] #各行の1列目だけみて、行インデックスをソート


ans = 0
start,end = 0,0
for ab in arr:
    a,b = ab[0],ab[1]
    if a < end: continue
    start,end = a,b
    ans += 1

print(ans)

Submission status: Accepted

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


def main():
    n, m = map(int, input().split())
    data = [list(map(int, input().split())) for _ in range(m)]
    rule = [[] for _ in range(n)]
    for i in range(m):
        rule[data[i][0] - 1].append(data[i][1])
        rule[data[i][1] - 1].append(data[i][0])
    res = rule[0][:]
    ans = 0
    for j in range(n - 1):
        if j + 2 not in res:
            res.extend(rule[j + 1])
        else:
            ans += 1
            res = rule[j + 1][:]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
il = []
for i in range(m):
  a,b = map(int,input().split())
  il.append([a,b])
il = sorted(il,key = lambda x:x[1])
count = 0

brr = -99999
for i in range(m):
  if il[i][0] >= brr:
    count += 1
    brr = il[i][1]
print(count)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
n,m=map(int,input().split())
a=sorted([tuple(map(int,input().split())) for _ in range(m)])
i=0
cnt=0
k=n
while i<m:
    k=a[i][1]
    if a[i][0]<k:
        while i<m and a[i][0]<k:
            k=min(k,a[i][1])
            i+=1
    if i<m and a[i][0]>=k:
        cnt+=1
    else:
        cnt+=1
        i+=1
print(cnt)

Submission status: Accepted

Solution code:
#この方法だとTLEになるためNG

from pprint import pprint
from copy import deepcopy

#N <= 10**5なので、全探索はNG
#Greedyでいける？


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

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

#区間スケジュール問題と考え、終端が小さい順で並べる。その後Greedyで計算。
requests = sorted(requests, key=lambda x:x[1])

counter = 0
before_point = -float('inf')

#pprint(requests)

for i in range(m):
    if requests[i][0] >= before_point:
        counter += 1
        before_point = requests[i][1]
        #print("requests[{}]={} YES".format(i,requests[i]))
    else:
        #print("requests[{}]={} NO".format(i,requests[i]))
        pass

print(counter)

Submission status: Accepted

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

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