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())
table=[]
for i in range(M):
    a,b=map(int,input().split())
    table.append((a-1,b-2))
table.sort()
s=0
t=N
ans=0
for a,b in table:
    if t<a:
        ans+=1
        s=a
        t=b
    else:
        s=a
        t=min(t,b)
        #print(s,t)
print(ans+1)

Submission status: Accepted

Solution code:
N, M = list(map(int, input().split()))
L = []
for i in range(N):
	L.append(100001)
for i in range(M):
	ab = list(map(int, input().split()))
	ab.sort()
	if L[ab[0] - 1] > ab[1] - 1:
		L[ab[0] - 1] = ab[1] - 1 

c = 0
x = 100001
for i in range(N - 1):
	if L[i] == 100001:
		if i == x:
			c += 1
			x = 100001
	else:
		if i == x:
			c += 1
			x = 100001

		if L[i] < x:
				x = L[i]
	
if x == 100001:
	print(c)
else:
	print(c + 1)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
c=[]
for i in range(m):
  a,b=map(int,input().split())
  c.append([a,b])
c.sort()
bridge=0
key=1
for i in range(m):
  if c[i][1]<=key:
    key=c[i][1]
  if c[i][0]>=key:
    bridge+=1
    key=c[i][1]
print(bridge)

Submission status: Accepted

Solution code:
def solve(xys):
    count = 0
    right = 0
    xys.sort(key=lambda x: x[0])
    for a, b in xys:
        if right <= a:
            count += 1
            right = b
        elif b < right:
            right = b
    return count

if __name__ == "__main__":
    n, m = map(int, input().split())
    xys = [[int(s) for s in input().split()] for _ in range(m)]
    print(solve(xys))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
