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 collections import deque
def main():
    N,M = map(int,input().split(" "))
    request = []
    for i in range(M):
        a,b = map(int,input().split(" "))
        request.append((b,a))
    request.sort()
    request = deque(request)
    ans = [request.popleft()]
    for i in range(M-1):
        x = request[i][1]
        if x >= ans[-1][0]:
            ans.append(request[i])
    print(len(ans))
if __name__ == "__main__":
    main()

Submission status: Accepted

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

rem = 0
now = 0

for ab in S:
    left = ab[0]
    right = ab[1]
    if left <= now:
        continue
    else:
        now = right -1
        rem += 1

print(rem)

Submission status: Accepted

Solution code:
from operator import itemgetter

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

requests = [tuple(map(int, input().split())) for _ in range(m)]
requests = sorted(requests, key=itemgetter(1))

counter = 1
now = requests[0][1]
for request in requests[1:]:
    if request[0] >= now:
        now = request[1]
        counter += 1

print(counter)

Submission status: Accepted

Solution code:
#https://atcoder.jp/contests/abc103/tasks/abc103_d
from collections import deque
N, M = map(int, input().split())
a = [0]*M
b = [0]*M
lis = []
for i in range(M):
    a[i], b[i] = map(int, input().split())
    lis.append([a[i], b[i]])

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

start, end = lis.popleft()
cnt = 1

while lis:
    x, y = lis.popleft()
    if x<end:
        continue
    else:
        start = x
        end = y
        cnt += 1

print(cnt)

Submission status: Accepted

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

pairs.sort(key=lambda x: x[1])  # 終端が早い順に並び替え

# 重複区間除去(greedy)
current = 0
bag = []
for pair in pairs:
    if pair[0] >= current:
        bag.append(pair)
        current = pair[1]

print(len(bag))

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 = sorted(AB, key=lambda x:x[1])

rem = 0
now = 0

for ab in AB:
    left = ab[0]
    right = ab[1]
    if left <= now:
        pass
    else:
        now = right -1
        rem += 1

print(rem)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M, *L = map(int, open(0).read().split())
sheet = [[[],[]] for i in range(N+1)]
for i,m in enumerate(zip(*[iter(L)]*2)):
  sheet[m[0]][0].append(i)
  sheet[m[1]][1].append(i)
ans = 0
log = set()
cnt = set()
for i in range(1,N+1):
  for x in sheet[i][1]:
    if x not in log:
      ans += 1
      log = log.union(cnt)
      cnt = set()
  for x in sheet[i][0]:
    cnt.add(x)
print(ans)

Submission status: Accepted

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

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

right = 0
count = 0

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

print(count)

Submission status: Accepted

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


bridge=[]

for i in range(M):
    C = list(map(int,input().split(' ')))
    bridge.append(C)

#print(bridge)

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

#print(bridge)

temp = 0
ans = 0

for i in range(M):
    if(temp<=bridge[i][0]):
        temp = bridge[i][1]
        ans+=1

print(ans)

Submission status: Accepted

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

N, M = map(int, input().split())
events = []
for i in range(M):
    a, b = map(lambda x: int(x)-1, input().split())
    events.append((a, 1, i))
    events.append((b, 0, i))
events.sort()
ans = 0
removed = set()
started = set()
for x, t, i in events:
    if t == 0:
        if i not in removed:
            removed |= started
            started = set()
            ans += 1
    if t == 1:
        started.add(i)
print(ans)

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N,M=map(int,input().split())
s=[tuple(map(int, input().split())) for i in range(M)]
from operator import itemgetter
s.sort(key=itemgetter(1))
t=0
a=0
for i in s:
    if i[0]>t:
        a+=1
        t=i[1]-1
print(a)

Submission status: Accepted

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

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

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

ans = 0
x = 0
for i in range(M):
    a, b = bridges[i]
    if a >= x:
        x = b
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ab = []
for _ in range(m):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])
ab = sorted(ab, key=lambda x: x[1])
#print(ab)
count = 1
memo = ab[0][1]
for i in range(m):
    if i == 0:
        continue
    if memo <= ab[i][0]:
        count += 1
        memo = ab[i][1]
