Problem:


Score : 400 points

Problem Statement

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

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

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

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

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

Find the minimum number of bridges that must be removed.

Constraints

All values in input are integers.

2 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq a_i < b_i \leq N

All pairs (a_i, b_i) are distinct.

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
a_2 b_2
:
a_M b_M

Output

Print the minimum number of bridges that must be removed.

Sample Input 1

5 2
1 4
2 5

Sample Output 1

1

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

Sample Input 2

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

Sample Output 2

2

Sample Input 3

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

Sample Output 3

4



Sample input:
5 2
1 4
2 5


Sample output:
1

Submission status: Accepted

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

s, t = list(), list()

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

time = list()
for i in range(m):
    time.append([s[i], t[i]])

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

ans = 0
now_end = 0

for i in range(0, m):
    if now_end <= time[i][0]:
        ans += 1
        now_end = time[i][1]

print(ans)

Submission status: Accepted

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

#取り除く橋は西側が出来るだけ大きいやつから取り除いても無駄がない
#（なぜならそうでない橋を取り除いた後にも上の橋を取り除かねばならないので）
N,M = map(int,input().split())
ab =[list(map(int,input().split())) for i in range(M)]
ab.sort(reverse=True)
ans = 0
tmp = inf
for i in range(M):
    if ab[i][1] > tmp:
        continue
    else:
        ans += 1
        tmp = ab[i][0]
print(ans)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc103/tasks/abc103_d
import sys

def solve():
    pairs.sort(key=lambda pair: pair[1])
    cnt = 0
    base = 0
    for (a, b) in pairs:
        if a >= base:
            cnt += 1
            base = b
    return cnt

n, m = map(int, input().split())
pairs = [tuple(int(c) for c in input().split()) for _ in range(m)]
print(n, pairs, file=sys.stderr)
print(solve())

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
need=[tuple(map(int,input().split())) for i in range(M)]
need.sort(key=lambda x:x[0])
ans=0
bef=0
for a,b in need:
    if a<=bef:
        bef=min(b-1,bef)
    else:
        ans+=1
        bef=b-1
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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])
# print(bridge)

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

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.sort()
ab += [[n, n + 1]]
ans = 0
s = 0
f = n

for i in range(m + 1):
    if ab[i][0] >= f:
        ans += 1
        s = ab[i][0]
        f = ab[i][1]
    else:
        if ab[i][1] < f:
            f = ab[i][1]
print(ans)

Submission status: Accepted

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


def solve(N: int, M: int, a: "List[int]"):
    a.sort(key=lambda x: x[1])
    ret = 1
    cur = a[0][1]
    for t in a:
        if t[0] >= cur:
            ret += 1
            cur = t[1]
    print(ret)
    return


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

if __name__ == '__main__':
    main()

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

fights = AB[:]

fights = sorted(fights, reverse=True)

import bisect


bridges = []
for a,b in fights:
    a_position = bisect.bisect(bridges, a)
    b_position = bisect.bisect(bridges, b)
    
    if a_position == b_position:
        bisect.insort(bridges, a+1)
        #print(bridges)

print(len(bridges))

Submission status: Accepted

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


###############################################################################


def main():
    n, m = intin()
    ablist = intinl(m)

    ablist.sort()
    candidates = []

    for a, b in ablist:
        if not candidates:
            candidates.append((a, b - 1))
            continue
        ca, cb = candidates[-1]
        if a <= cb:
            candidates[-1] = (max(a, ca), min(b - 1, cb))
            continue
        candidates.append((a, b - 1))

    print(len(candidates))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
b_list=[]
INF=10**6
for i in range(n):
    b_list.append(INF)
for i in range(m):
    a,b=map(int,input().split())
    b_list[a-1]=min(b-1,b_list[a-1])
end=INF
count=0
for i in range(n):
    if b_list[i]==INF:
        pass
    else:
        if i>=end:
            count=count+1
            end=b_list[i]
        else:
            end=min(end,b_list[i])
print(count+1)

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 a:a[1])
last = -1
ans = 0
for a in A:
    if last < a[0]:
        last = a[1] - 1
        ans += 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 = sorted(L,key=lambda x:x[1])
now = -10
cnt = 0
for x in L:
    if now < x[0]:
        now = x[1] - 0.5
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
L = []
for _ in range(M):
    L.append(list(map(int,input().split())))
