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:
# https://atcoder.jp/contests/abc103/tasks/abc103_d
# D - Islands War

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

for _ in range(m):
    a, b = list(map(int, input().split()))
    ab_list.append((a, b))

# 区間が被っている場合は、一括で分けられる
# 区間が被っていない場合は、個別に分ける必要がある
# 区間が被っている個数を数えればよいはず

# 最小の区間を調べる
# bの1個前なら絶対切れる
ab_list = sorted(ab_list, key=lambda x: (x[1]))
# print(ab_list)
i = 0
count = 0

while i < len(ab_list):
    count += 1

    a, b = ab_list[i]
    diff_index = 1
    end_index = b

    debug_list = [(a, b)]

    if (i + diff_index) >= len(ab_list):
        break

    # 次の区間について
    while ab_list[i + diff_index][0] < end_index:
        # debug_list.append(ab_list[i + diff_index])

        diff_index += 1

        if (i + diff_index) >= len(ab_list):
            break

        # if ab_list[i + diff_index][1] < end_index:
        #     end_index = ab_list[i + diff_index][1]

    # print('==========')
    # print(debug_list)

    i = i + diff_index

print(count)

Submission status: Accepted

Solution code:
import sys
INPUT = lambda: sys.stdin.readline().rstrip()
MAP = lambda: map(int, INPUT().split())
sys.setrecursionlimit(10 ** 9)


def main():
    N, M = MAP()
    AB = sorted([list(MAP()) for _ in range(M)], key=(lambda x: x[1]))

    point = cnt = 0
    for (a, b) in AB:
        if a > point:
            point = b - 1
            cnt += 1

    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from operator import itemgetter

n,m = list(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:
        ans += 1
        removed = b-1
print(ans)

Submission status: Accepted

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

conflict = [0] * M

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

conflict = sorted(conflict, key=lambda x: x[0])

used = [False] * M
count = 0

for m in range(M):
    if not used[m]:
        head, tail = conflict[m]
        used[m] = True

        j = m + 1
        while j < M:
            h, t = conflict[j]
            if tail <= h:
                break
            else:
                tail = min(tail, t)
                used[j] = True
            j += 1
        count += 1

print(count)

Submission status: Accepted

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

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

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

#print(bridges)
count=1
done=[intervals[0]]

for interval in intervals:
	#print(interval)
    # we cut the last bridage of last processed interval
	if not interval[0] < done[-1][1]:
		count += 1
		done.append(interval)	
#print(done)
print(count)

Submission status: Accepted

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

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

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

#print(bridges)
count=1
done=[intervals[0]]

for interval in intervals:
	#print(interval)
	if not interval[0] < done[-1][1]:
		count += 1
		done.append(interval)	
#print(done)
print(count)

Submission status: Accepted

Solution code:
from bisect import bisect_left

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

cutted = [-1]
for i in range(M):
    a, b = ab[i]
    if a <= cutted[-1]:
        continue
    cutted.append(b-1)
print(len(cutted)-1)

Submission status: Accepted

Solution code:
from bisect import bisect_left

N, M = map(int, input().split())
ab = [0]*M
for i in range(M):
    ab[i] = tuple(map(int, input().split()))
ab.sort()


used = [False]*M
count = 0
for i in range(M):
    if used[i]:
        continue
    head, tail = ab[i]
    used[i] = True
    j = i+1
    while j < M:
        h, t = ab[j]
        if tail <= h:
            break
        tail = min(tail, t)
        used[j] = True
        j += 1
    count += 1
print(count)

Submission status: Accepted

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

N, M = map(int, input().split())
L = [[int(v) - 1 for v in input().split()] for _ in range(M)]

L.sort(key = lambda x:(-x[1], -x[0]))

ans = 0
k = 0
bx = L[0][0]
for i in range(M):
    x, y = L[i]
    if bx < y:
        k += 1
        if bx <= x:
            bx = x
        continue
    else:
        ans += 1
        if i == M - 1:
            k = 1

        bx = x

print(ans + (1 if k != 0 else 0))

Submission status: Accepted

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

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

removed_bridge = []
for ab in AB_sorted:
    if removed_bridge:
        if ab[0] < removed_bridge[-1] < ab[1]:
            continue
    removed_bridge.append(ab[1] - 0.5)

print(len(removed_bridge))

Submission status: Accepted

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

ans = 0
lmax = 0
rmin = 10**9
for x in ab:
    a = x[0]
    b = x[1]
    if rmin <= a:
        ans += 1
        lmax = 0
        rmin = 10 ** 9
    if lmax < a:
        lmax = a
    if b < rmin:
        rmin = b
print(ans+1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
#sys.setrecursionlimit(10 ** 9)
import math
import heapq

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

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

num = 0
loc = 0
for i in range(M):
	if loc < areas[i][1]:
		num += 1
		loc = areas[i][0]

print(num)

Submission status: Accepted

Solution code:
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
Mod = 1000000007




def main(): #startline--------------------------------------------
    N,M = map(int,input().split())
    AB = [list(map(int,input().split())) for i in range(M)]
    AB.sort(key = lambda x:x[1],reverse = True)
    l = AB[0][0]
    r = AB[0][1]
    ans = 1
    for i in range(1,M):
        if r <= AB[i][0] or l >= AB[i][1]:
            ans += 1
            l = AB[i][0]
            r = AB[i][1]
        else:
            l = max(AB[i][0],l)
            r = AB[i][1]

    print(ans)
if __name__ == "__main__":
    main() #endline===============================================





def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n < 2 is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))):
        if prime[i] == 1:
            for j in range(2*i,n):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n):
        if prime[i] == 1:
            res.append(i)
    return res

