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())
req = []
for _ in range(m):
    a, b = map(int, input().split())
    req.append((a, b))

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

ans = 0
pre = 0

for i in range(m):
    a, b = req[i]
    if a < pre:
        continue
    pre = b
    ans += 1
    
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split()) # 入力が複数
# [int(i) for i in input().split()] # 配列で数字
# seg or imos 違った。
req = []
for _ in range(m):
    a, b = map(int, input().split())
    req.append((a, b))
req.sort(key=lambda x: x[1])
ans = 0
pre = 0
for a, b in req:
    if a >= pre:
        ans += 1
        pre = b
print(ans)

Submission status: Accepted

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


war = sorted(war,key=lambda x:x[1])
a = 0
ans = 0
for i in range(M):
    if a <= war[i][0]:
        a= war[i][1]
        ans +=1
    else:
        continue
print(ans)

Submission status: Accepted

Solution code:
import numpy as np

N,M=map(int, input().split())
a=[]
b=[]
for _ in range(M):
  t = list(map(int, input().split()))
  a.append(t)
  b += [t[1]]

b = np.array(b)
idx = np.argsort(b)
a=np.array(a)
a=a[idx]

n=1
r = a[0][1]
for i in range(M):
  if r <= a[i][0]:
    n+=1
    r=a[i][1]

print(n)

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest


def resolve():
    # ★get input
    n, m = map(int, input().split())

    demands = [[int(i) for i in input().split()] for j in range(m)]

    # 要望を[1]の昇順で並べ替え(後述する[1]-1の場所に橋を作る、という方法の効率を最大化するため、らしい。
    # 右側から徐々に橋を取り除くイメージ。
    demands = sorted(demands,key=lambda x:x[1])

    # 最後に取り除いた橋
    new_remove_bridge = 0
    # 取り除いた橋の数
    remove_bridge_count = 0

    for demand in demands:

        # 最後に取り除いた橋では分断できない島に対する要望を受けた場合
        # 例
        # 島1-除-島2-除-島3----島4 <= 2-3間の橋を取り除いた状態で・・3-4間の橋を取り除いてほしい、と言われた場合。
        if new_remove_bridge  < demand[0]:
            new_remove_bridge = demand[1] -1
            remove_bridge_count += 1

    print(str(remove_bridge_count))



class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """5 2
1 4
2 5"""
        output = """1"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """9 5
