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 = [[0 for j in range(3)] for i in range(2)]　2行3列の場合
S = [[0 for j in range(2)] for i in range(M)]

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


T=sorted(S,key=lambda x:x[1])
#U=sorted(T,key=lambda x:x[1])



count=1
last=T[0][1]
#print(T)
for i in range(1,M):
    if T[i][0]>=last:
        count+=1
        last=T[i][1]
print(count)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############
N,M = IL()
data = ILL(M)
data.sort(reverse=True)

L,R = data.pop()
count = 0
while data:
  l,r = data.pop()
  if l>=R:
    count += 1
    L = l
    R = r
  else:
    L = l
    if r<R:
      R = r
print(count+1)

Submission status: Accepted

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

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
schedule = []
for i in range(M):
    start, end = map(int, input().split())
    schedule.append((start, end))               # schedule = (始点、終点)

schedule = sorted(schedule, key=lambda x: x[1])
ans = 0
end = -10**12                                   # 始点の最小値

for i in range(M):
    if end <= schedule[i][0]:                   # 重複が OK ならば等号を加える
        end = schedule[i][1]                    # 終点でソートされているので、自動的に可能な中で最速の終点が選ばれている
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# Segment tree (+)
from operator import add
from sys import stdin


class SegmentTree:
    _f = None
    _data = None
    _offset = None
    _size = None

    def __init__(self, size, f):
        self._f = f
        self._size = size
        t = 1
        while t < size:
            t *= 2
        self._offset = t - 1
        self._data = [0] * (t * 2 - 1)

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

    def query(self, start, stop):
        def iter_segments(data, l, r):
            while l < r:
                if l & 1 == 0:
                    yield data[l]
                if r & 1 == 0:
                    yield data[r - 1]
                l = l // 2
                r = (r - 1) // 2
        f = self._f
        it = iter_segments(self._data, start + self._offset,
                           stop + self._offset)
        result = next(it)
        for e in it:
            result = f(result, e)
        return result


readline = stdin.readline

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

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

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

Submission status: Accepted

Solution code:
# Segment tree (+)
class SegmentTree:
    _f = None
    _data = None
    _offset = None
    _size = None

    def __init__(self, size, f):
        self._f = f
        self._size = size
        t = 1
        while t < size:
            t *= 2
        self._offset = t - 1
        self._data = [0] * (t * 2 - 1)

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

    def query(self, start, stop):
        def iter_segments(data, l, r):
            while l < r:
                if l & 1 == 0:
                    yield data[l]
                if r & 1 == 0:
                    yield data[r - 1]
                l = l // 2
                r = (r - 1) // 2
        f = self._f
        it = iter_segments(self._data, start + self._offset,
                           stop + self._offset)
        result = next(it)
        for e in it:
            result = f(result, e)
        return result


from sys import stdin
readline = stdin.readline

from operator import add

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

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

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

Submission status: Accepted

Solution code:
# D - Islands War

N, M = map(int, input().split())
Q = []
for _ in range(M):
    a, b = map(int, input().split())
    Q.append((a, b))
Q.sort(key = lambda x: x[1])

ans = []
for i in range(M):
    (a, b) = Q[i]
    if ans == [] or ans[-1] < a:
        ans.append(b-1)
    else:
        continue
print(len(ans))

Submission status: Accepted

Solution code:
n , m = map(int,input().split())
war = [[] for i in range(n-1)]
for i in range(m):
    a , b = map(lambda x:int(x)-1,input().split())
    war[a].append(b)
utan = n
ans = 0
for i in reversed(range(n-1)):
    for j in war[i]:
        if utan >= j:
            ans += 1
            utan = i
            break
print(ans)

Submission status: Accepted

Solution code:
# Binary indexed tree
from sys import stdin
readline = stdin.readline


def bit_add(bit, i, x):
    i += 1
    n = len(bit)
    while i <= n:
        bit[i - 1] += x
        i += i & -i


def bit_sum(bit, i):
    result = 0
    i += 1
    while i > 0:
        result += bit[i - 1]
        i -= i & -i
    return result


def query(bit, start, stop):
    if start == 0:
        return bit_sum(bit, stop - 1)
    else:
        return bit_sum(bit, stop - 1) - bit_sum(bit, start - 1)


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

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