v = [0 for i in range(n+1)]
path = [0 for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    if v[b] < a:
        v[b] = a

last = 0

for i in range(n+1):
    if v[i] == 0:
        continue
    m = v[i]

    if last < m:
        path[i - 1] = 1
        last = i - 1


s = 0
for p in path:
    s += p
print(s)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
B = []
for i in range(M):
    (a, b) = map(int, input().split())
    B.append((a, b))
B = sorted(B, key=lambda x: x[0])


def update(x, y):
    if x[0] == y[0]:
        return (x[0], min(x[1], y[1]))
    if x[1] <= y[0]:
        return False
    else:
        return (y[0], min(x[1], y[1]))


now = B[0]
count = 0
for i in range(1, M):
    ans = update(now, B[i])
    # print(ans)
    if ans:
        now = ans
    else:
        count += 1
        now = B[i]
count += 1
print(count)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
mx =[-1 for i in range(0,n)]
for z in range(0,m):
  a,b=map(int,input().split())
  mx[b-1]=max(mx[b-1],a-1)
cut=-1
cn=0
for z in range(0,n):
	if cut<mx[z]:
		cut=z-1
		cn=cn+1
print(cn)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
list=[]
for i in range(m):
    a,b=map(int,input().split())
    list.append([max(a,b),min(a,b)])
list.sort()
a=1
b=0
k=0
while list!=[]:
    j=list[0]
    if k>j[1]:
        list.remove(j)
    elif j[0]<a:
        list.remove(j)
    else:
        list.remove(j)
        b+=1
        a=j[0]+1
        k=j[0]
print(b)

Submission status: Accepted

Solution code:
N, M = [int(elem) for elem in input().split(' ')]
request_list = [[int(elem) for elem in input().split(' ')] for _ in range(M)]
assert len(request_list) == M
assert len(request_list[0]) == 2

# sort request_list in the ascending order
request_list.sort(key=lambda x: x[0])

def is_overlap(a, b):
    if max(a) <= min(b) or max(b) <= min(a):
        return False
    else:
        return True


count = 1
current_list = request_list[0]
for i in range(1, M):
    if is_overlap(current_list, request_list[i]):
        current_list = [max(current_list[0], request_list[i][0]), \
                        min(current_list[1], request_list[i][1])]
    else:
        count += 1
        current_list = request_list[i]

print(count)

Submission status: Accepted

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

Query = []
for _ in range(M):
    Query.append(list(map(int, input().split())))


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

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

Submission status: Accepted

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


br_ = []
q = 0

for i in br:
    a = i[0]
    if q == a:
        continue
    else:
        br_.append(i)
    q = a

ans = []
w = br_[0]
for i in br_[1:]:
    if i[0] < w[1]:
        w = [i[0], min(i[1], w[1])]
    else:
        ans.append(w)
        w = i

print(len(ans)+1)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
ab = sorted(set(map(lambda x: (x[0], x[1]) if x[0] < x[1] else (x[1],x[0]), [list(map(int, input().split())) for _ in range(M)])))

ans = 0
e = 10**6
for m in ab:
    a, b = m
    if e <= a:
        ans += 1
        e = b
    if b < e:
        e = b
print(ans + 1)

Submission status: Accepted

Solution code:
def merge(arr, l, m, r):
    n1 = m - l + 1
    n2 = r- m
 
    # create temp arrays
    L = [0,0] * (n1)
    R = [0,0] * (n2)
 
    # Copy data to temp arrays L[] and R[]
    for i in range(0 , n1):
        L[i] = arr[l + i]
 
    for j in range(0 , n2):
        R[j] = arr[m + 1 + j]
 
    # Merge the temp arrays back into arr[l..r]
    i = 0     # Initial index of first subarray
    j = 0     # Initial index of second subarray
    k = l     # Initial index of merged subarray
 
    while i < n1 and j < n2 :
        if L[i][0] <= R[j][0]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1
 
    # Copy the remaining elements of L[], if there
    # are any
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1
 
    # Copy the remaining elements of R[], if there
    # are any
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1
 
# l is for left index and r is right index of the
# sub-array of arr to be sorted
def mergeSort(arr,l,r):
    if l < r:
 
        # Same as (l+r)/2, but avoids overflow for
        # large l and h
        m = (l+(r-1))//2
 
        # Sort first and second halves
        mergeSort(arr, l, m)
        mergeSort(arr, m+1, r)
        merge(arr, l, m, r)
n,m=map(int,input().split())
arr=[]
for i in range(m):
    arrx=list(map(int,input().split()))
    arr.append(arrx)
mergeSort(arr,0,m-1)
ans=0
x1=arr[0][0]
y1=arr[0][1]
for i in range(m):
    if(arr[i][0]>=y1):
        ans+=1
        x1=arr[i][0]
        y1=arr[i][1]
    else:
        x1=max(x1,arr[i][0])
        y1=min(y1,arr[i][1])
ans+=1
print(ans)

Submission status: Accepted

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

k = []
for _ in range(m):
    k.append(list(map(int,input().split())))

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

#print(k)
l=0
ans = 0
for i in range(m):
#    print(l,k[i][0])
    if l <= k[i][0]:
        ans += 1
        l = k[i][1]
    
    
print(ans)

Submission status: Accepted

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

L.sort()

c = 0
pa, pb = 0, 0
for a, b in L:
    if pb <= a:
        c += 1
        pa, pb = a, b
    else:
        pa, pb = max(pa, a), min(pb, b)

print(c)

Submission status: Accepted

Solution code:
from operator import itemgetter

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

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

ans = 1
limit = ab[0][1]

for i in range(1, m):
	if ab[i][0] >= limit:
		ans += 1
		limit = ab[i][1]

print(ans)

Submission status: Accepted

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

D = defaultdict(lambda: N+1)
for i in range(M):
    a,b = map(int,input().split())
    if b<D[a]:D[a]=b
        
side_b_min = N+1
ans = 0
for i in range(1,N+1):
    if i == side_b_min:
        side_b_min = N+1
        ans += 1
    if D[i] < side_b_min: side_b_min = D[i]
    #print(i,side_b_min)
    
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return list(map(int, input().split()))
N, M = inpl()

E = []
for _ in range(M):
    E.append(inpl())

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

ans = 0
c = 0
for a, b in E:
    if a < c:
        continue
    else:
        ans += 1
        c = b
print(ans)

Submission status: Accepted

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

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

count = 0
start = -1
for a in A:
    if a[0] >= start:
        count += 1
        start = a[1]
print(count)

Submission status: Accepted

Solution code:
N, M = map( int, input().split())
Q = []
for i in range(M):
    a,b = map(int,input().split())
    Q.append([a,b])
Q = sorted(Q)
ans = 1
LQ = len(Q)
while LQ != 0:
    stan = Q[0][1]
    k = 1
    while LQ != 0:
        if Q[0][0] < stan:
            stan = min(stan,Q.pop(0)[1])
            LQ -= 1
        else:
            ans += 1
            break
print(ans)

Submission status: Accepted

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

AB.sort()

result = 1

x1, x2 = 1, N
for a, b in AB:
    # print(x1, x2, a, b)
    if x2 <= a:
        # print("*")
        result += 1
        x1, x2 = a, b
    else:
        x1 = max(x1, a)
        x2 = min(x2, b)

print(result)

Submission status: Accepted

Solution code:
import sys

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

left, right = None, None
cnt = 0

for a, b in ab:
    a, b = min(a, b), max(a, b)
    if left is None:
        left, right = a, b
        continue
    if a < right and b > left:
        left = max(left, a)
        right = min(right, b)
    else:
        cnt += 1
        left, right = a, b

print(cnt + 1)

Submission status: Accepted

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

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

demands = sorted(demands)
last_splited = -1
splited = 0

for end, start in demands:
    if last_splited < end and start >= last_splited:
        last_splited = end
        splited += 1

print(splited)

Submission status: Accepted

Solution code:
n,m = (int(i) for i in input().split())
x = [[int(i) for i in input().split()] for i in range(m)]
x,a,b,ans = sorted(x),0,n+1,0
for i,j in x:
	if i>=a and j<=b: a,b = i,j
	elif b>i>=a: a = i
	elif j<=b: b = j
	else: ans,a,b = ans+1,i,j
print(ans+1)

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

cur = 0
ans = 0
for a,b in AB:
    if cur > a:
        continue
    
    ans += 1
    cur = b

print(ans)

Submission status: Accepted

Solution code:
import sys
N, M = map(int, sys.stdin.readline().split())
lst = []
for i in range(M):
    a, b = map(int, sys.stdin.readline().split())
    lst.append((a, 1, i))
    lst.append((b, 0, i))
lst.sort()
open_set = set()
cnt = 0
for pos, t, idx in lst:
    if t == 0:
        if idx in open_set:
            cnt += 1
            open_set = set()
    else:
        open_set.add(idx)
print(cnt)

Submission status: Accepted

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

ans = 0
minb = N
for a,b in src:
    if a >= minb:
        ans += 1
        minb = b
    else:
        minb = min(minb,b)
if src[-1][0] < minb:
    ans += 1
print(ans)

Submission status: Accepted

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

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

l = 0
for i in range(m):
  if e[i][0] < l:
    continue
  else:
    l = e[i][1]
    ret += 1
    
print(ret)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
s=[[0]*m for _ in range(2)]
for k in range(m):
	i,j=map(int,input().split())
	s[1][k]=i
	s[0][k]=j

u=sorted([list(x) for x in list(zip(*s))])
#print(u)
s0=0
ans=0
for i in range(m):
	if s0<=u[i][1]:
		s0=u[i][0]
		ans+=1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A = []
for i in range(M):
  a, b = map(int, input().split())
  A.append([a - 1, b - 1])
A = sorted(A, key=lambda a: a[0])
cut = 1
b_min = N
for a in A:
  if a[0] >= b_min:
    cut += 1
    b_min = N
  b_min = min(b_min, a[1])
print(cut)

Submission status: Accepted

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

AB.sort()

Ans = 0
l,r = 1,N
for ab in AB:
    a,b = ab
    if r <= a:
        Ans += 1
        l,r = a,b
    else:
        l = max(l,a)
        r = min(r,b)
else:
    Ans += 1

print(Ans)

Submission status: Accepted

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

ans=1
l=A[0][0]
r=A[0][1]

for i in range(1,M):
  a,b = A[i]
  if r <= a or l >= b:
    ans+=1
    l=a
    r=b
  else:
    l=a
    r=min(r,b)

print(ans)

Submission status: Accepted

Solution code:
n,m=input().split()
n=int(n)
m=int(m)
l=[]
for i in range(m):
    t=input().split()
    l.append((int(t[0]),int(t[1])))
l.sort()
i=0
res=0
flag=False
while True:
    ra=l[i][1]
    while l[i][0]<ra:
        if i==m-1:
            flag=True
            break
        ra=min(ra,l[i][1])
        i+=1
    res+=1
    if flag:
        break
print(res)

Submission status: Accepted

Solution code:
N,M = map(int, raw_input().split())
a = [0]*M
b = [0]*M
for i in range(M):
  a[i],b[i] = map(int, raw_input().split())
  a[i] -= 1
  b[i] -= 1

A = [[] for _ in range(N)]
B = [[] for _ in range(N)]
for i in range(M):
  A[a[i]] += [i]
  B[b[i]] += [i]

ans = 0
F = [False]*M
T = []
for i in range(N):
  for t in B[i]:
    if not F[t]:
      ans += 1
      for x in T:
        F[x] = True
      T = []
  for t in A[i]:
    T += [t]
print ans

Submission status: Accepted

Solution code:
n,m = map(int, raw_input().split())
ps = [map(int, raw_input().split()) for _ in range(m)]
ps.sort()
ps.reverse()
v = 10**100
ret = 0
for a,b in ps:
 if b <=v:
  ret += 1
  v = a
print ret

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N, M = reads()
cond = []
for _ in range(M):
  a, b = reads()
  cond.append((a-1, b-1))
cond.sort()

count = 0
end = -1
for a, b in cond:
  if a < end:
    end = min(end, b)
  else:
    count += 1
    end = b
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 - 1, 2, i))
    ab.append((b - 1, 1, i))