L = sorted(L,key=lambda x:x[1])
now = -10
cnt = 0
for x in L:
    if now <= x[0]:
        now = x[1]
        cnt += 1
print(cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

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

cuts = [bridge[0][1]]
for b in bridge[1:]:
    cut = cuts[-1]
    if b[0]< cut <= b[1]:
        continue
    cuts.append(b[1])

# print(cuts)
print(len(cuts))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#coding:utf-8
N,M=map(int,raw_input().split())
P=[]
for i in range(M):
    a,b=map(int,raw_input().split())
    P.append((a,b))
P.sort()
ans=0
l=-1
r=-1
for a,b in P:
    if r<=a:
        ans+=1
        l=a
        r=b
        continue
    l=a
    r=min(b,r)
print(ans)

Submission status: Accepted

Solution code:
import sys

def main():
    num, younou = map(int, input().split())

    data = [list(map(int, input().split())) for i in range(younou)]
    data.sort(key=lambda x: x[1])

    ans = 0
    now_value = 1
    for ele in data:
        if ele[0] >= now_value:
            now_value = ele[1]
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# Input
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

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

n,m = li()
ab = []
for _ in range(m):
    ai, bi = li_()
    ab.append((ai, bi))

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

ans = 0
cur = -1
for ai, bi in ab:
    if ai >= cur:
        ans += 1
        cur = bi

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
l = [0]*m
for i in range(m):
  a, b = map(int, input().split())
  l[i] = [b, a]
l.sort()

ans = 0
x = 0
for i in range(m):
  if x < l[i][1]:
    ans += 1
    x = l[i][0] -1
print(ans)

Submission status: Accepted

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

divide_list = [war_list[0][1]]
for i in range(1,M):
    if  war_list[i][0] < divide_list[-1]:
        pass
    else:
        divide_list.append(war_list[i][1])
    
print(len(divide_list))

Submission status: Accepted

Solution code:
# 問題 https://atcoder.jp/contests/abc103/tasks/abc103_d

# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


N, M = read_ints()

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

from operator import itemgetter

AB.sort(key=itemgetter(1))  # リスト1は2次元以の配列

# . - . - . - .

i = -1  # いま考慮している島の位置
ans = 0
for a, b in AB:
    # zero-based index
    a -= 1
    b -= 1
    if a < i:
        # 考えなくてもいい(もう満たしている)要望は飛ばす
        # 同じ島からスタートする橋は許容できるので<=ではなく<
        continue
    ans += 1
    i = b

print(ans)

Submission status: Accepted

Solution code:
N,M = list(map(int,input().split(' ')))
 
abp = []
 
for i in range(M):
	a,b = list(map(int,input().split(' ')))
	abp.append([a,b])
 
abp.sort(key=lambda x:x[1])
 
ep = 0
ans = 0 
for a,b in abp:
	if a >= ep:
		ep = b
		ans = 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)]

ans = 0
ab = sorted(ab, key=lambda x: x[1])
n = 0
for i in range(M):
    if ab[i][0] >= n:
        n = ab[i][1]
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m = [ int (it ) for it in input().split() ]
lip =[]
lia =[ [] for i in range(n)]
lib =[ [] for i in range(n)]
for i in range(m):
  a,b = [ int(it)-1 for it in input().split() ]
  lip.append((a,b))
  lia[a].append(b)
  lib[b].append(a)


anow = 0
bnow = 0
mi = 1000000
s = 0
for i in range(n):
  #print (mi)
  if (len(lia[i])>0):
    _mi = min(lia[i])
    mi = min(_mi,mi)
  if (i==mi):
    s+=1
    #print ("+",i)
    if (len(lia[i])>0):
      mi = min(lia[i])
    else:
      mi = 1000000
print (s)

Submission status: Accepted

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

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

lst.sort()

count = 0
position = 0

for i in range(M):
    if position <= lst[i][1]:
        count += 1
        position = lst[i][0]
        
print(count)

Submission status: Accepted

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

from operator import itemgetter
AB.sort(key = itemgetter(1))

temp = 0
ans = 0
for a,b in AB:
    if b != temp and a >= temp:
        ans += 1
        temp = b
print(ans)

Submission status: Accepted

Solution code:

n, m = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(m)]
ab.sort(key=lambda x:x[1])
ans = 0
endplace = 0
for ai, bi in ab:
    if endplace <= ai:
        endplace = bi
        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 x:x[1])