bit = [0] * (N - 1)
result = 0
for a, b in ab:
    a, b = a - 1, b - 1
    if query(bit, a, b) != 0:
        continue
    result += 1
    bit_add(bit, b - 1, 1)
print(result)

Submission status: Accepted

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

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

ab = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, readline().split())
    ab[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 ab[i]:
        dp[j] = max(dp[j], dp[i] + 1)

print(dp[N])

Submission status: Accepted

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

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

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

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


from sys import stdin
readline = stdin.readline

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

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N, M = mi()
Q = li2(M)
'''
l = [N]*N
for i in range(M):
    ind = max(0, Q[i][0]-1)
    l[ind] = min(Q[i][1]-1, l[ind])

for i in reversed(range(N-1)):
    l[i] = min(l[i], l[i+1])

cnt = 0
i = 0

while True:
    i = l[i]
    cnt += 1
    if l[i] == N:
        break

print(cnt)
'''

dp = [0]*N
#rel = [[] for _ in range(N)]
rel = [N]*N
for s, t in Q:
    rel[s-1] = min(t-1, rel[s-1])

#dp[0] = 0
for i in range(N-1):
    dp[i+1] = max(dp[i], dp[i+1])
    if rel[i] != N:
        dp[rel[i]] = max(dp[i] + 1, dp[rel[i]])

print(dp[N-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))
 
N, M = mi()
Q = li2(M)
Q = sorted(Q, key=lambda x:x[1])
 
#table = dp2(0, N, N)
 
#for i in range(M):
    #s, t = mi()
    #for i in range(t):
    #table[s-1][t-1] = 1
 
#for i in reversed(range(N-1)):
    #for j in range(i, N):
        #table[i][j] = max(table[i+1][j], table[i][j])
 
#print(table)
'''
i = j = 0
cnt = 0
while True:
    while j < N and table[i][j] == 0:
        j += 1
    if j >= N:
        break
    cnt += 1
    i = j
 
print(cnt)
'''
 
l = [N]*N
for i in range(M):
    ind = max(0, Q[i][0]-1)
    l[ind] = min(Q[i][1]-1, l[ind])
 
for i in reversed(range(N-1)):
    l[i] = min(l[i], l[i+1])
 
cnt = 0
i = 0
#print(l)
while True:
    i = l[i]
    cnt += 1
    if l[i] == N:
        break
 
print(cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N, M = mi()
Q = li2(M)
Q = sorted(Q, key=lambda x:x[1])

l = [N]*N
for i in range(M):
    ind = max(0, Q[i][0]-1)
    l[ind] = min(Q[i][1]-1, l[ind])

for i in reversed(range(N-1)):
    l[i] = min(l[i], l[i+1])

cnt = 0
i = 0
#print(l)
while True:
    i = l[i]
    cnt += 1
    if l[i] == N:
        break

print(cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N, M = mi()
Q = li2(M)
#Q = sorted(Q, key=lambda x:x[1])

l = [N]*N
for i in range(M):
    ind = max(0, Q[i][0]-1)
    l[ind] = min(Q[i][1]-1, l[ind])

for i in reversed(range(N-1)):
    l[i] = min(l[i], l[i+1])

cnt = 0
i = 0
#print(l)
while True:
    i = l[i]
    cnt += 1
    if l[i] == N:
        break

print(cnt)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
y = [list(map(int,input().split())) for _ in range(m)]
y.sort(key=lambda x:x[1])
s = y[0][1]-0.5
ans = 1
for i in range(1,m):
    a,b = y[i]
    if a < s < b:
        continue
    else:
        ans += 1
        s = b-0.5
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[0])
br=set([])
ans=0
now=[0,n+1]
for a,b in ab:
  #print('now',now)
  if now[1]<=a:
    ans+=1
    now=[a,b]
  else:
    now[0]=a
    now[1]=min(now[1],b)
print(ans+1)

Submission status: Accepted

Solution code:
import sys
#print(316736)
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from operator import itemgetter
N,M=map(int,readline().split())
ab=[]
#print(112)
for i in range(M):
    x,y=map(int,readline().split())
    ab.append((x,y))
#print(111)
ab=sorted(ab,key=itemgetter(1))
ans=0
x=0
for a,b in ab:
    #print(a,x,b)
    if a<=x:
        continue
    x=b-1
    ans+=1
print(ans)

Submission status: Accepted

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


def main():
  N, M = list(map(int, input().split()))
  A_B = [list(map(int, input().split())) for _ in range(M)]

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

  added = [A_B[0][1]]
  for i in range(1, M):
    pre_b = added[-1]
    a, b = A_B[i]
    if pre_b <= a:
      added.append(b)

  print(len(added))


if(__name__ == '__main__'):
  main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
L = []
for _ in range(m):
    a, b = map(int, input().split())
    L.append((a, b))
L = sorted(L, key=lambda x: x[1])
ans = 0
r = -float('inf')
for i in L:
    if i[0] >= r:
        ans += 1
        r = i[1]
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
debug = lambda *a, **kw: print(*a, **dict(file=sys.stderr, **kw))

N, M = inm()


def solve():
    xs = []
    for i in range(M):
        a, b = inm()
        xs.append((a, True, i))
        xs.append((b, False, i))
    xs.sort()
    cut = 0
    opn = set()
    closed = set()
    for x, start, i in xs:
        if start:
            opn.add(i)
        elif i in closed:
            closed.remove(i)
        else:
            cut += 1
            opn.remove(i)
            closed |= opn
            opn = set()
    assert not opn
    assert not closed
    return cut


print(solve())

Submission status: Accepted

Solution code:
from operator import itemgetter
n, m = map(int, input().split())
ab = sorted([list(map(int, input().split()))
             for i in range(m)], key=itemgetter(1))

removed = -1

ans = 0

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
a=[list(map(int,input().split())) for i in range(M)]
a.sort(key=lambda x:x[1])
j=0
k=0
ans=0
for i in range(M):
  if i==0:
    k=a[i][1]
    j=k-1
    ans+=1
  else:
    if a[i][0]<=j:
      continue
    else:
      k=a[i][1]
      j=k-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))