ab.sort()
ans = 0
separated = [False] * m
buf = set()
for island, ab, i in ab:
    if ab == 1:
        if separated[i]:
            continue
        else:
            ans += 1
            for j in buf:
                separated[j] = True
            buf.clear()
    else:
        buf.add(i)
print(ans)

Submission status: Runtime Error

Solution code:
def IslandsWar():
    n, m = map(int, input().split())
    a = [0 for _ in range(n-1)]
    INF = float('INF')
    for _ in range(m):
        x, y = map(int, input().split())
        for i in range(x-1, y-1):
            if abs(x-y) == 1:
                a[i] = INF
            else:
                a[i] += 1

    ans =  0
    count = 0
    status = False
    for i in range(n-2):
        if a[i] == INF:
            ans += 1
        elif a[i] < a[i+1]:
            status = True
        elif a[i] > a[i+1] and status:
            ans += 1
            count = 0
            status = False
        elif a[i] == a[i+1]:
            count += 1
        else:
            if count != 0:
                ans += 1
            count = 0
    if count != 0:
        ans += 1
    if a[-2] < a[-1]:
        ans += 1
    if a[-1] == INF:
        ans += 1
    print(ans)
            
if __name__ == "__main__":
    IslandsWar()

Submission status: Runtime Error

Solution code:
import sys
N, M = map(int, input().split())
A = [tuple(map(int, line.split())) for line in sys.stdin.buffer.readlines()]
A.sort()
cnt = 0
R = 0
for a, b in A:
    if R <= a:
        cnt += 1
        R = b
    elif b < R:
        R = b