print(count)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
ab=[]
for m in range(M):
  [a,b]=[int(i) for i in input().split()]
  ab.append([a,b])
ab.sort(key=lambda x:x[1])
count=[]
count.append(ab[0][1]-1)
for i in range(1,M):
  if ab[i][0]<=count[-1]<ab[i][1]:
    pass
  elif ab[i][0]<=count[-1] and ab[i][1]-1==count[-1]:
    count.remove(count[-1])
    count.append(ab[i][1]-1)
  else:
    count.append(ab[i][1]-1)
print(len(count))

Submission status: Accepted

Solution code:
import sys
sin = sys.stdin.readline
N, M = map(int, sin().split())
bs = [tuple(map(int, sin().split())) for _ in range(M)]
bs.sort(key=lambda x: x[1])

rbs = []
for a, b in bs:
    if not rbs or a > rbs[-1]:
        rbs.append(b - 1)
ans = len(rbs)
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
bs = [tuple(map(int, input().split())) for _ in range(M)]
bs.sort(key=lambda x: x[1])

rbs = []
for a, b in bs:
    if not rbs or a > rbs[-1]:
        rbs.append(b - 1)
ans = len(rbs)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

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

# 東側の順にソート
sorted_AB = sorted(AB, key=lambda ab: ab[1])
#print(sorted_AB)

# 戦争中のペアの最東端の橋を取り除く
removed_bridge_number = 0
easternmost = 0
for (a, b) in sorted_AB:
    #print('(a, b): ({}, {})'.format(a, b))
    if a >= easternmost:
        removed_bridge_number += 1
        easternmost = b

print(removed_bridge_number)

Submission status: Accepted

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

section=[]

for i in range(m):
    aa,bb=list(map(int,input().split()))
    section.append([aa,bb])

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

maxr=-10**6
cnt=0

for a,b in section:
    if maxr<=a:
        maxr=b
        cnt+=1

print(cnt)

Submission status: Accepted

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

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

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

b = -1
ans = 0
for tupl in ab_list:
  if b == -1:
    ans += 1
    b = tupl[1]
  elif b == tupl[1]:
    continue
  elif b != tupl[1]:
    if tupl[0] <= b-1:
      continue
    else:
      ans += 1
      b = tupl[1]
print(ans)

Submission status: Accepted

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

ans = 0
pos = 0
for a, b in requests:
    if pos <= a:
        ans += 1
        pos = b

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N,M=map(int,input().split())

memo=[[10**9] for i in range(N)]

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

ans=0
kill=10**9
for i in range(N):
    if i==kill:
        #print(i)
        ans+=1
        kill=10**9
    kill=min(kill,min(memo[i]))
print(ans)

Submission status: Accepted

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

previous = -1
total = 0
for ab in ABsorted:
  if ab[0] <= previous and previous <= ab[1]-1:
    pass
  else:
    total += 1
    previous = ab[1]-1
print(total)

Submission status: Accepted

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

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

# sort by end point
plan = sorted(plan, key=lambda x:x[1])

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
ab.sort()
m = 0
ans = 0
for a, b in ab:
  if m <= a:
    ans += 1
    m = n
  m = min(b, m)
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from operator import itemgetter

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

# 区間の終端でソート
ab = sorted([tuple(map(int, input().split())) for i in range(m)], key=itemgetter(1))
# 前回除いた橋
removed = -1
ans = 0

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

print(ans)

Submission status: Accepted

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

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

cut.sort()

b_min = cut[0][1]
count = 0

for a,b in cut[1:]:
  if b_min > b:
    b_min = b
    continue
  if b_min <= a:
    count += 1
    b_min = b

print(count+1)

Submission status: Accepted

Solution code:

from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations
import sys
import bisect
import string
import math
import time
from fractions import gcd
#import random


def I(): return int(input())


def MI(): return map(int, input().split())


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


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['Yes', 'No']
MOD = 10**9+7
inf = float('inf')
IINF = 10**19
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)


# show_flg = False
show_flg = True