class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py

    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)

Submission status: Accepted

Solution code:
import heapq

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

Bri = [[] for _ in range(N+1)]
for a, b in AB:
    Bri[a].append(b)

q = []
ans = 0
for j in range(1, N+1):
    if q:
        if q[0] == j:
            q = []
            ans += 1
    for p in Bri[j]:
        heapq.heappush(q, p)
print(ans)

Submission status: Accepted

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

ab.sort(key=lambda x:x[1])
#print(ab)
split=[0,]

#while len(ab)!=0:
for item in ab:
  if (item[1]-split[-1]>0 and item[0]-split[-1]<=0)!=True:
    split.append(item[1]-1)
  
  #print(ab)
print(len(split)-1)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab = sorted(tuple(map(int, input().split())) for _ in range(m))
s = n + 1
ret = 0
for a, b in ab:
    if s <= a:
        ret += 1
        s = n + 1
    s = min(s, b)
if s != n + 1:
    ret += 1
print(ret)

Submission status: Accepted

Solution code:
from functools import reduce
from operator import itemgetter

N, M = map(int, input().split())
a, b = (
    zip(*(map(int, input().split()) for _ in range(M))) if M else
    ((), ())
)

# bについてソートし、橋を取り除く必要があれば可能な限り東の橋を取り除く
ans, _ = reduce(
    lambda acc, q: (
        (acc[0] + 1, q[1]) if q[0] >= acc[1] else
        acc
    ),
    sorted(zip(a, b), key=itemgetter(1)),
    (0, 0)
)

print(ans)

Submission status: Accepted

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

war = [float('inf')]*N

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

ans = 0
cat = float('inf')
for i in range(N):
    if i == cat:
        ans += 1
        cat = float('inf')
    cat = min(cat,war[i])
print(ans)

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])
count = 0

del_num = 0
for i in range(M):
  if ab[i][0] >= del_num:
    count += 1
    del_num = ab[i][1]
print(count)

Submission status: Accepted

Solution code:
sortsecond = lambda val: val[1]
N, M = map(int, input().split())
l=[]
for i in range(M):
    t=input().split()
    l.append((int(t[0]),int(t[1])))
l.sort(key=sortsecond)
ans = int(0)
count = int(0)
br = int(0)


for i in range(M):
    if br<l[i][0]+1:
        count +=1
        br = l[i][1]

ans = count
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter

N, M = map(int,input().split())
demand = [list(map(int,input().split())) for _ in range(M)]
demand.sort(key=itemgetter(1))
x = 1
b = demand[0][1]

for i in range(1, M):
    if demand[i][0] < b:
        pass
    else:
        x += 1
        b = demand[i][1]

print(x)

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])
tmp = ab[0][1]-1
ans = 1
for i in range(1,M):
  if ab[i][0] <= tmp:
    continue
  else:
    ans += 1
    tmp = ab[i][1]-1
print(ans)

Submission status: Accepted

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

ab.sort()

l = ab[0][0]
r = ab[0][1]
ans = 1

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

print(ans)

Submission status: Accepted

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

sort_ab = sorted(AB, key=lambda x: x[1])
cur_max = 0
cnt = 0
for el in sort_ab:
  if el[0] >= cur_max:
    cnt += 1
    cur_max = el[1]