print(cnt)

Submission status: Runtime Error

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[0])
 
table = dp2(0, N, N)
 
for i in range(M):
    s, t = mi()
    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)

Submission status: Runtime Error

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

ab = [0] * M
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: Runtime Error

Solution code:
a=[""]*m
b=[""]*m
for i in range(m):
    x,l=map(int,input().split())
    a[i]=x*10+5
    b[i]=l*10-5
st=sorted([(a[i],b[i]) for i in range(m)], key=itemgetter(1))
ans=0
last=0
last=-float("inf")
for i in range(m):
    if last<st[i][0]:
        ans+=1
        last=st[i][1]
print(ans)

Submission status: Runtime Error

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

left = 0
ans = 0


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

Submission status: Runtime Error

Solution code:
n = int(input())
lst = []
for i in range(n):
  x, l = map(int, input().split())
  left = x - l
  right = x + l
  lst.append([left, right])

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

ans = 1
limit = lst[0][1]
for i in range(n):
  if lst[i][0] >= limit:
    ans += 1
    limit = lst[i][1]

print(ans)

Submission status: Runtime Error

Solution code:
#区間スケジューリング
n, m = map(int, input().split())
lst = []
for _ in range(m):
    a, b = map(int, input().split())
    lst.append([a, b])

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

ans = 0
ed = 0
for _ in lst:
    if _[0] < ed:
    else:
        ed = _[1]
        ans += 1
print(ans)

Submission status: Runtime Error

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

cnt = 0
last = -float('inf')
for left, right in islands:
    if last <= left:
        cnt += 1
        last = right

print(cnt)

Submission status: Runtime Error

Solution code:
from operator import itemgetter

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

a = []
b = []

for i in range(M):
    ao,bo = map(int,input().split())
    a.append(ao)
    b.append(bo)