def main():
    N, M = MI()
    ab = [None] * M

    for i in range(M):
        a, b = MI()
        ab[i] = [a, b]

    ab = sorted(ab, key=lambda v: v[1])
    bridges = [ab[0]]
    # print(ab)

    for i in range(1, M):
        if bridges[-1][1] <= ab[i][0]:
            bridges.append(ab[i])

    print(len(bridges))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def connected(a, b, last):
    if a <= last:
        return False
    return True
def solve():
    N, M = [int(x) for x in input().split()]
    lst = [[int(x) for x in reversed(input().split())] for i in range(M)]
    lst.sort()
    last = 0
    cnt = 0
    for l in lst:
        b, a = l
        if connected(a, b, last):
            last = b - 1
            cnt += 1
    return cnt

if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
bridge = set()
def connected(a, b):
    for i in bridge:
        if a <= i and i < b:
            return False
    return True
def solve():
    N, M = [int(x) for x in input().split()]
    lst = [[int(x) for x in reversed(input().split())] for i in range(M)]
    lst.sort()
    res = 0
    for l in lst:
        a, b = l
        if connected(b, a):
            bridge.add(a - 1)
    return len(bridge)

if __name__ == '__main__':
    print(solve())

Submission status: Accepted

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

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

Solution code:
import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
def gcd(a,b):return fractions.gcd(a,b) #最大公約数
def lcm(a,b):return (a*b) // fractions.gcd(a,b) #最小公倍数
def iin(): return int(input()) #整数読み込み
def ifn(): return float(input()) #浮動小数点読み込み
def isn(): return input().split() #文字列読み込み
def imn(): return map(int, input().split()) #整数map取得
def fmn(): return map(float, input().split()) #浮動小数点map取得
def iln(): return list(map(int, input().split())) #整数リスト取得
def iln_s(): return sorted(iln()) # 昇順の整数リスト取得
def iln_r(): return sorted(iln(), reverse=True) # 降順の整数リスト取得
def fln(): return list(map(float, input().split())) # 浮動小数点リスト取得
def join(l, s=''): return s.join(l) #リストを文字列に変換
def perm(l, n): return itertools.permutations(l, n) # 順列取得
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) # 順列の総数
def comb(l, n): return itertools.combinations(l, n) # 組み合わせ取得
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) #組み合わせの総数
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 # 2点間の距離
def m_add(a,b): return (a+b) % MOD

N,M = imn()
ab = [iln() for _ in range(M)]
ab = sorted(ab, key=lambda x: x[1])

broken = ab[0][1]
cnt = 1
for i in range(1, M):
    if not ab[i][0] < broken <= ab[i][1]:
        broken = ab[i][1]
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
import itertools
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
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys

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

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
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)




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 ab[i][1]<= l:
            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===============================================

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
import sys, heapq, bisect, math, itertools, string, queue, copy, time
from fractions import gcd
import numpy as np
sys.setrecursionlimit(10**8)
INF = float('inf')
MOD = 10**9+7
EPS = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())

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

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

just_cut = -1
for a, b in request_list:
    if a > just_cut:
        ans += 1
        just_cut = b-1

print(ans)

Submission status: Accepted

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

bmax = 0
ans = 0
for a, b in l:
    if bmax > a:
        continue
    bmax = b
    ans += 1
print(ans)

Submission status: Accepted

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

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

ans=0
prev=-1#直近で橋を落とした位置

for i in range(M):
    if prev<ba[i][1] or prev>ba[i][0]:
        ans+=1
        prev=ba[i][0]-1
        
print(ans)

Submission status: Accepted

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


def read_values():
    return map(int, input().split())


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


def main():
    N, M = read_values()
    Q = [read_list() for _ in range(M)]
    Q.sort()

    res = 0
    end = 10 ** 6
    for q in Q:
        if q[0] >= end:
            res += 1
            end = q[1]
        else:
            end = min(end, q[1])
    
    res += 1
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
from operator import itemgetter
 
N,M = map(int,readline().split())
m = map(int,read().split())
AB = sorted(zip(m,m))
AB.sort(key = lambda x: x[1])