print(cnt)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a_list = []
for _ in range(m):
    a, b = map(int, input().split())
    a_list.append([a, b])
a_list.sort(key = lambda x: (x[1], x[0]))
temp = -1
ans = 0
for a, b in a_list:
    if (temp < a):
        temp = b - 1
        ans += 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 ab: ab[1])
removed = list()
for a, b in AB:
    if len(removed) == 0:
        removed.append(b - 1)
    elif a <= removed[-1] < b:
        continue
    else:
        removed.append(b - 1)
print(len(removed))

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import bisect

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

def LI(): return list(map(int, sys.stdin.readline().split()))

N,M = LI()
ab = [[] for i in range(M)]
for i in range(M):
    a,b = LI()
    a -= 1
    b -= 1
    ab[i] = [a,b]


ans = 0
ab = sorted(ab,key = lambda x:x[1])
ans += 1
a,b = ab[0]
cutting = b-1
for i in range(1,M):
    a,b = ab[i]
    if a <= cutting < b:
        pass
    else:
        cutting = b-1
        ans += 1

print(ans)

# print(ab)

Submission status: Accepted

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

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

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

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

last_break = 0
ans = 0
for ab in ab_array:
    a, b = ab
    if last_break >= a:
        continue
    last_break = b - 1
    ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
AB = [tuple(map(int, input().split())) for m in range(M)]
AB = sorted(AB, key=lambda x: x[1])
ans = 0
prev = 0
for a, b in AB:
    if ans > 0 and a <= prev:
        pass
    else:
        ans += 1
        prev = b-1
print(ans)

Submission status: Accepted

Solution code:
# ABC103D_IslandsWar.py

import operator

"""
区画スケジューリング
まず、(ai, bi) の組を bi について昇順にソートし、以下を行う
• 既にその要望を満たしている場合、何もしない
• 要望を満たしていない場合、bi − 1 番目と bi 番目を接続する橋を取り除く

TLE に注意
bridges[-1] == max(bridges), ms[i][0] == min(ms) という事実を使う
ジェネレータ表記は必ずしも使わなくてもよい
"""

n, m = map(int, input().split())
bridges = [0]
ms1 = (tuple(map(int, input().split())) for i in range(m))
ms2 = sorted(ms1, key=operator.itemgetter(1))

for i in range(m):
    if ms2[i][0] <= bridges[-1]:
        pass
    else:
        bridges.append(ms2[i][1] - 1)

if __name__ == "__main__":
    print(len(bridges)-1)    # 0 の分を除く

Submission status: Accepted

Solution code:
# ABC103D_IslandsWar.py

import operator

"""
区画スケジューリング
まず、(ai, bi) の組を bi について昇順にソートします。ソートした順に、以下を行う。
• 既にその要望を満たしている場合、何もしない。
• 要望を満たしていない場合、bi − 1 番目の島と bi 番目の島を接続する橋を取り除く。
TLE に注意
"""

n, m = map(int, input().split())
bridges = [0]
ms = sorted((tuple(map(int, input().split())) for i in range(m)), key=operator.itemgetter(1))

for i in range(m):
    if ms[i][0] <= bridges[-1]:
        pass
    else:
        bridges.append(ms[i][1] - 1)

if __name__ == "__main__":
    print(len(bridges)-1)

Submission status: Accepted

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

def ri():
    return int(input())

def rl():
    return list(input().split())

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

def main():
    n, m = rli()
    edges = []
    for _ in range(m):
        a, b = rli()
        edges.append((a, b))
    edges.sort(key=lambda x:x[1])
    ans = 0
    left = 0
    for e in edges:
        if e[0] <= left:
            continue
        ans += 1
        left = e[1]-1
    #     print(ans, e[0], left)
    # print(edges)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np


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

demands = [0]*M
for i in range(0, M):
    demands[i] = list(map(int, input().split()))

demands = np.array(demands)

arr = np.argsort(demands, axis=0) # 列でsort
lvl = arr[:,1] # 1列目を取得（終了時間が早い順のindexを取得）

start = 1
end = 1
cnt = 0
for i in lvl:    
    # 既に切られている範囲にいるならskip
    if demands[i][0] < end:
        continue
    
    # 今までで切れていない場合は新しく切る
    end = demands[i][1]
    cnt += 1
        
print(cnt)

Submission status: Accepted