# print(ab)

ans = 0
endtime = 0
for ai,bi in ab:
    if endtime <= ai:
        endtime = bi
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N,M = list(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
m = 0
for a,b in ab:
    if a<m:
        continue
    ans += 1
    m = b
print(ans)

Submission status: Accepted

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


def solve(N: int, M: int, P: "List[List[int]]"):
    fallen = -1
    count = 0
    P.sort(key=lambda p: p[1] * N - p[0])
    for p in P:
        if fallen==p[1]-1:
            continue
        if p[0] <= fallen:
            continue
        fallen = p[1]-1
        count += 1
    print(count)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    P = [[int(), int()] for _ in range(M)]   # type: "List[List[int]]" 
    for i in range(M):
        P[i] = [int(next(tokens)), int(next(tokens))]
    solve(N, M, P)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

pairs = []

for _ in range(M):
  pairs.append([int(x) for x in input().split()])

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

right_most = 0 # 最後に破壊されている場所（右のindex）

cnt = 0
for a,b in pairs:
  if a < right_most:
    continue
  cnt += 1
  right_most = b

print(cnt)

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
inlist = [tuple([int(st) for st in input().split()]) for i in range(M)]
inlist.sort()
res=0
minright=100000000000
for fr, to in inlist:
    if to < minright: minright = to
    if minright <= fr:
        res += 1
        minright = to
print(res+1)

Submission status: Accepted

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

res=0
minright=100000000000
for fr, to in inlist:
    if to < minright:
        minright = to
    if minright <= fr:
        res += 1
        minright = to
    # print("minr: {}".format(minright))

print(res+1)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
Y=[list(map(int,input().split())) for i in range(M)]
Y.sort(key=lambda x:x[1])
K=1
x=Y[0][1]
for a,b in Y[1:]:
    if a+1>x:
        x=b
        K+=1
print(K)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
N, M = map(int, input().split(" "))
ab = np.array([[int(i) for i in input().split(" ")] for _ in range(M)])

ab_sort = ab[np.argsort(ab[:,1])]
ans = 0
nb = -1
for a, b in ab_sort:
    if a >= nb:
        ans += 1
        nb = b
print(ans)

Submission status: Accepted

Solution code:
import functools

import os
import sys

sys.setrecursionlimit(10000)
INF = float('inf')


def debug(fn):
    if not os.getenv('LOCAL'):
        return fn

    @functools.wraps(fn)
    def wrapper(*args, **kwargs):
        ret = fn(*args, **kwargs)
        print('DEBUG: {}({}) -> '.format(
            fn.__name__,
            ', '.join(
                list(map(str, args)) +
                ['{}={}'.format(k, str(v)) for k, v in kwargs.items()]
            )
        ), end='')
        print(ret)
        return ret

    return wrapper


N, M = map(int, input().split())
# reqs[i]: i 番目の島から行けないようにしたい、最小の島番号 (i < reqs[i])
reqs = [INF for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    reqs[a] = min(reqs[a], b)

ans = 0
# 最後に壊した橋の右側の島番号
broken = INF
# 後ろから壊していく
for i in reversed(range(len(reqs))):
    req = reqs[i]
    if req < broken:
        # 一番左壊しとけばその先には行けない
        broken = i + 1
        ans += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

ans = 1
x = demand[0][1] - 2
for i in range(1, m):
    if x < demand[i][0] - 1:
        ans += 1
        x = demand[i][1] - 2
print(ans)

Submission status: Accepted

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

dp = [0]*(n+1)
for i in range(1,n+1):
    dp[i] = max(dp[i],dp[i-1])
    for j in edge[i]:
        dp[j] = max(dp[j], dp[i]+1)
#print(dp)
print(dp[n])

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 = 0
now = -1
for s, e in ab:
    if now <= s:
        ans += 1
        now = e
print(ans)

Submission status: Accepted

Solution code:
def main():
	N, M = map(int, input().split())
	LR = [0]*M
	for i in range(M):
		LR[i] = list(map(int, input().split()))

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

	l, r = LR[0][0], LR[0][1]
	ans = 1
	for i in range(1, M):
		if LR[i][0] < r:
			l = max(l, LR[i][0])
		else:
			ans += 1
			l = LR[i][0]
			r = LR[i][1]
	print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from operator import itemgetter

N, M = map(int, raw_input().split())
request = []
for i in range(0, M):
	inpt = map(int, raw_input().split())
	request.append(inpt)
request.sort(key=itemgetter(1))
cnt = 0
tmp = -1
for i in range(0, len(request)):
	if tmp <= request[i][0]:
		cnt += 1
		tmp = request[i][1]
print cnt

Submission status: Accepted

Solution code:
from operator import itemgetter

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

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

ab.sort(key=itemgetter(1))

fall = -1
ans = 0

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

print(ans)

Submission status: Accepted

Solution code:
islands, requests = map(int, input().split(" "))
req = []
for r in range(requests):
    a, b = map(int, input().split(" "))
    req.append([a, b])
req = sorted(req, key = lambda x:x[1])
answer = 1
temp_end = req[0][1]
for r in req:
    if r[0] >= temp_end:
        temp_end = r[1]
        answer += 1
print(answer)

Submission status: Accepted

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

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

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

ans = 0
x = 0
for a in A:
    if x < a[0]:
        x = a[1] - 1
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import heapq
N, M = map(int, input().split())
data = []
for i in range(M):
    a, b = map(int, input().split())
    heapq.heappush(data, (b, a))

cut = 0
answer = 0
for i in range(M):
    b, a = heapq.heappop(data)
    if cut <= a:
        answer += 1
        cut = b

print(answer)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n,m = map(int,input().split())
ab = [[0,0] for _ in range(m)]
for i in range(m):
    ab[i][1],ab[i][0] = map(int,input().split())

ab.sort()

cnt = 0
before = 0
for i in range(m):
    if cnt >= 1 and ab[i][1] < before:
        pass
    else:
        before = ab[i][0]
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
w=[]
for i in range(m):
    a,b=map(int,input().split())
    w.append((a,b))
w.sort(reverse=True)
d=[]
for i in range(m):
    a,b=w.pop()
    if i==0:
        d.append([a,b])
    else:
        if d[-1][1]<=a:
            d.append([a,b])
        elif d[-1][1]>b:
            d[-1][1]=b
print(len(d))

Submission status: Accepted

Solution code:
#TLEした
#方針　もっとも近い敵でない島の集まりを調べると区間スケジュール問題となる。
#一列に並んでいるので飛んだ島とは繋げない
#橋の取り壊しの最小値というが、分割としてはもっとも番号の若いものまでしか無理である。
#最近接の敵である島の数字をもつ配列を考える。

#TLEの解決さく最小値順に初めから並べ替えておく。そのとき島の位置がindexkara
#測れないのでtupleを作っていく。

from operator import itemgetter
N,M = (int(_) for _ in input().split())
mostNeightborOpponent = [(N+1,i+1) for i in range(N)]
#print(mostNeightborOpponent)
for i in range(M):
    a,b = (int(_) for _ in input().split())
    if mostNeightborOpponent[a-1][0] > b:
        mostNeightborOpponent[a-1] = (b,a) #tupleを作るsortは第一引数を考えるので順序はこの順
#print(mostNeightborOpponent)
#island:・・・島|島・・・の右の島のindex
island = 1
bridgeWillBreak = 0

sortedOpponent = sorted(mostNeightborOpponent,key = itemgetter(0))

for b,a in sortedOpponent:
    if a < island :
        continue
    island = b
    if island > N :
        break
    bridgeWillBreak += 1

print(bridgeWillBreak)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    islands_count, demands_count = list(map(int, input().split()))
    demands = []
    break_count = 0

    for i in range(demands_count):
        demand = list(map(int, input().split()))
        demands.append(demand)

    demands.sort(key=lambda x: x[1])
    west_edge = 0

    for demand in demands:
        if demand[0] >= west_edge:
            break_count += 1
            west_edge = demand[1]

    print(break_count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import itertools
import collections
import functools
import math
import operator
from queue import Queue
INF = float("inf")


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):

    ab = [[x, y] for x, y in zip(a, b)]
    ab.sort(key=operator.itemgetter(1))
    # print(ab)

    cut = [0]                   # i番目とi+1番目をカット
    for a, b in ab:
        if a <= cut[-1]:         # OK
            continue
        cut.append(b-1)
    print(len(cut)-1)


def main():

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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])
end = 0
ans = 0
for y in ab:
    if y[0] >= end:
        ans += 1
        end = y[1]