ab = sorted([(a[i],b[i]) for i in range(M)], key = itemgetter(1))

ans = 0
last = 0

for i in range(N):
    if last <= ab[i][0]:
        ans += 1
        last = ab[i][1]

print(ans)

Submission status: Runtime Error

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

ab.sort()
l=1,r=N
ans=1
for a,b in ab:
  l=max(a,l)
  r=min(b,r)
  if l>=r:
    ans+=1
    l=a
    r=b
print(ans)

Submission status: Runtime Error

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

count=1
mae=s[0][1]
for i in range(1,N):
    if s[i][0]>=mae:
        count+=1
        mae=s[i][1]

print(count)

Submission status: Runtime Error

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

count=1
mae=[0][1]
for i in range(1,N):
    if s[i][0]>=mae:
        count+=1
        maes[i][1]

print(count)

Submission status: Runtime Error

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

count=1
mae=[0][1]
for i in range(1,N):
    if s[i][0]>=mae:
        count+=1
        mae=kukan[i][1]

print(count)

Submission status: Runtime Error

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

Submission status: Runtime Error

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=0
border=0

for item in ab:
    if item[0]>=border:
        border=item[1]
        cnt+=1

print(cnt)

Submission status: Runtime Error

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])
ans=[ab[0]]
for i in range(1:m):
    if ans[-1][1]<=ab[i][0]:
        ans.append(ab[i])
print(len(ans))

Submission status: Runtime Error

Solution code:
s

Submission status: Runtime Error

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: Runtime Error

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

count += 0
t = 0

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

Submission status: Runtime Error

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,k=map(int,input().split())
A=list(map(int,input().split()))
#n,k=5,3
#A=[-30,-10,10,20,40]
ans=inf
for i in range(n-k+1):
    ans=min(ans, abs(A[i])+abs(A[i]-A[i+k-1]), abs(A[i+k-1])+abs(A[i+k-1]-A[i]) )
print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
l=[True for _ in range(n+1)]
q=[]
for _ in range(n):
  x,y=map(int,input().split())
  a,b=max(x,y),min(x,y)
  q.append([a,b])
q=sorted(q,reverse=True)
count=0
print(q)
for y,x in q:
  if all(l[x:y])==False:
    continue
  else:
    l[y-1]=False
    count+=1
    print(l)

print(count)

Submission status: Runtime Error

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

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:
  if b_min > b:
    b_min = b
    continue
  if b_min > a:
    count += 1
    b_min = b

print(count)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
read=sys.stdin.buffer.read
N,M,*a=map(int,read().split())
a=np.reshape(a,(M,2))
c=np.zeros((M,N-1),int)
for i in range(M):
  for j in range(a[i][0]-1,a[i][1]-1):
    c[i,j]+=1
res=0
while np.any(c==1):
  max_c=np.argmax(np.sum(c,axis=0))
  for i in range(M):
    if c[i][max_c]==1:
      c[i][:]=0
  res+=1
print(res)

Submission status: Runtime Error

Solution code:
import numpy as np
N,M=list(map(int,input().split()))
a=[list(map(int,input().split())) for _ in range(M)]
c=np.zeros((M,N-1),int)
for i in range(M):
  for j in range(a[i][0]-1,a[i][1]-1):
    c[i,j]+=1
res=0
while np.any(c==1):
  max_c=np.argmax(np.sum(c,axis=0))
  for i in range(M):
    if c[i][max_c]==1:
      c[i][:]=0
  res+=1
print(res)

Submission status: Runtime Error

Solution code:
import numpy as np
N,M=list(map(int,input().split()))
a=[list(map(int,input().split())) for _ in range(M)]
c=np.zeros((M,N),int)
for i in range(M):
  for j in range(a[i][0]-1,a[i][1]):
    c[i,j]+=1
res=0
while np.any(c==1):
  max_c=np.argmax(np.sum(c,axis=0))
  for i in range(M):
    if c[i][max_c]==1:
      c[i][:]=0
  res+=1
print(res)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
p = []
for i in range(n):
  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
    continue
  c += 1
  mr = min(mr, r)

print(c)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
ab_lis =[]
for i in range(m):
    a,b = map(int, input().split())
    ab_lis.append([b,a])