Solution code:
n,m=map(int, input().split()) 
s=[list(map(int, input().split())) for i in range(m)]
s.sort(key = lambda x:x[1])
x=[0]
count=0
for i in range(m):
    if s[i][0]<=x[-1]:
        pass
    else:
        x.append(s[i][1]-1)
        count+=1
print(count)

Submission status: Accepted

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

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

i = 0
count = 1
b1=ab[0][1]
a1=ab[0][0]
while i < m:
    if ab[i][0]>=b1:
        count += 1
        b1 = ab[i][1]
    else:
        b1 = min(b1,ab[i][1])
    i += 1
print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
#ABC103 D

import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7

n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]
ab = sorted(ab,key = itemgetter(1))
x = 0
ans = 0
for a,b in ab:
    if a >= x:
        x = b
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
N,M = map(int,input().split())
graph = [[int(i) for i in input().split()] for _ in range(M)]
graph.sort(key=itemgetter(1))
ans = 0
cut = 0

for i in range(M):
    if cut < graph[i][0]:
        cut = graph[i][1] -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[0])
x = n
l = 0
for a, b in reversed(AB):
  if b > x :
    continue
  else:
    x = a
    l += 1
    
print(l)

Submission status: Accepted

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

x.sort(key=lambda x: x[1])
res = 0
right = 0
for i in range(M):
    if x[i][0] >= right:
        right = x[i][1]
        res += 1

print(res)

Submission status: Accepted

Solution code:
# ABC103 D-Islands War

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

for i, j in enumerate(ab):
    if i == 0:
        ans += 1
        temp = j[1] - 1
    else:
        if j[0] <= temp:
            continue
        else:
            ans += 1
            temp = j[1] - 1
            
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

war = []

for _ in range(M) :
    A, B = map(int, input().split())
    war.append((A,B))

war.sort(key=lambda A : A[0])

ans = 1
left, right = war[0]

for i in range(1, M) :
    A, B = war[i]
    if right <= A :
        ans += 1
        left = A
        right = B
        continue
    left = A
    right = min(right, B)

print(ans)

Submission status: Accepted

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

def minpair(A,B):
    if A[1] <= B[0]:
        C = []
    elif B[0] < A[1] <= B[1]:
        C = [B[0],A[1]]
    else:
        C = B
    return C

Bridge.sort(key=lambda x: x[0])
c = 0
ans = 0
while c <= M-2:
    Temp = minpair(Bridge[c],Bridge[c+1])
    if Temp == []:
        ans += 1
    else:
        Bridge[c+1] = Temp
    c += 1
print(ans+1)

Submission status: Accepted

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

def main():
    N, M = map(int, input().split())
    ab = sorted([list(map(int, input().split())) for i in range(M)], key = lambda x:x[1])
    count = 0
    break_ = -1
    for a, b in ab:
        a -= 1; b -= 1;
        if a > break_:
            count += 1
            break_ = b-1
    print(count)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np

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

dtype = [('start', int), ('end', int)]
req = np.empty([M], dtype=dtype)

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

req.sort(order=['end'])

cutList = []

def isConnected(start, end):
    for i in cutList:
        if start <= i and i < end:
            return False
    return True

ans = 0

for i in range(M):
    if isConnected(req[i][0], req[i][1]):
        cutList.append(req[i][1]-1)
        ans += 1

print(ans)

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))
t = 0
ans = 0
table.sort(key=itemgetter(1))
for a,b in table:
  if t < a:
    ans += 1
    t = b-1
print(ans)

Submission status: Accepted

Solution code:
import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

N, M = [int(x) for x in input().split()]
AB = []
for _ in range(M):
    a, b = [int(x) for x in input().split()]
    AB.append((a - 1, b - 2))

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

cnt = 0
i = 0
while i < len(AB):
    cut = AB[i][0]
    while i < len(AB) and AB[i][1] >= cut:
        i += 1
    cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
from operator import itemgetter

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

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

es.sort(key=itemgetter(1))

ans = 0
last_cut = -1
for a, b in es:
    if a <= last_cut < b:
        continue
    last_cut = b - 1
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

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

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

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

heap = []

ans = 0
for a, b in AB:
    if heap and a >= heap[0]:
        heap = []
        ans += 1
    heapq.heappush(heap, b)
if heap:
    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)]

ba = []
for i in range(M):
    ba.append([ab[i][1], ab[i][0]])
ba.sort() # sorted on b