ans = 0
removed = -1

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

Submission status: Accepted

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

ab = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    ab[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 ab[i]:
        dp[j] = max(dp[j], dp[i] + 1)

print(dp[N])

Submission status: Accepted

Solution code:
from operator import itemgetter

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

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

removed = -1
ans = 0

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

Submission status: Accepted

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def main():
    n, m = i_map()
    num_list = i_row_list(m)

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

    count = 0
    tmp = 0
    for num in num_list:
        if num[0] < tmp:
            continue
        tmp = num[1]
        count += 1

    print(count)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def Main():
    n,m = IL()
    war = [list(IL()) for _ in range(m)]
    war.sort(key=lambda x: x[1])
    pre = war[0][1]-2
    ans = 1
    for rep in war:
        if pre<rep[0]-1:
            pre = rep[1]-2
            ans += 1
    print(ans)
    return

if __name__=='__main__':
    Main()

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 = sorted(l, key=itemgetter(1))
ans = 0
last = 0
for i in range(m):
    if last <= l_sort[i][0]:
        last = l_sort[i][1]
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():

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

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

    INF = 10**10
    cur = -INF
    cnt = 0

    for i in range(M):
        if A[i][0] < cur:
            continue
        else:
            cur = A[i][1]
            cnt += 1
    print(cnt)


resolve()

Submission status: Accepted

Solution code:
import sys
from collections import deque
def input(): return sys.stdin.readline().strip()


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

    """
    aについて昇順に貪欲法を考えて破綻しました。。。
    （その後aの昇順にdpすることも考えたけど同じく行き詰まり）
    bについての昇順なら貪欲法がうまく回ります。
    「貪欲法はあらゆる変数に対して考えるべし」ということなのか？
    """
    dislike.sort(key=lambda x: x[1])
    cnt = 0
    last = -1 # 最後に落とした橋
    for a, b in dislike:
        if a <= last: continue
        cnt += 1
        last = b - 1
    print(cnt)



if __name__ == "__main__":
    main()

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

now = ab[0][1] - 1
count = 1

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

print(count)

Submission status: Accepted

Solution code:
def solve():
    ret = 0
    most_right = 0
    for left, right in sects:
        if left < most_right:
            continue
        ret += 1
        most_right = right
    print(ret)

if __name__ == "__main__":
    N, M = map(int, input().split())
    sects = []
    for _ in range(M):
        sects.append(list(map(int, input().split())))
    sects.sort(key=lambda x: x[1])
    solve()

Submission status: Accepted

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


ans = 0
X = 0
for L, R in conflict:
    if L <= X:
        continue
    X = R-1
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
itv=[]
for i in range(m):
  a,b=map(int,input().split())
  start=min(a,b)
  end=max(a,b)
  itv.append([end,start])
t,ans=0,0
itv=sorted(itv)
for e,s in itv:
  if t<=s:
    t=e
    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])