print(ans)

Submission status: Accepted

Solution code:
inf = 10**10

N,M = map(int,input().split())
ab =[list(map(int,input().split())) for i in range(M)]
ab.sort(reverse=True)
ans = 0
tmp = inf
for i in range(M):
    if ab[i][1] > tmp:
        continue
    else:
        ans += 1
        tmp = ab[i][0]
print(ans)

Submission status: Accepted

Solution code:
N,M = (int(num) for num in input().split())
ab = []
for i in range(M):
    ab.append([int(num)-1 for num in input().split()])
    
ab.sort(key= lambda l:l[1])

tmppos = 0
cnt = 0
for dem in ab:
    a = dem[0]
    b = dem[1]
    if a >= tmppos:
        tmppos = b
        cnt += 1
        
print(cnt)

Submission status: Accepted

Solution code:
from collections import deque
def dfs(v,N,memo):
    ans =0
    if not False in memo.values():
        return 1
    for u in E[v]:
        if memo[u]!=True:
            memo[u] = True
            ans += dfs(u,N,memo)
            memo[u] = False
    return ans
N,M = list(map(int,input().split()))
memo = {i:False for i in range(1,N+1)}
E = {i: []for i in range(1,N+1)}
for i in range(M):
    u,v = list(map(int,input().split()))
    E[v].append(u)