c = AB[0][1]
ans = 1
for i in range(1,M):
	if AB[i][0] < c:
		continue
	else:
		ans += 1
		c = AB[i][1]

print(ans)

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
n, m = map(int, input().split())

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

request.sort(key=lambda x: x[1])
pre = - 1
ans = 0
for a, b in request:
    if pre < a:
        ans += 1
        pre = b - 1

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
AB=[]
for _ in range(M):
    a,b=map(lambda x:int(x)-1, input().split())
    AB.append((a,b,b*10**6+a))
AB.sort(key=lambda x:x[2])
ans=0
i=0
k=0
while i<N-1 and k<M:
    a,b,c=AB[k]
    i=b-1
    ans+=1
    j=k+1
    while j<M:
        a,b,c=AB[j]
        if i<a: break
        j+=1
    k=j
print(ans)

Submission status: Accepted

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

spam.sort(key=lambda x: x[1])
pre = -1
cnt = 0
for a, b in spam:
    if pre < a:
        cnt += 1
        pre = b - 1
print(cnt)

Submission status: Accepted

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

def main():
    n,m = map(int, input().split())
    orders = [[int(s)-1 for s in input().split()] for i in range(m)]
    orders.sort(key=lambda x: x[1])
    
    fallen_bridge = -1
    ans = 0
    for order in orders:
        a = order[0]
        b = order[1]

        if fallen_bridge >= a:
            continue

        fallen_bridge = b - 1
        ans += 1
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
ab = []
for i in range(m):
    a,b = inm()
    ab.append((b,a))
ab.sort()
cnt = 0
prev = -1
for b,a in ab:
    if prev<a:
        prev = b-1
        cnt += 1
print(cnt)

Submission status: Accepted

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

ab.sort(key=lambda x: x[1])
count = 0
current_right = 0
for i in range(m):
    if ab[i][0] >= current_right:
        count += 1
        current_right = ab[i][1]

print(count)

Submission status: Accepted

Solution code:
n,m=list(map(int,input().split()))
M=[list(map(int,input().split())) for _ in range(m)]
M.sort(key=lambda X: X[1])
end,ans=0,0

for a,b in M:
  if a >= end:
    ans += 1
    end=b
print(ans)

Submission status: Accepted

Solution code:
n,m=list(map(int,input().split()))
M=[list(map(int,input().split())) for _ in range(m)]
M.sort(key=lambda X: X[1])
end,ans=0,0

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

Submission status: Accepted

Solution code:
n,m=list(map(int,input().split()))
M=[list(map(int,input().split())) for _ in range(m)]
M.sort(key=lambda X: X[0])
start,end=0,n+1
ans=0

for i in range(m):
  if M[i][0] >= end:
    ans += 1
    start,end=0,n+1
  if M[i][0] > start:
    start=M[i][0]
  if M[i][1] < end:
    end = M[i][1] 
if start != 0 and end != n+1:
  ans += 1 
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ab=[[0]*2 for _ in range(m)]
for i in range(m):
  ab[i][1],ab[i][0]=map(int,input().split())
ab.sort()
cnt=0
num=0
for i in range(m):
  if ab[i][1]<=num:
    continue
  else:
    cnt+=1
    num=ab[i][0]-1
print(cnt)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ab=[[0]*2 for _ in range(m)]
for i in range(m):
  a,b=map(int,input().split())
  ab[i][0],ab[i][1]=b,a
ab.sort()
cnt=0
chk=0
for b,a in ab:
  if chk<=a:
    cnt+=1
    chk=b
print(cnt)

Submission status: Accepted

Solution code:
#coding: utf-8
import math
import heapq
import bisect
import numpy as np
from collections import Counter
#from scipy.misc import comb

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

ans = 0
brid = -1
for a,b in R:
    if a >= brid:
        brid = b
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
length, req = map(int, input().split(" "))
target = []
for i in range(req):
    s, e = map(int, input().split(" "))
    target.append([s, e])