ans = 0
t = 0
for i in range(M):
    if t <= ba[i][1]:
        ans += 1
        t = ba[i][0]
print(ans)

Submission status: Accepted

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

BA.sort()

cnt = 0
end = 0
for ba in BA:
    b, a = ba
    if a > end:
        cnt += 1
        end = b - 1

print(cnt)

Submission status: Accepted

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

import numpy as np

d2=np.array(d)

#d3=d2[np.argsort(d2[:,1])][::-1]
d3=d2[np.lexsort(d2.T)][::-1]
#print(d3)

cnt=1
i=0

while i<n:
	j=i+1
	st=d3[i][0]
	while j<n:
		if d3[j][1]<=st:
			#print(d3[i][0])
			#print(d3[j][1])
			#print(i)
			#print(j)            
			cnt+=1
			i=j-1
			j=n-1
		if st<d3[j][0]:
			st=d3[j][0]
		j+=1
	i+=1
print(cnt)

Submission status: Accepted

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

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

removed = []

for a,b in AB:
    if len(removed) == 0:
        removed.append(b - 1)
    elif max(removed) < a:
        removed.append(b - 1)

print(len(removed))

Submission status: Accepted

Solution code:
# 2019/07/02

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

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

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

pre=0
cnt=0
for i in range(m):
    if pre<=ab[i][0]:
        pre=ab[i][1]
        cnt+=1
    else:
        pre=min(pre,ab[i][1])
print(cnt)

Submission status: Accepted

Solution code:
# 写経

n,m=map(int,input().split())
ab=[]

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

sep=[0]*n

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

ans=0
pre=0

for i in range(m):
    if pre<=ab[i][0]:
        ans+=1
        pre=ab[i][1]
    else:
        pre=min(pre,ab[i][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))
    
ab.sort()

ans = 0
b_prev = 0

for i in range(M):
    if b_prev <= ab[i][0]:
        ans += 1
        b_prev = ab[i][1]
    else:
        b_prev = min(b_prev, ab[i][1])
    
print(ans)

Submission status: Accepted

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

check = [B[0][1]-1]

for a, b in B:
    if a <= check[-1]:
        continue
    check.append(b-1)
print(len(check))

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

Submission status: Accepted

Solution code:
from sys import stdin

input=[int(x) for x in stdin.readline().rstrip().split()]
N=input[0]
M=input[1]

order_list=[]
for m in range(M):
    order_list.append([int(x) for x in stdin.readline().rstrip().split()])

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

a=0
b=0
output=0
for i in order_list:
    a=i[0]
    if a>=b:
        output+=1
        b=i[1]
print(output)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
b=[]
for i in range(m):
    b.append(list(map(int,input().split())))
b.sort(key=lambda x:x[1])
time=0
count=0
for k in range(len(b)):
    if b[k][0]>=time:
                time=b[k][1]
                count+=1
print(count)

Submission status: Accepted

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

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

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


ans = 1
s, g = e[0]

for i in range(1, M):

    # 直近で最も小さい終点と、現在の始点を比較する
    if e[i][0] < g:
        continue
    else:
        g = e[i][1]
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N, M = LI()
ab = LIR(M)

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

before = 0
ans = 0
for ai, bi in ab:
    if (ai <= before):
        continue
    else:
        ans += 1
        before = bi-1
print(ans)

"""
left = [0]*N
right = [0]*N

for ai, bi in ab:
    left[ai-1] = 1
    right[bi-1] = 1

l = N-1
r = N-1
ans = 0

flag = False
while (l>=0):
    if (left[l]):
        while (r>l):
            if (right[r]):
                flag = True
            r -= 1
        if (flag):
            ans += 1
            flag = False
    l -= 1

print(ans)
"""

Submission status: Accepted

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

e.sort(key=lambda x:x[1])
ret = 0


l = 0
for i in range(m):
    if e[i][0] < l:
        continue
    else:
        l = e[i][1]
        ret += 1
    
print(ret)

Submission status: Accepted

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

Schedule = sorted(Schedule, key=lambda x: x[1])
cnt = 0
before_end = 0
for task in Schedule:
    start = task[0]
    end = task[1]
    if start < before_end:
        continue
    cnt += 1
    before_end = end
print(cnt)

Submission status: Accepted

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

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

ans = 0
now = -1

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

for i in range(m):
    if li[i][0] <= now and li[i][1] > now:
        pass
    else:
        ans += 1
        now = li[i][1] - 1

print(ans)