1 8
2 7
3 5
4 6
7 9"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5"""
        output = """4"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

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

Submission status: Accepted

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

import sys

def main():
    n, m = map(int, input().split())
    a = []
    b = []
    atoi = [[] for i in range(n)]
    btoi = [[] for i in range(n)]
    for i in range(m):
        aa, bb = map(int, sys.stdin.readline().split())
        a.append(aa - 1)
        b.append(bb - 1)
        atoi[aa - 1].append(i)
        btoi[bb - 1].append(i)

    achieved = [False for i in range(m)]
    res = 0
    aptr = -1  # Already achieved
    for x in range(n - 1):
        tobreak = False
        for i in btoi[x + 1]:
            if not achieved[i]:
                tobreak = True
        if tobreak:
            res += 1
            while aptr < x:
                aptr += 1
                for j in atoi[aptr]:
                    achieved[j] = True
    print(res)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

import sys
from collections import defaultdict

def main():
    n, m = map(int, input().split())
    a = []
    b = []
    atoi = defaultdict(list)
    btoi = defaultdict(list)
    for i in range(m):
        aa, bb = map(int, sys.stdin.readline().split())
        a.append(aa - 1)
        b.append(bb - 1)
        atoi[aa - 1].append(i)
        btoi[bb - 1].append(i)

    achieved = [False for i in range(m)]
    res = 0
    aptr = -1  # Already achieved
    for x in range(n - 1):
        tobreak = False
        for i in btoi[x + 1]:
            if not achieved[i]:
                tobreak = True
        if tobreak:
            res += 1
            while aptr < x:
                aptr += 1
                for j in atoi[aptr]:
                    achieved[j] = True
    print(res)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

from collections import defaultdict

def main():
    n, m = map(int, input().split())
    a = []
    b = []
    atoi = defaultdict(list)
    btoi = defaultdict(list)
    for i in range(m):
        aa, bb = map(int, input().split())
        a.append(aa - 1)
        b.append(bb - 1)
        atoi[aa - 1].append(i)
        btoi[bb - 1].append(i)

    achieved = [False for i in range(m)]
    res = 0
    aptr = -1  # Already achieved
    for x in range(n - 1):
        tobreak = False
        for i in btoi[x + 1]:
            if not achieved[i]:
                tobreak = True
        if tobreak:
            res += 1
            while aptr < x:
                aptr += 1
                for j in atoi[aptr]:
                    achieved[j] = True
    print(res)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# nいらんな
# -####-------
# ----##------
# --####------
# -----###----
# -------- ##-
# みたいな感じで終端でソートするといい感じに見えてくる


_, m = map(int, input().split())
interval = []
for _ in range(m):
    interval.append(list(map(int, input().split())))
interval = sorted(interval, key=lambda x: x[1])
divide_pos = -1
ans = 0
for itv in interval:
    if divide_pos < itv[0]:
        ans += 1
        divide_pos = itv[1] - 1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
a = [[0,0] for i in range(m)]
for i in range(m) :
  a0,a1 = map(int,input().split())
  a[i][:] = a0-1,a1-1

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

ans = [0 for i in range(n-1)]
ans[a[0][1]-1] = 1
right = a[0][1]-1
for i in range(1,m) :
  if right < a[i][0] :
    ans[a[i][1]-1] = 1
    right = a[i][1]-1
    
print(sum(ans))

Submission status: Accepted

Solution code:
def main():
    N, M = map(int, input().split())
    kukan_list = sorted([list(map(int, input().split())) for _ in range(M)], key=lambda x: x[1])
    ans = 0
    cut = 0
    
    for kukan in kukan_list:
        if cut >= kukan[0]:
            continue
        ans += 1
        cut = kukan[1] - 1
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

ng_dic={}
for i in range(M):
  a,b=map(int,input().split())
  if not a in ng_dic:
    ng_dic[a]=b
  else:
    ng_dic[a]=min(b,ng_dic[a])
    
ng_dic=sorted(ng_dic.items())
#print(ng_dic)

answer=0
right=N+1
for key,value in ng_dic:
  #print(key,value)
  right=min(right,value)
  #print(key,right)
  if key>=right:
    answer+=1
    right=value
  
print(answer+1)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
bridges = [list(map(int,input().split())) for _ in range(M)]
bridges.sort(key=lambda x: x[1])
cut = -1
ans = 0
for b in bridges:
    if b[0] <= cut <= b[1]:
        continue
    else:
        cut = b[1]-1 # なるべく後続にも影響する範囲を切る
        ans += 1
print(ans)

Submission status: Accepted

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

from collections import deque
from copy import copy,deepcopy
from itertools import permutations,combinations
from pprint import pprint

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

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

n,m = myinput()
ab = [ list(myinput()) for _ in range(m) ]
# print(ab)

ab_sorted = mysort(ab,1)
# print(ab_sorted)

count = 0
e = 0
for i in range(m):
    ns = ab_sorted[i][0]
    ne = ab_sorted[i][1]
    if ns>=e:
        count += 1
        e = ne
    else:
        pass
print(count)

Submission status: Accepted

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

ba.sort()
removed_id = 0 # 取り除かれた橋の中で最も右の橋
ans = 0
for b, a in ba:
  if a >= removed_id:
    ans += 1
    removed_id = b

print(ans)

Submission status: Accepted

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

ab.sort(key=lambda x:x[1])
cnt=0
dis=-1
for i in range(M):
  if dis<ab[i][0]:
    cnt+=1
    dis=ab[i][1]-1
print(cnt)

Submission status: Accepted

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

remove = ab[0][1]
res = 1
for i in range(m):
    if remove <= ab[i][0]:
        res += 1
        remove = ab[i][1]

print(res)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
data = []
for i in range(m):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    data.append((b,a))
data.sort()
cnt = 0
dis = -1
for i in range(m):
    b,a = data[i]
    if(dis < a):
        cnt += 1
        dis = b - 1
print(cnt)

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

Submission status: Accepted

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab = sorted(ab, key=lambda x:x[1])
ans = 0
left, right = ab[0]
for a, b in ab[1:]:
    if a <= left and right <= b:
        continue
    if left < a and right > a:
        left = a 
        right = min(right, b)
    else:
        ans += 1
        left = a 
        right = b
print(ans+1)

Submission status: Accepted

Solution code:
# coding: utf-8
N,M=map(int,input().split())
AB=[]

for i in range(M):
    AB.append(list(map(int,input().split())))

AB.sort()

INF=10**9
ans=0
bottom=INF

for i in range(M):
    a,b=AB[i]
    
    if a>=bottom:
        ans+=1
        bottom=INF
    
    bottom=min(bottom,b)

print(ans+1)

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
brid = -1
for a,b in ab:
    if a > brid:
        c += 1
        brid = b-1
print(c)

Submission status: Accepted

Solution code:
import numpy as np

def main():
  N,M = map(int,input().split())
  ab=[]
  for _ in range(M):
    a,b = map(int,input().split())
    ab.append([b,a])
  ab.sort()
  tmp=0
  count = 0
  for i in range(M):
    if ab[i][1] >= tmp:
      tmp = ab[i][0]
      count += 1
  print(count)

main()

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
AB = []
for _ in range(M):
    a, b = map(int, input().split())
    AB.append((a, b))
AB.sort(key=lambda x: x[1])
cnt = 1
x = AB[0][1]
for a, b in AB:
    if a <= x - 1 <= b and a <= x <= b:
        continue
    else:
        cnt += 1
        x = b
print(cnt)

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
A = sorted([list(map(int,input().split())) for _ in range(M)],key=lambda x:x[1])
cnt = 1
cur = A[0][1]
for i in range(1,M):
    if A[i][0]<cur:continue
    cur = A[i][1]
    cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
n, m = [int(x) for x in input().split()]
ab = [[int(x) for x in input().split()] for _ in range(m)]
ab.sort(key=lambda x: x[1])
removed = []
for a, b in ab:
    if not any(a <= x < b for x in removed):
        removed.append(b - 1)
print(len(removed))

Submission status: Accepted

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

S = sorted(S, key=lambda x: x[1])
res = 1
cur = S[0][1]
for i in range(M):
    if S[i][0] < cur:
        continue
    cur = S[i][1]
    res += 1

print(res)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

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

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

B.sort()
ans = 1
tmp = B[0][0]
for upper, lower in B[1:]:
  if lower >= tmp:
      tmp = upper
      ans += 1

print(ans)

Submission status: Accepted

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

LI.sort()
#print(LI) #debug
ans = 0
bridge = 0
for i in range(m):
    d, c = LI[i]
    #print(bridge) #debug
    if bridge < c:
        bridge = d-1
        ans += 1

print(ans)

Submission status: Accepted

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

n, m = [int(x) for x in input().split()]

islands = [set() for _ in range(n + 1)]

for _ in range(m):
    ab = [int(x) for x in input().split()]
    islands[min(ab)].add(max(ab))

ans = 0

for i in range(1, n):
    if i + 1 in islands[i]:
        ans += 1
    elif len(islands[i]) > 0:
        islands[i + 1].add(min(islands[i]))

ans += len(islands[n])

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from collections import defaultdict
N, M = list(map(int, input().split()))

edge_dict = defaultdict(set)
A, B = [], []
for i in range(M):
    a, b = list(map(int, input().split()))
    A.append(a)
    B.append(b)
A = np.array(A)
B = np.array(B)
inds = np.argsort(B)

last_connected_node = 0
cnt = 0
for a, b in zip(A[inds], B[inds]):
    if last_connected_node <= a:
        last_connected_node = b
        cnt += 1
print(cnt)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
p = [list(map(int,input().split())) for _ in range(m)]
p.sort()
a1 = p[0][0]
b1 = p[0][1]
ans = 1

for i in range(1,m):
    a2 = p[i][0]
    b2 = p[i][1]
    if b1 <= a2:
        ans += 1
        a1 = a2
        b1 = b2
    else:
        if a1 < a2:
            a1 = a2
        if b1 > b2:
            b1 = b2

print(ans)

Submission status: Accepted

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

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

ans = 0
cur_end = -float("inf")

for st, en in spans:
    if cur_end > st:
        continue
    ans += 1
    cur_end = en
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter

N, M = map(int, input().split())
AB = []
for _ in range(M):
    AB.append(list(map(int, input().split())))
AB.sort(key=itemgetter(1,0))
# print(AB)

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

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
numbers=[]
for _ in range(M):
    a,b=input().split()
    numbers.append([int(b),int(a)])
new_numbers=sorted(numbers)
answers=[]
while new_numbers:
    large = new_numbers[0][0]
    if  not new_numbers[0] in answers:
        answers.append(new_numbers[0])
    new_numbers=[a for a in new_numbers if a[1]>=large]
print(len(answers))

Submission status: Accepted

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

from operator import itemgetter
st = sorted(ab, key=itemgetter(1))
last = 0
ans = 0
for s, t in st:
    #print(x, l)
    if s >= last:
        ans += 1
        last = t
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])

bef=-1
cnt = 0
for one in ab:
    if one[0]<=bef and bef<=one[1]:
        continue
    else:
        bef = one[1]-1
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
ts = [list(map(int,input().split()))[::-1] for i in range(M)]
ts.sort()

count=0
tmp=0

for i in ts:
  if i[1]>=tmp:
    count += 1
    tmp = i[0]
print(count)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
S = []
for i in range(M):
    a, b = map(int, input().split())
    S.append([a, b])
    
from operator import itemgetter
S = sorted(S, key=itemgetter(1))
ans = 0
last = -1*float('Inf')
for si in S:
    if si[0] >= last:
        ans += 1
        last = si[1]
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ts = [list(map(int,input().split()))[::-1] for j in range(m)]

ts.sort()

count = 0
t = 0

for j in range(m):
  if ts[j][1]>=t:
    count+=1
    t = ts[j][0]
    
print(count)

Submission status: Accepted

Solution code:
from sys import stdin

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

ab.sort()

inf = 10 ** 9

left = -inf
right = inf

ans = 1

for a, b in ab:
    if left <= a and a < right:
        left = a
        if left < b and b <= right:
            right = b
    elif left < b and b <= right:
        right = b
    else:
        ans += 1
        left = a
        right = b

if M == 0:
    print(0)
else:
    print(ans)

Submission status: Accepted

Solution code:
from sys import stdin

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

ab.sort()

inf = 10 ** 9

left = -inf
right = inf

ans = 1

for a, b in ab:
    if left <= a and a < right:
        left = a
        if left < b and b < right:
            right = b
    elif left < b and b < right:
        right = b
    else:
        ans += 1
        left = a
        right = b

if M == 0:
    print(0)
else:
    print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter

n, m = [int(i) for i in input().split()]

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

for a in ab:
    # a が removed より大きい = まだ取り除いてない
    if a[0] > removed:
        #print(a)
        removed = a[1] - 1
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class UnionFind():
    def __init__(self, n):
        self.n = n
        # parents[i]: 要素iの親要素の番号
        # 要素iが根の場合、parents[i] = -(そのグループの要素数)
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    # 要素xが属するグループの要素数を返す
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # 要素xが属するグループに属する要素をリストで返す
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    # 全ての根の要素をリストで返す
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    # グループの数を返す
    def group_count(self):
        return len(self.roots())
    # 辞書{根の要素: [そのグループに含まれる要素のリスト], ...}を返す
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    # print()での表示用
    # all_group_members()をprintする
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N, M = MAP()
L = [LIST() for i in range(M)]
A = [0] * N
# graph = defaultdict(list)
L = sorted(L, key=lambda x: x[1])
tmp = L[0][1]
ans = 1
for a, b in L:
    if a < tmp <= b:
        continue
    else:
        ans += 1
        tmp = b
print(ans)

Submission status: Accepted

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

ans = 1
b_edge  = section[0][1]
del section[0]

for a, b in section:
    if b_edge<= a:
        b_edge = b
        ans +=1
    elif b < b_edge:
        b_edge = b
    elif a < b_edge <= b:
        b_edge = b_edge
print(ans)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
A = []
B = []
all = []
for _ in range(M):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)
    all.append([a,b])
all = sorted(all,key=lambda x:x[1])
MinBar = 1
abar = all[0][0]
bbar = all[0][1]

for i in range(1,M):
    if all[i][0] < bbar:
        bbar = min(bbar,all[i][1])
    else:
        MinBar += 1
        abar = all[i][0]
        bbar = all[i][1]
print(MinBar)

Submission status: Accepted

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

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

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

for temp in base:
  if t <= temp[0]:
    count = count + 1
    t = temp[1]

print(count)

Submission status: Accepted

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

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))
bridge = 0
ans = 0

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
intervals = [list(map(int, input().split())) for _ in range(M)]
intervals.sort(key=lambda ab: ab[1])
ans = 1
position = intervals[0][1]
for i in range(1,M):
  if position <= intervals[i][0]:
    ans += 1
    position = intervals[i][1]
print(ans)

Submission status: Accepted

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

ab.sort(key=lambda x: x[1])
sub = -1
ans = 0
for i in range(m):
    if ab[i][0] <= sub and ab[i][1] > sub:
        continue
    else:
        ans += 1
        sub = ab[i][1] - 1

print(ans)

Submission status: Accepted

Solution code:
import sys


N, M = map(int, input().split())
bridge = [[] for _ in range(N)]
for x in sys.stdin.readlines():
    a, b = map(int, x.split())
    a -= 1; b -= 1
    bridge[a].append(b)

ans = 0
near = N
for i in range(N):
    if near == i:
        ans += 1
        near = N
    for e in bridge[i]:
        near = min(near, e)

print(ans)

Submission status: Accepted

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

# 区間スケジューリング

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

cnt = 0
right = -1
for A,B in AB:
    if A >= right:
        cnt += 1
        right = B

print(cnt)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ab = []
for i in range(m):
    ab.append(list(map(int,input().split())))
cnt = m
ab.sort()
a0 = ab[0][0]
b0  = ab[0][-1]
for a,b in ab[1:]:
    if a < b0:
         cnt -=1
         b0 = min(b0,b)
    else:
        b0 = b
print(cnt)

Submission status: Accepted

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

def main():
    n, m = map(int, input().split())
    ab_list = [tuple(map(int, input().split())) for _ in range(m)]
    ab_list.sort(key = itemgetter(1))
    del_max = -10
    ans = 0
    for ab in ab_list:
        if ab[0] - 1 > del_max:
            ans += 1
            del_max = ab[1] - 2
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

request = sorted(request, key=lambda x:x[1])
broken = -1
ans = 0
for a, b in request:
    if a > broken:
        broken = b - 1
        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)]
ranges = [[] for _ in range(m)]
for i in range(m):
    a,b = map(int,input().split())
    ranges[i] = [a,b]
ranges = sorted(ranges, key = lambda x:x[1])
MAX = - float("inf")
ans = 0
for i in range(m):
    if MAX <= ranges[i][0]:
        MAX = ranges[i][1]
        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)]
ranges = [[] for _ in range(m)]
for i in range(m):
    a,b = map(int,input().split())
    ranges[i] = [a,b]
ranges = sorted(ranges, key = lambda x:x[1])
MAX = - float("inf")
ans = 0
for i in range(m):
    if MAX < ranges[i][0]:
        MAX = ranges[i][1] - 0.1
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
l_rng = []
for i in range(m):
    l_rng.append( list(map(int,input().split()) ) )
l_rng.sort(key=lambda x:x[1])    
#初期
r_isl = l_rng[0][1]
cnt = 1

for i in l_rng:
  if  r_isl <= i[0]:
    r_isl = i[1] 
    cnt = cnt + 1
print(cnt)

Submission status: Accepted

Solution code:
from operator import itemgetter
n, m = map(int, input().split())
yobo = []
for _ in range(m):
    a, b = map(int, input().split())
    yobo.append((a, b))

yobo = sorted(yobo, key=itemgetter(1))
ans = 0
rem = -1

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

print(ans)

Submission status: Accepted

Solution code:
n,m = [int(x) for x in input().split()]
li = []
for _ in range(m):
    li.append([int(x) for x in input().split()])
z = sorted(li,key=lambda x:x[1])
ans = 0
res = 0
for i in z:
    if res < i[0]:
        ans += 1
        res = i[1]-0.5
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
box = [list(map(int, input().split())) for _ in range(M)]
box = sorted(box, key= lambda x: x[1])
rmax = box[0][1]
ans = 1
for i in range(1, M):
    if box[i][0] >= rmax:
        rmax = box[i][1]
        ans += 1
    else:
        continue
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
A=[[0]*2 for i in range(m)]
for i in range(m):
  A[i]=list(map(int,input().split()))
A.sort(key=lambda x:x[1])
B=[A[0][1]-1]
for i in range(m):
  if A[i][0]<=B[-1] and B[-1]<A[i][1]:
    pass
  else:
    B.append(A[i][1]-1)
print(len(B))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
INF = 10**6

def main():
    n,m=map(int,input().split())
    G=[INF]*n
    for _ in range(m):
        a,b=map(int,input().split())
        a-=1
        b-=1
        G[a]=min(G[a],b)
    
    lim=INF
    cnt=0
    for i in range(n):
        if lim==i:
            cnt+=1
            lim=G[i]
        else:
            lim=min(lim,G[i])
    
    print(cnt)
if __name__=='__main__':
    main()

Submission status: Accepted

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

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

for a,b in AB:
    if cut<=a:
        cnt +=1
        cut=b

print(cnt)

Submission status: Accepted

Solution code:
import sys
import math
mod=10**9+7
inf=float("inf")
from math import sqrt
from collections import deque
from collections import Counter
input=lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(11451419)
from functools import lru_cache
#メモ化再帰defの冒頭に毎回 @lru_cache(maxsize=10**10)
#引数にlistはだめ
#######ここまでテンプレ#######
#######ここから天ぷら########
n,m=map(int,input().split())
query=[]
for i in range(m):
    a,b=map(int,input().split())
    query.append([a,b])
query.sort(key=lambda x:x[1])

tekyo=-1
kazu=0
for i in range(m):
    a,b=query[i][0],query[i][1]
    if tekyo<a: #キレてない
        tekyo=b-1
        kazu+=1
print(kazu)