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 = []
cnt = 0
for i in range(M):
    A.append(list(map(int, input().split(" "))))

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

endtime = 0
for i in range(M):
    if A[i][0] >= endtime:
        endtime = A[i][1]
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
req = [list(map(int, input().split())) for i in range(M)]
req.sort()
ans = 0
left = 0
right = 0
for i in range(M):
    if req[i][0] >= right:
        ans += 1
        left, right = req[i][0], req[i][1]
    else:
        left = req[i][0]
        right = min(req[i][1], right)
 
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
req = [list(map(int, input().split())) for i in range(M)]
req.sort(key = lambda x:(x[0], -x[1]))
ans = 0
left = 0
right = 0
for i in range(M):
    if req[i][0] >= right:
        ans += 1
        left, right = req[i][0], req[i][1]
    else:
        left = req[i][0]
        right = min(req[i][1], right)

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

broken_bridges=[0]
for sorted_require in sorted_requires:
    if max(broken_bridges) >sorted_require[0]:
        continue
    else:
        broken_bridges.append(sorted_require[1])

ans=len(broken_bridges)-1
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

D = []
dic = dict()

for m in range(M):
    a, b = map(int, input().split())
    D.append((b, a))
    if b in dic.keys() and (dic[b] > a):
        continue
    else:
        dic[b] = a
    
# print(dic)

dp = np.zeros(N+1, dtype=int)

dp[0] = 0
for i in range(1, N+1):
    dp[i] = dp[i-1]
    if i in dic.keys():
        a = dic[i]
        if dp[a] == dp[i]:
            dp[i] = 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 _ in range(m)]
ab.sort(key=lambda x:x[1])
cnt = 0
end_time = 0
for a,b in ab:
  if end_time <= a:
    end_time = b
    cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
n,m=list(map(int,input().split()))
c=[]
for i in range(m):
    a,b=list(map(int,input().split()))
    d=[]
    d.append(a)
    d.append(b)
    c.append(d)
c.sort(key=lambda x: x[1])
#print(c)
cur=0
ans=0
for i in range(m):
    if c[i][0] >= cur:
        cur = c[i][1]
        ans += 1  
print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

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

    return G

def solve(G, N):
    ans = 0
    index = -1

    for i in range(1, N):
        for p in G[i]:
            if index < p < i:
                ans += 1
                index = i - 1
    return ans

if __name__ == "__main__":
    N, M = map(int, input().split())
    G = getG(N, M)
    print(solve(G, N))

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    e = sorted([LI()[::-1] for _ in range(m)])
    r = 0
    c = -2
    for b,a in e:
        if a > c:
            r += 1
            c = b - 0.5
    return r


print(main())

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
n, m = map(int, input().split())
d = []
for i in range(m):
    a, b = map(int, input().split())
    d.append([a, b])

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

mn = 100000000
ans = 0
for a, b in d:
    if a >= mn:
        ans += 1
        mn = b
    mn = min(mn, b)

if mn != 100000000:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Thu Aug  9 04:30:54 2018