ab_lis.sort()
count = 0
bridge = [1]*(n-1)
for lis in ab_lis:
    b = lis[0]
    a = lis[1]
    if sum(bridge[a:b])/len(bridge[a:b]) == 1 and b >= 2:
        bridge[b-2] = 0
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
ab_lis =[]
for i in range(m):
    a,b = map(int, input().split())
    ab_lis.append([b,a])
ab_lis.sort()
count = 0
bridge = [1]*(n-1)
for lis in ab_lis:
    b = lis[0]
    a = lis[1]
    if sum(bridge[a:b])/len(bridge[a:b]) == 1:
        bridge[b-2] = 0
        count += 1
print(count)

Submission status: Runtime Error

Solution code:
import numpy as np

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

mt = np.zeros([M, N])

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

flag = 1
cnt = 0
while flag:
    cnt += 1
    tmp = np.sum(mt, axis=0)
    ID = np.argmax(tmp)
    mt[mt[:, ID] == 1] = 0
    
    if np.sum(mt)==0:
        flag = 0
            
print( cnt)

Submission status: Runtime Error

Solution code:
import numpy as np

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

mt = np.zeros([M, N])

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

flag = 1
cnt = 0
while flag:
    cnt += 1
    tmp = np.sum(mt, axis=0)
    ID = np.argmax(tmp)
    for j in range(M):
        if mt[j, ID] == 1:
            mt[j] = np.zeros([N])
    if np.sum(mt)==0:
        flag = 0
            
print( cnt)

Submission status: Runtime Error

Solution code:
from operator import itemgetter

n, m = map(int, input().split())
r = sorted([list(map(int, input().split())) for _ in range(m)], key = itemgetter(0))

if m == 0:
    print(0)
    exit()

last = r[1][0]
i = 1
count = 0
for i in range(m):
    if last <= r[i][0]:
        last = r[i][1]
        count += 1

print(count)

Submission status: Runtime Error

Solution code:
#D - Islands War
import numpy as np
import copy
N,M = (int(i) for i in input().split()) 
a_tmp = [[int(i) for i in input().split()] for i in range(M)] 
a = copy.deepcopy(a_tmp)
cnt = 0
def cal(a,cnt):
    l = np.zeros(N+1)
    flg = np.zeros(M)
    for i in range(len(a)):
        l[a[i][0]:a[i][1]] += 1
    tmp = l.argmax()
    cnt += 1
    #print("tmp:"+str(tmp))
    #tmpを区間に含むリストにフラグを立てる
    tmp_index = []
    for j in range(len(a)):
        if a[j][0]<=tmp<a[j][1]:
            #print(j)
            tmp_index.append(j)
    #print(tmp_index)
    if len(tmp_index)>0:
        for k in range(len(tmp_index)-1,-1,-1):
            #print(k)
            a.pop(tmp_index[k])
    #print(a)
    if len(a)<=0:
        return cnt
    else:
        return cal(a,cnt)
print(cal(a,0))

Submission status: Runtime Error

Solution code:
import numpy as np

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

request_arr = np.zeros((M, N-1),dtype=np.int)

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




for counter in range(1,100000):
    max_index = np.argmax(request_arr.sum(axis=0))
    delete_raw = []
    for i in range(len(request_arr)):    
        if request_arr[i][max_index] == 1:
            delete_raw.append(i)
    request_arr = np.delete(request_arr,delete_raw,0)
    
    if len(request_arr) == 0:
        ans=counter
        break

print(ans)

Submission status: Runtime Error

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



print(pro_con_module.SectionScheduling(L))

Submission status: Runtime Error

Solution code:

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

from operator import itemgetter
def SectionScheduling(array):
    if len(array)>0:
        array.sort(key=itemgetter(1))
        pos=array[0][1]
        array.sort()
        for i in range(len(array),-1):
            if array[i][0]<=pos:
                array.remove(i)

        return 1 + SectionScheduling(array)
    else:
        return 0

print(SectionScheduling(L))

Submission status: Runtime Error

Solution code:
a=[]
b=[]
for i in range(m):
    a_,b_=map(int,input().split())
    a.append(a_)
    b.append(b_)
ab=sorted([(a[i],b[i]) for i in range(m)],  key=itemgetter(1))  

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
a = []
for i in range(m):
  x,y = map(int, input().split())
  a.append((x,y))
a.sort()
ans = 1
l,r = a[0][]
for x,y in a[1:]:
  if r <= x:
    ans += 1
    r = x
    l = y
  else:
    r = max(r, y)
print(ans)