ans=0
t=-1
for a,b in ab:
  if a>=t:
    ans+=1
    t=b
print(ans)

Submission status: Accepted

Solution code:
# kaisetsu
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

right=-1
for a,b in ab:
  if a<right:
    continue
  ans+=1
  right=b
print(ans)

Submission status: Accepted

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

N, M = map(int, input().split())
AB = []
for _ in range(M):
    ai, bi = map(int, input().split())
    AB.append((ai, bi))
AB = sorted(AB, key=lambda x: x[1])

ans, x = 0, 0

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

Submission status: Accepted

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

itv.sort()

ans, x = 0, 0
for [b, a] in itv:
    if a > x:
        ans += 1
        x = b - 1

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
ab=[list(map(int, input().split())) for _ in range(m)]
# bに注目してソート
ab = sorted(ab, key=lambda x: x[1])
ans=0
left=-1
for i in range(m):
    if ab[i][0]<=left<ab[i][1]:
        continue
    left=ab[i][1]-0.5
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
import math

def resolve():
    N, M = list(map(int, input().split()))
    AB = sorted([list(map(int, input().split())) for _ in range(M)], key=lambda x: x[1])
    broken = None
    cnt = 0
    for ab in AB:
        a, b = ab
        if broken and a <= broken < b:
            continue
        broken = b-1
        cnt += 1
    print(cnt)

    

if '__main__' == __name__:
    resolve()

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
	N, M = NMI()
	querys = [NLI() for _ in range(M)]
	querys.sort(key=lambda x: x[1])
	ans = 0
	last = 0
	for a, b in querys:
		if a <= last < b:
			continue
		last = b-1
		ans += 1
	print(ans)


if __name__ == "__main__":
	main()

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


s = ab[0][0]
e = ab[0][1]
ans = 1

for i in range(m):
    if (ab[i][0] <= s and e <= ab[i][1]) or s < ab[i][0] < e or s < ab[i][1] < e:
        continue

    ans += 1
    s = ab[i][0]
    e = ab[i][1]

print(ans)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict

    n, m = map(int, readline().split())
    cum = [0] * n

    war = defaultdict(list)

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

    ans = 0
    cur = n + 1
    for i in range(1, n + 1):
        if cur == i:
            ans += 1
            cur = n + 1
        ng = war[i]
        if ng:
            cur = min(cur, min(ng))

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math
import sys
from collections import deque
import copy
import itertools
from itertools import permutations
def mi() : return map(int,sys.stdin.readline().split())
def ii() : return int(sys.stdin.readline().rstrip())
a,b=mi()
l=[list(mi()) for _ in range(b)]
l=sorted(l,key=lambda x:x[1])
q=deque([1,1])
ans=0
for i,j in l:
  y=q.pop()
  x=q.pop()
  if i<x:
    q.append(x)
    q.append(y)
  else:
    ans+=1
    q.append(j)
    q.append(j)
print(ans)

Submission status: Accepted

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

AB = []
for _ in range(M):
    a, b = map(int, input().split())
    AB.append((a, b))
AB = sorted(AB, key=lambda x: x[1])

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

Submission status: Accepted

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

AB = []
for _ in range(M):
    a, b = map(int, input().split())
    AB.append((a, b))
AB = sorted(AB, key=lambda x: (x[1], x[0]))

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
graph = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
r = n
ans = 0
for i in range(n):
    if i>=r:
        ans += 1
        r = n
    if not graph[i]:
        continue
    mi = min(graph[i])
    r = min(r, mi)
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
n,m = map(int,input().split())
a = [list(map(int,input().split())) for i in range(m)]
a = sorted(a, key=itemgetter(1))
bridge = [a[0][1]-1]
for i in range(1,m):
    if a[i][0] <= max(bridge):
        continue
    else:
        bridge.append(a[i][1]-1)
print(len(bridge))

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

c_l = 0
c_r = n+1

res = 0
for i, v in enumerate(ab):
    a, b = v
    if c_r <= a:
        res += 1
        c_l = a
        c_r = b
    else:
        c_l = max(c_l, a)
        c_r = min(c_r, b)

print(res+1)