@author: Yuki
"""
import numpy as np
N, M = map(int, input().split())
AB = np.zeros([M, 2])
for i in range(M):
    AB[i, 0], AB[i, 1] = map(int, input().split())

AB = AB[np.argsort(AB[:, 1])]

cut_br = [AB[0, 1]-1]
for i in range(1, M):
    flag = False
    if AB[i, 0] <= cut_br[-1]:
        if cut_br[-1] < AB[i, 1]:
            flag = True
    if not(flag):
        cut_br.append(AB[i, 1]-1)

print(len(cut_br))

Submission status: Accepted

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

Submission status: Accepted

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

A.sort(key=lambda a:a[1])
ans = 0
last = 0

for a, b in A:
    if a >= last:
        ans += 1
        last = b

print(ans)

Submission status: Accepted

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

A.sort(key=lambda a:a[1])
ans = 0
i = 0

while i < m:
    b = A[i][1]
    ans += 1
    i += 1
    while i < m:
        if A[i][0] >= b:
            break
        i += 1

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:

from operator import itemgetter
 
n,m=map(int, input().split())
A=[]
B=[]
a=0
b=0
for i in range(m):
  a,b=map(int, input().split())
  A.append([a,b])

A.sort(key=itemgetter(1))
bri=0 #取った橋のうち番号最大の島のもの。bri=5なら4,5番目の島の橋

count=0

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

print(count)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
# stdin.readlines?
x = [[0, 0] for i in range(m)]
for i in range(m):
    x[i][0], x[i][1] = map(int, input().split())
x = sorted(x, key=lambda y: y[0])
ans = 1
mx = max([x[i][0] for i in range(m)])
while len(x) > 0:
    for i in range(len(x)-1, -1, -1):
        if mx < x[i][1]:
            x.pop(i)
            break
        else:
            mx = x[i][0]
            ans += 1
            break
print(ans)

Submission status: Accepted

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

p_num = -1
ans = 0

for i in range(M):
	if not l[i][0] <= p_num:
		p_num = l[i][1] - 1
		ans += 1

print(ans)

Submission status: Accepted

Solution code:
break_offs = set()
N, M = map(int, input().split())
for i in range(M):
    a, b = map(int, input().split())
    if a > b:
        a, b = b, a
    break_offs.add((a, b))

last_bridge = 0
count = 0
for a, b in sorted(list(break_offs), key=lambda x:x[1]):
    if last_bridge <= a:
        last_bridge = b
        count += 1

print(count)

Submission status: Accepted

Solution code:
break_offs = set()
N, M = map(int, input().split())
for i in range(M):
    a, b = map(int, input().split())
    if a > b:
        a, b = b, a
    break_offs.add((a, b))

covered = []
break_offs = sorted(list(break_offs), key=lambda x:x[1])
for a, b in break_offs:
    found = False
    for area in covered:
        if not (area[0] >= b or area[1] <= a):
            covered.remove(area)
            covered.append((max(area[0], a), min(area[1], b)))
            found = True
            break

    if not found:
        covered.append((a, b))


answer = len(covered)
print(answer)

Submission status: Accepted

Solution code:
n, m = list(map(int, input().split()))
ab = list(list(map(int, input().split())) for i in range(m))
ab = sorted(ab, key=lambda x: x[1])
bridge = 0
count = 0
for i in range(m):
    if ab[i][0] < bridge:
        continue
    else:
        bridge = ab[i][1]
        count = count + 1
    if count == n-1:
        break
    else:
        continue
print(count)

Submission status: Accepted

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

#aをbについて昇順にする。
a=sorted(a, key=lambda x: x[1])
hasi = -1#どこの橋を壊したか
sum = 0

for i in range(0,M):
    # print(c1,c2,hasi)
    if (hasi >= a[i][0])and (hasi < a[i][1]):
        continue
    else:
        hasi = a[i][1]-1
        sum = sum+1

print(sum)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = map(int, input(). split())
lists = [[int(i) for i in input().split()] for j in range(m)]
lists.sort()
a = b = count = 0
for x in lists:
  if a < x[0]:
    if b <= x[0]:
      count += 1
      a = x[0]
      b = x[1]
    else:
      b = min(b, x[1])
print(count)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
li = [[int(i) for i in input().split()] for j in range(M)]
li.sort()
a = b = C = 0
for d in li:
    if a < d[0]:
      if b <= d[0]:
        C += 1
        a = d[0]
        b = d[1]
      else:
        b = min(b,d[1])
print(C)

Submission status: Accepted

Solution code:
#!/usr/bin/python3

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def solve(N, M, a, b):
    pass


def main():
    N, M = map(int, input().split())
    l = []
    for _ in range(M):
        a, b, = map(int, input().split())
        l.append((a, b))
    l.sort()

    ans = 0
    mini = INF
    for a, b in l:
        if mini <= a:
            ans += 1
            mini = INF
        mini = min(mini, b)

    print(ans + 1)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

input_lines = [list(map(int,input().split())) for i in range(b)]
input_lines = sorted(input_lines,key=lambda x: x[1]) #各要素において[1]に基づきソートする

c=[0]
for i in input_lines:
    #for j in c:
    #   if j > i[0]:
    #        p=1
    if max(c)<=i[0]:
        c.append(i[1])
        
print(len(c)-1)

Submission status: Accepted

Solution code:
N,M=list(map(int,input().split()))
ab= [list(map(int, input().split())) for i in range(M)]
ab=sorted(ab,key=lambda x:x[1])
cut=-1
ct=0
for a,b in ab:
    if a<=cut:
        continue
    else:
        cut=b-1
        ct+=1
print(ct)

Submission status: Accepted

Solution code:
a=list(map(int,input().split()))
b=[]
c=0
r=0
for i in range(a[1]):
  b.append(list(map(int,input().split())))
b=sorted(b,key=lambda b:b[1])

for i in range(a[1]):
  if b[i][0]<=r:
    continue
  else:
    c=c+1
    r=b[i][1]-1

print(c)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
a = []
for _ in range(m):
    u, v = map(int, input().split())
    a.append((u, v))
a.sort()
i, c = 0, 0
for u, v in a:
    if u >= i:
        c += 1
        i = v
    else:
        i = min(i, v)
print(c)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
from operator import itemgetter

str = input()
nm=[int(x) for x in str.split(' ')]
n = nm[0]
m = nm[1]
ab_2d = []
for i in range( 0, m ):
    str_ab = input()
    ab = [int(x) for x in str_ab.split(' ')]
    ab_2d.append(ab)

sorted_ab_2d = sorted(ab_2d, key = itemgetter(1))

bridge = 0
count = 0

for i in range( 0, m ):
    if(sorted_ab_2d[i][0] > bridge):
        count = count + 1
        bridge = sorted_ab_2d[i][1] - 1
    # print('bridge',bridge)

print(count)

Submission status: Accepted

Solution code:
ab=[]

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

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

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

res=0
for z in range(len(ab)):
    x=ab[0][1]
    for j in range(len(ab)):
        if x > ab[0][0]:
            del ab[0]
        else:
            res+=1
            break
    if len(ab)==0:
        res+=1
        break
    
print(res)

Submission status: Accepted

Solution code:
def main():
    n = [int(i) for i in input().split()]
    bridge = set()
    counter = 0
    reqs = [[int(j) for j in input().split()] for i in range(n[1])]
    reqs.sort(key=lambda x:(x[0],x[1]))
    
    preset = 0
    for i in range(1, n[0]+1):
        if i in bridge:
            bridge.clear()
            counter += 1
        for j in range(preset, len(reqs)):
            if reqs[j][0] == i:
                bridge.add(reqs[j][1])
            else:
                preset = j
                break
    
    print(counter)

main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
disputes = [list(map(int, input().split())) for x in range(M)]
disputes.sort(key=lambda x: x[1])
disconnects = []
for dispute in disputes:
    for disconnect in disconnects:
        if dispute[0] <= disconnect and disconnect < dispute[1]:
            break
    else:
        disconnects.append(dispute[1] - 1)
print(len(disconnects))

Submission status: Accepted

Solution code:
n,m = list(map(int,input().split()))
wars = []
last_bs = 0
cnt = 0

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

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

for war in wars:
    if war[0] > last_bs:
        last_bs = war[1]-1
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
def main():
    """
    2 <= N <= 10^5
    1 <= M <= 10^5
    1 <= ai < bi <= N
    (ai, bi) != (aj, bj)
    """
    N, M = map(int, input().split())
    A, B = zip(*[
        map(int, input().split())
        for _ in range(M)
    ])
    # ans = WA(N, M, A, B)
    ans = editorial(N, M, A, B)
    # ans = TLE(N, M, A, B)

    print(ans)


def editorial(N, M, A, B):
    ans1 = AC_b_sort(N, M, A, B)
    ans2 = AC_a_sort(N, M, A, B)
    assert ans1 == ans2
    return ans1


def AC_b_sort(N, M, A, B):
    ab = sorted(zip(A, B), key=lambda x: (x[1], x[0]))
    ans = 0
    bef_b = 0
    for a, b in ab:
        # print(" " * (a-1), a, "-" * (b - a - 1), b, sep="")
        if bef_b <= a:
            ans += 1
            bef_b = b

    return ans


def AC_a_sort(N, M, A, B):
    ab = sorted(zip(A, B), key=lambda x: (x[0], -x[1]))
    ans = 0
    bef_b = float("inf")
    for a, b in ab:
        # print(" " * (a-1), a, "-" * (b - a - 1), b, sep="")
        if bef_b <= a:
            ans += 1
            bef_b = b
        else:
            bef_b = min(bef_b, b)

    return ans + 1


def TLE(N, M, A, B):
    """
    """
    ans = N - 1
    for a in A:
        for b in B:
            pass

    return ans


def WA(N, M, A, B):
    """
    ai, bi の分断:

    入力例1
        1, 4 の分断
            橋1-3 のどれかを除去
        2, 5 の分断
            橋2-4 のどれかを除去
        共通部: 2-3
        要望ごとの共通部を探す必要がある
            M^2: TLE

    A_min: 西
    A_max: 東
    B_min: 西
    B_max: 東

    入力例2
    9 5
    1------8
     2----7
      3-5
       4-6
          7-9

    a_min,b_max の順に並べる
    要望の東側が以前の西側未満ならOK
    要望の西側が以前の東側を超えないならOK ?
    """
    ab = sorted(zip(A, B), key=lambda x: (x[0], -x[1]))
    ans = 0
    bef_a, bef_b = -1, float("inf")
    for i, (a, b) in enumerate(ab):
        print(" " * (a-1), a, "-" * (b - a - 1), b, sep="")
        if bef_a <= a < b <= bef_b:
            pass
        elif bef_b <= a:
            ans += 1
        elif bef_a < a < bef_b < b:
            pass

        bef_a, bef_b = a, b

    return ans + 1


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    string = input().split()
    island = int(string[0])
    dispute_num = int(string[1])
    disputes = []
    for i in range(dispute_num):
        string = input().split()
        disputes.append([int(string[0]), int(string[1])])
    disputes.sort()

    cut_count = 1
    left_cut = disputes[0][0]
    right_cut = disputes[0][1]
    for i in range(1, dispute_num):
        left = disputes[i][0]
        right = disputes[i][1]
        if( right_cut > left):
            left_cut = left
            if(right_cut > right):
                right_cut = right
        else:
            cut_count += 1
            right_cut = right
            left_cut = left

    print(cut_count)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from operator import itemgetter
def main():
  n, m = map(int, input().split())
  bridge = 0
  ab = []
  for _ in range(m):
    a, b = map(int, input().split())
    ab.append((a,b))
  ab = sorted(ab, key=itemgetter(1))
  count = 0
  for a, b in ab:
    if not a <= bridge <= b:
      count += 1
      bridge = b-1
  print(count)

main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#
import sys
import math
import numpy as np
import itertools


# いくつか入力
n,m = (int(i) for i in input().split())  
# m行複数列の数をリストに
l = [[int(i) for i in input().split()] for i in range(m)] 

l = sorted(l, key=lambda x:x[0])
answer=1
a=l[0][0]
b=l[0][1]
for i in range(1,m):
    if l[i][0] >= b:
        answer += 1
        a=l[i][0]
        b=l[i][1]
    else:
        a=l[i][0]
        b=min(b,l[i][1])
#    print(answer,"-",a,b)

print(answer)

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

# bの昇順でsort
ab.sort(key=lambda inv: inv[1])   


count = 0
while(0 < len(ab)):
    count += 1
    cutb = ab[0][1]
    # cutbで除外できる闘争を除外する
    remove_index = 0
    for i in range(len(ab)):
        a, b = ab[i]
        if a <= cutb - 1 and cutb <= b:
            remove_index = i
        else:
            break

    ab = ab[remove_index+1:]

print(count)

Submission status: Accepted

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

arr = []

for i in range(m):
	arr.append(map(int,raw_input().split()))

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


ans = 0
t = 0


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

print ans

Submission status: Accepted

Solution code:
def main():
    n = [int(i) for i in input().split()]
    bridge = set()
    counter = 0
    reqs = [[int(j) for j in input().split()] for i in range(n[1])]
    reqs.sort(key=lambda x:(x[0],x[1]))
    
    preset = 0
    for i in range(1, n[0]+1):
        if i in bridge:
            bridge.clear()
            counter += 1
        for j in range(preset, len(reqs)):
            if reqs[j][0] == i:
                bridge.add(reqs[j][1])
            else:
                preset = j
                break
    
    print(counter)

main()

Submission status: Accepted

Solution code:
def main():
    n = [int(i) for i in input().split()]
    bridge = set()
    counter = 0
    reqs = [[int(j) for j in input().split()] for i in range(n[1])]
    reqs.sort(key=lambda x:(x[0],x[1]))
    prefix = 0
    
    for i in range(1, n[0]+1):
        if i in bridge:
            bridge.clear()
            counter += 1
        for j in range(prefix, len(reqs)):
            if reqs[j][0] == i:
                bridge.add(reqs[j][1])
            else:
                prefix = j
                break
    
    print(counter)
 
main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
x = [[] for _ in range(n)]
for q in range(m):
    a, b = map(int, input().split())
    x[b-1].append(a-1)
r = p = 0
for i in range(n):
    for j in x[i]:
        if j >= p:
            r += 1
            p = i
print(r)

Submission status: Accepted

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

right_bridge,sum_bridge = 0,0
for a, b in village:
    if right_bridge<a:
        right_bridge=b-1
        sum_bridge+=1
        
print(sum_bridge)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
r = []
for _ in range(m):
    r.append(tuple(map(int,input().split())))
r.sort(key = lambda x:x[1],reverse = True)
ans = 0
while len(r) > 0:
    _,y = r[-1]
    ans += 1
    while len(r) > 0 and r[-1][0] < y:
        r.pop()
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
r = []
for _ in range(m):
    r.append(tuple(map(int,input().split())))
r = deque(sorted(r,key = lambda x:x[1]))
ans = 0
while len(r) > 0:
    _,y = r[0]
    ans += 1
    while len(r) > 0 and r[0][0] < y:
        r.popleft()
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,raw_input().split())
arr = []
for _ in range(m):
	a,b = map(int,raw_input().split())
	arr.append((b,a))
arr.sort()
mr = -1
ans = 0
for i in range(m):
	if mr > arr[i][1]:
		continue
	else:
		mr = arr[i][0]
		ans += 1
print ans

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
war = []
for i in range(m):
    a,b = map(int,input().split())
    war.append([a,b])
war.sort(key = lambda x: x[1])
ans = 1
now = war[0][1]
k = 1
while k < m:
    if war[k][0] >= now:
        ans += 1
        now = war[k][1]
    k += 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])
c = 0
d = 0
i = 0
for t in ab:
  if d < t[0]:
    c += 1
    d = t[1]-1
print(c)

Submission status: Accepted

Solution code:
#coding:utf-8

n,m = map(int, input().split())
itv = []
for i in range(m):
    si,ti = map(int, input().split())
    itv.append([ti, si])
itv.sort()

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

print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

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

ind = np.argsort(b)
a = a[ind]
b = b[ind]

num_broken_bridge = 0
last_bridge_position = - float("inf")
for i in range(len(a)):
    if a[i] > last_bridge_position:
        last_bridge_position = b[i] - 1
        num_broken_bridge += 1
    
print(num_broken_bridge)

Submission status: Accepted

Solution code:
def d_islands_war(N, M, Demands):
    demands = sorted(Demands, key=lambda x: x[1])
    _, previous_cut = demands[0]  # previous_cut番目の島のすぐ西の橋を切る
    ans = 1
    for a, b in demands[1:]:
        if a >= previous_cut:
            # 要望を満たすためにb番目の島のすぐ西の橋を切らねばならない
            ans += 1
            previous_cut = b
    return ans

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

Submission status: Accepted

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

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

    if ai <= x:
        continue

    else:
        x = bi - 1
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
n,m=[int(x) for x in input().split()]
isA,atob=[0]*n,[n+1]*n
for _ in [0]*m:
    ai,bi=[int(x) for x in input().split()]
    isA[ai-1]=1
    atob[ai-1]=min(atob[ai-1],bi-1)
bstack=n+1
ans=0
for a in range(n):
    if bstack==a:
        ans+=1
        bstack=n+1
    if isA[a]==0:
        continue
    bstack=min(bstack,atob[a])
print(ans)

Submission status: Accepted

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

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

bridge = 0
ans = 0

for ab in abList:
  if not ab[0] <= bridge < ab[1]: # 3 <=0 <   5 //  4 <= 4 < 6 //  2 <= 4 7 // 7 <= 4 < 9
    bridge = ab[1] -1             # 4           //  pass                    // bridge = 8
    ans += 1                      # 1           //  pass                    // +1

print(ans)

Submission status: Accepted

Solution code:
NM = [int(i) for i in input().split()]
N, M = NM[0], NM[1]
abList = sorted([[int(i) for i in input().split()] for _ in range(M)], key=lambda x: x[1])
bridge = 0
ans = 0

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

print(ans)

Submission status: Accepted

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

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

wars = []

for i in range(m):
    wars.append(list(map(int, input().split())))

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

res = 0
recent_destroyed = -1

for i in range(len(wars)):
    if wars[i][0] <= recent_destroyed and wars[i][1] > recent_destroyed:
        continue
    res += 1
    recent_destroyed = wars[i][1] - 1

print(res)

Submission status: Accepted

Solution code:
import sys

N, M = map(int, input().split())
A = [0 for i in range(N+1)]
for i in range(M):
	A1, A2 = map(int, input().split())
	if A[A1] > A2 or A[A1] == 0:
		A[A1] = A2
	
ans = 0
min_dir = sys.maxsize
for i in range(1, N+1):
	if A[i] != 0:
		min_dir = min(A[i], min_dir)
	if i >= min_dir:
		ans += 1
		if A[i] != 0:
			min_dir = A[i]
		else:
			min_dir = sys.maxsize
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
data=sorted([tuple(map(int,input().split())) for i in range(m)],reverse=True)
ans=0
last=-1
for d in data:
    if d[0]<=last<d[1]:
        pass
    else:
        ans+=1
        last=d[0]
print(ans)

Submission status: Accepted

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

deleted_bridges = [array[0][1]-1]
for rule in array:
    bridge_flag = True
    for bridge in deleted_bridges:
        if rule[0] <= bridge < rule[1]:
            bridge_flag = False
            break
    if bridge_flag:
        deleted_bridges.append(rule[1]-1)

print(len(deleted_bridges))

Submission status: Accepted

Solution code:
#!/usr/bin/python3

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

ab.sort(reverse=True)
x = ab[0][0]
ans = 1
for i in ab:
    if i[1] <= x:
        x = i[0]
        ans += 1

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

idx = ans = 0
for x in data:
  if x[0] >= idx:
    idx = x[1]
    ans += 1

print (ans)

Submission status: Accepted

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

paths = []

for i in range(M) :
    _a, _b = map(int, input().split())
    paths.append((_a, _b))

st = sorted(paths, key = lambda x : x[1])
cnt = 0
prev_b = -1

for i in st :
    if cnt == 0 :
        cnt += 1
        prev_b = i[1]
    else :
        if i[0] >= prev_b :
            cnt += 1
            prev_b = i[1]
    
print(cnt)

Submission status: Accepted

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

last  = -1  # the last broken bridge
count = 0   # the number of broken bridges
for a, b in sorted(R, key=lambda r: r[1]):
    if last < a:
        last = b - 1
        count += 1
print(count)

Submission status: Accepted

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

#http://drken1215.hatenablog.com/entry/2018/07/21/224200

# 条件の入力
N,M = map(int, raw_input().split())

orders=[]
for i in range(M):
	first, second = map(int, raw_input().split())
	orders.append((first, second))
	

#secondの値の小さい順に並び替え
cmpFunc = lambda x, y : x[1] - y[1]
sorted_orders = sorted(orders, cmpFunc)

#多分、この辺がgreedyにとっていく処理
ret=0
endtime=0
for order in sorted_orders:
	if order[0] >= endtime:
		endtime=order[1]
		ret+=1

#結果の出力
print ret