target.sort(key = lambda x: x[1])
answer = 0
before_e = -1
for s, e in target:
    # print(before_e, s, e)
    if s < before_e:
        answer += 1
    else:
        before_e = e
print(req - answer)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n, m = [int(x) for x in input().strip().split()]
d = sorted([tuple([int(x) for x in input().strip().split()]) for _ in range(m)], key=lambda x: x[1])
ans = 0
p = d[0][1]
# print(d)
for l, r in d:
    if l < p:
        continue
    ans += 1
    p = r
else:
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ab=[]
for i in range(m):
    a,b=[int(x) -1 for x in input().split()]
    ab.append((a,b))
ab=sorted(ab,key=lambda x: x[1])
ans=0
last_bridge=-1
for a,b in ab:
    # print(a,b)
    if last_bridge<a:
        last_bridge=b-1
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
N,M = map(int,input().split())
AB = [list(map(int,input().split())) for i in range(M)]

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

remove = [-1]

for a,b in AB:
    if remove[-1] <= a:
        remove.append(b)

print(len(remove)-1)

Submission status: Accepted

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

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

bridge = ab[0][1] - 1
ans = 1
for i in range(m):
    s, t = ab[i][0], ab[i][1]
    if bridge < s:
        bridge = t - 1
        ans += 1

print(ans)

Submission status: Accepted

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

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

c = -float("inf")
ans = 0
for i in range(m):
    if c <= ab[i][0]:
        c = ab[i][1]
        ans += 1

print(ans)

Submission status: Accepted

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

a, b = ab[0]
ans = 1
prev = b - 1
for a, b in ab[1:]:
    if prev >= a:
        continue
    ans += 1
    prev = b - 1
print(ans)

Submission status: Accepted

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

p.sort()
mr = 0
c = 0
for l, r in p:
  if l >= mr:
    mr = r
    c += 1
    continue
  mr = min(mr, r)

print(c)

Submission status: Accepted

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

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

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

current_end = r[0][1]
cnt = 1
for i in range(1, m):
    if not r[i][0] <= current_end <= r[i][1]:
        cnt += 1
        current_end = r[i][1]
print(cnt)

Submission status: Accepted

Solution code:
from operator import itemgetter
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
l.sort(key=itemgetter(1))
mini,ans=l[0][1],1
for i in range(1,m):
  if mini<=l[i][0]:
    ans+=1
    mini=l[i][1]
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter

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

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

li.sort(key=itemgetter(1,0))

#print(li)

ans = 0
prevcut = -1
for a, b in li:
  if a < prevcut and prevcut <= b:
    continue
  ans += 1
  prevcut = b
  
print(ans)

Submission status: Accepted

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

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

cnt = 1
s = AB[0][1]
for a, b in AB[1:]:
    if s <= a:
        cnt += 1
        s = b
print(cnt)

Submission status: Accepted

Solution code:
##貪欲法(greedy)
#区間スケジューリング
#D - Islands War
#https://atcoder.jp/contests/abc103/tasks/abc103_d

n, m = list(map(int,input().split()))
lst = [list(map(int,input().split())) for _ in range(m)]
lst.sort(key=lambda x: x[1])
ans = []
ans.append(lst[0])

for i in range(1,m):
    if ans[-1][1] <= lst[i][0]:
        ans.append(lst[i])

print(len(ans))

Submission status: Accepted

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


def make_sorted_pairs(a_list, b_list):
    return list(sorted(
        tuple(sorted((a, b))) 
        for a, b in zip(a_list, b_list)
    ))


def is_in_range(bridges_range, west):
    b_west, b_east = bridges_range
    if b_east <= west:
        return False
    return True


def update_range(bridges_range, west, east):
    b_west, b_east = bridges_range
    return max(b_west, west), min(b_east, east)


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    pairs = make_sorted_pairs(a, b)
    bridges_range = (-1, -1)
    n_broken = 0
    for west, east in pairs:
        if is_in_range(bridges_range, west):
            bridges_range = update_range(bridges_range, west, east)
            continue
        bridges_range = west, east
        n_broken += 1
    print(n_broken)
    return


# Generated by 1.1.6 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
    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()