a =0
b = 0
counter =0
for i in range(1,N+1):
    if E[i]:
        if a<max(E[i]):
          if b>max(E[i]):
            a = max(E[i])
            continue
          a = max(E[i])
          b = i
          counter +=1
print(counter)

Submission status: Accepted

Solution code:
def main():
    N, M = [int(n) for n in input().split()]
    paths = [[int(n) for n in input().split()] for _ in range(M)]
    paths.sort(key = lambda x: x[0])

    prev = (-1, -1)
    result = 0
    for l, r in paths:
        r = r - 1
        pl, pr = prev
        if pl <= l and r <= pr:
            prev = (l, r)
            continue
        elif pl <= l <= pr and pr < r:
            prev = (l, pr)
            continue
        elif pr < l :
            prev = (l, r)
            result += 1
            continue
        else:
            raise ValueError("aaa")
    print(result)
if __name__ == "__main__":
    main()

Submission status: Accepted

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

requests = sorted(requests, key=lambda x: x[1])# end <= nextend
start = 0
end = 0
ans = 0
for request in requests:
    nextstart, nextend = request
    if end <= nextstart:
        ans += 1
        start = nextstart
        end = nextend
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

l_ab.sort(key=operator.itemgetter(1))
#l_br=[]
l_br_last=0
num_br=0
for i in range(m):
    #if bisect.bisect_left(l_br,l_ab[i][0])==len(l_br):
    #if l_br[-1]<l_ab[i][0]:
        #l_br.append(l_ab[i][1]-1)
    if l_br_last<l_ab[i][0]:
        l_br_last=l_ab[i][1]-1
        num_br+=1
print(num_br)

Submission status: Accepted

Solution code:
from operator import itemgetter

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

req.sort(key=itemgetter(1))

max=0
ans=0

for i in range(M):
    if not req[i][0]<=max<req[i][1]:
        max=req[i][1]-1
        ans+=1
        
print(ans)

Submission status: Accepted

Solution code:
import numpy as np
N, M  = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(M)]
ab.sort(key=lambda student: student[1])
temp = [0,0]
count = 0
for x in ab:
    if  x[0] <= temp[0] and temp[1] <= x[1] :
        continue
    else:
        temp[0] = x[1]-1
        temp[1] = x[1]
        count += 1
print(count)

Submission status: Accepted

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

D = {}

for _ in range(M):
  a,b = map(int, input().split())
  if not b in D.keys():
    D[b] = a
  elif a > D[b]:
    D[b] = a

th = 0
count = 0
D = sorted(D.items(), key=lambda x: x[0])
for (e,s) in D:
  if ((th < s) or (e < th)):
    th = e - 1
    #print(s,e,th)
    count += 1
print(count)

Submission status: Accepted

Solution code:
from operator import itemgetter
n,m = map(int,input().split())

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

ans = 0
cut_pos = -1
for i in range(m):
    if cut_pos <= info[i][0]:
        ans += 1
        cut_pos = info[i][1]
print(ans)