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

Solution code:
n,m = map(int, input().split())
a = []
for i in range(n):
  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)

Submission status: Runtime Error

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

# ToDo not yet

# biについて昇順にソートする
# それぞれのbiについて、
# 1: すでに分断されているなら何もしない
# 2: 分断されていないならbi - 1番目の橋を切断する
from typing import List, Any

N, M = map(int, input().split())
demand_list = []
for _ in range(M):
    ai, bi = map(int, input().split())
    demand_list.append([ai, bi])

# ソート
demands = sorted(demand_list, key=lambda d: d[1])

# 分断開始 切断されている橋は1で表現される
cut_bilagge_list = [0 for _ in range(N)]

for demand in demands:
    # すでに分断されているのかをチェックする
    if len([1 for i in cut_bilagge_list[demand[0] - 1:demand[1] - 1] if i == 1]) > 0:
        continue

    # 分断されていないので bi - 2の橋を切断する
    cut_bilagge_list[demand[1] - 2] = 1


print(sum(1 for bilagge in cut_bilagge_list if bilagge == 1))

Submission status: Runtime Error

Solution code:
def main():
    input = sys.stdin.readline
    n, m = map(int, input().split())
    a_b = [list(map(int, input().split())) for i in range(m)]
    a_b.sort(key=itemgetter(1))
    end = a_b[0][1]-2
    ans = 1 
    for i in range(m):
        if a_b[i][0]-1 > end:
            end = a_b[i][1]-2
            ans += 1
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
B = sorted([a-i-1 for i, a in enumerate(A)])
if (N%2): median = B[N//2]
else: median = (B[(N-1)//2] + B[N//2])//2
print(sum([abs(b-median) for b in B]))

Submission status: Runtime Error

Solution code:
from operator import itemgetter
bridges = []
for i in range(M):
    bridges.append(list(map(int, input().split())))
bridges.sort(key=itemgetter(1))
b_right = 0
cnt = 0
for a,b in bridges:
    if a > b_right:
        b_right = b - 1
        cnt += 1
print(cnt)

Submission status: Runtime Error

Solution code:
n , m = map(int,input().split())
war = []
for _ in range(m):
    a , b = map(int,input().split())
    war.append([a,b])
war.sort()
ans = 1
min_right = min(war[0][1] , war[1][1])
max_left = max(war[0][0] , war[1][0])
for i in range(0,m - 1):
    now_left, now_right = war[i][0], war[i][1]
    next_left , next_right = war[i + 1][0] , war[i + 1][1]
    min_right = min(min_right , next_right)
    max_left = max(max_left,next_left)
    if max_left >= min_right:
        ans += 1
        min_right = next_right
print(ans)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
ab = [[int(i) for i in input().split()] for i in range(m)]
count = 0
while len(ab) > 0:
    ab = sorted(ab, key = lambda x: x[1])
    end = ab[0]
    list.sort(ab, reverse=True)
    remove = ab.index(end)
    while ab[remove][0] == end[0]:
        remove += 1
    del ab[(remove - 1):]
    count += 1
print(int(count))

Submission status: Runtime Error

Solution code:
class BIT():
	def __init__(self, n):
		self.n = n
		self.bit = [0]*(n+1)
	
	def getsum(self, k):
		ret = 0
		while k:
			ret += self.bit[k]
			k -= k&-k
		return ret
		
	def p_sum(self, i, j):
		return self.getsum(j)-self.getsum(i-1)
		
	def add(self, k, x):
		while k <= n:
			self.bit[k] += x
			k += k&-k

n,m,*t=map(int,open(0).read().split())
q=sorted([(a,b) for a,b in zip(*[iter(t)]*2)],key=lambda x:x[1]-x[0])
bit=BIT(n-1)
c=0
for a,b in q:
	if bit.p_sum(a,b-1)==0:
		bit.add(a,1)
		bit.add(b-1,1)
		c+=1
print(c)

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
wars = {}
for i in range(m):
  a, b = map(int, input().split())
  if a in frontiers.keys():
    frontiers[a] = min(frontiers[a], b)
  else:
    wars[a] = b

cuts = 0
frontier = 10**6

for i in range(1, n):
  if i in frontiers.keys():
    antis = min(frontier, wars[i])
  if i + 1 == frontier:
    cuts += 1
    frontier = 10**6
    
print(cuts)

Submission status: Runtime Error

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], reverse = True)
ab = sorted(ab)

def find_seed(ab, t):
	if len(ab) == 0:
		return 1
	if t[0] <= ab[0][0] < t[1]:
		t = [ab[0][0], min([ab[0][1],t[1]])]
		ab.pop(0)
		return find_seed(ab,t)

	return 1

ans = 0

while len(ab) > 0:
	t = ab.pop(0)
	ans += find_seed(ab,t)

print(ans)

Submission status: Runtime Error

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], reverse = True)
ab = sorted(ab)

def find_seed(ab, t):
	if len(ab) == 0:
		return 1
	if t[0] <= ab[0][0] < t[1]:
		t = [ab[0][0], min([ab[0][1],t[1]])]
		ab.pop(0)
		if len(ab) == 0:
			return 1
		else:
			return find_seed(ab,t)

	return 1

ans = 0

while len(ab) > 0:
	t = ab.pop(0)
	ans += find_seed(ab,t)

print(ans)

Submission status: Runtime Error

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

left = [""] * (n - 2)
right = [""] * (n - 2)

for i in range(m):
    a, b = map(int, input().split())
    left[a - 1] = "["
    right[b - 2] = "]"

s = ""
for i in range(n):
    s += left[i]
    s += right[i]

count = 0
for i in range(len(s) - 1):
    if s[i:i+2] == "[]":
        count += 1
print(count)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
youbou = [map(int,input().split()) for x in range(m)]

import itertools
bridge = []
for y in range(n-1):
    for x in itertools.combinations([x+1 for x in range(n-1)],y+1):
        bridge.append(x)
        
import numpy as np
flag = 0
for x in bridge:
    all_result = [0 for x in range(m)]
    for y in x:
        result = []
        for route in youbou:
            if (y>=int(route[0]))&(y+1<=int(route[1])):
                result.append(1)
            else:
                result.append(0)
        all_result += np.array(result)
    if 0 not in all_result:
        print(len(x))
        break

Submission status: Runtime Error

Solution code:
#取り除く橋は西側が出来るだけ大きいやつから取り除いても無駄がない
#（なぜならそうでない橋を取り除いた後にも上の橋を取り除かねばならないので）
N,M = map(int,input().split())
ab =[list(map(int,input().split())) for i in range(M)]
ab.sort(reverse=True)
ans = 0
tmp = inf
for i in range(M):
    if ab[i][1] > tmp:
        continue
    else:
        ans += 1
        tmp = ab[i][0]
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.sort()
AB.append([float('inf'),float('inf')])
ans,reset,left,right=0,1,0,float('inf')
for i in range(m)t:
    right=min(right,AB[i][1])
    left=AB[i][0]
    if right==left+1 and left!=AB[i+1][0]:
      ans+=1
      right=float('inf')
if right!=float('inf'):
  ans+=1
print(ans)

Submission status: Runtime Error

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

def solve(n, pairs):
    pairs.sort(key=lambda pair: pair[1])
    cnt = 0
    while pairs:
        _, b0 = pairs[0]
        cnt += 1
        for (a, b) in pairs:
            if a < b0:
                pairs.remove((a, b))
    return cnt

n, m = map(int, input().split())
pairs = [[int(c) for c in input().split()] for _ in range(m)]
print(solve(n, pairs))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
w=[]
if n<99:
    print(w[1])
for i in range(m):
    a,b=map(int,input().split())
    w.append((a,b))
w.sort(reverse=True)
d=[]
for i in range(m):
    a,b=w.pop()
    if i==0:
        d.append([a,b])
    else:
        if d[-1][1]<=a:
            d.append([a,b])
        elif d[-1][1]>b:
            d[-1][1]=b
print(len(d))

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
w=[]
if n>99:
    print(w[1])
for i in range(m):
    a,b=map(int,input().split())
    w.append((a,b))
w.sort(reverse=True)
d=[]
for i in range(m):
    a,b=w.pop()
    if i==0:
        d.append([a,b])
    else:
        if d[-1][1]<=a:
            d.append([a,b])
        elif d[-1][1]>b:
            d[-1][1]=b
print(len(d))

Submission status: Runtime Error

Solution code:
a

Submission status: Runtime Error

Solution code:
from typing import List
from preconditions import preconditions
import heapq


def solve(N: int, M: int, a: List[int], b: List[int]) -> int:
    q = []
    ret = 0
    conditions = sorted([(b[i], a[i]) for i in range(M)], key = lambda x: x[1])
    ci = 0
    for i in range(N+1):
        while ci < len(conditions) and i == conditions[ci][1]:
            heapq.heappush(q, conditions[ci])
            ci += 1
        if len(q) > 0 and i == q[0][0]-1:
            ret += 1
            q = []
    return ret





def main():
    N, M = list(map(int, input().split(' ')))
    a = []
    b = []
    for i in range(M):
        ai, bi = list(map(int, input().split(' ')))
        a.append(ai)
        b.append(bi)

    print(solve(N, M, a, b))



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n,m = [int(i) for i in input().split()]
e = [[int(j) for j in input().split()] for i in range(m)]
sorted(e,key= lambda x : x[1])
s=[]
for i in e:
  if i[0]<=s[-1] and s!=[]:
    pass
  else:
    s.append(i[1]-1)
    
print(len(s))

Submission status: Runtime Error

Solution code:
n,m = [int(i) for i in input().split()]
e = [[int(j) for j in input().split()] for i in range(m)]
sorted(e,key= lambda x : x[1])
s=[]
for i in e:
  if i[0]<=s[-1]:
    pass
  else:
    s.append(i[1]-1)
    
print(len(s))

Submission status: Runtime Error

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

s =[]
for cmd in e:
  if s==[]:
    s.append(cmd)
  else:
    found = False
    for tmp in s:
      if cmd[0]>=tmp[0] and cmd[0]<tmp[1]:
        tmp[0]=cmd[0]
        found = True
      if cmd[1]>tmp[0] and cmd[1]<=tmp[0]:
        tmp[1]=cmd[1]
        found = True
    if found == False:
      s.append(cmd)
      
print(len(size))

Submission status: Runtime Error

Solution code:
a_b = []
for _ in range(M):
    a, b = map(int, input().split())
    a_b.append((a, b))
a_b.sort(key=lambda x: x[0])

r = a_b[0][1]
ans = 1
for a, b in a_b[1:]:
    if a >= r:
        r = b
        ans += 1
        continue
    if b < r:
        r = b
print(ans)

Submission status: Runtime Error

Solution code:
from operator import itemgetter

def ans(ab, c):
    global i
    global tempcut
    #print(tempcut)
    #print(len(ab), i)
    if len(ab)-1 <i:
        print(c)
        return 0
    elif ab[i][0]< tempcut and tempcut<=ab[i][1]:
        i+=1
    else:
        tempcut=ab[i][1]
        c+=1
        i+=1
    ans(ab, c)



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

c=1
i=0
ab.sort(key=itemgetter(1))
tempcut=ab[0][1]
ans=ans(ab, c)

Submission status: Runtime Error

Solution code:
from operator import itemgetter

def ans(ab, c):
    global i
    global tempcut
    #print(tempcut)
    print(len(ab), i)
    if len(ab)-1 <i:
        print(c)
        return 0
    elif ab[i][0]< tempcut and tempcut<=ab[i][1]:
        i+=1
    else:
        tempcut=ab[i][1]
        c+=1
        i+=1
    ans(ab, c)



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

c=1
i=0
ab.sort(key=itemgetter(1))
tempcut=ab[0][1]
ans=ans(ab, c)

Submission status: Runtime Error

Solution code:
from operator import itemgetter

def ans(ab, c):
    global i
    global tempcut
    #print(tempcut)
    if len(ab) <=i:
        print(c)
        return 0
    if ab[i][0]< tempcut and tempcut<=ab[i][1]:
        i+=1
    else:
        tempcut=ab[i][1]
        c+=1
        i+=1
    ans(ab, c)



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

c=1
i=0
ab.sort(key=itemgetter(1))
tempcut=ab[0][1]
ans=ans(ab, c)

Submission status: Runtime Error

Solution code:
import sys

N, M = map(int, input().split())
ab = (tuple(map(int, line.split())) for line in sys.stdin.readlines())
ab.sort(key = lambda x : x[1])

ans = 0
last = -1
for a, b in ab:
    if a < last:
        continue
    else:
        ans += 1
        last = b

print(ans)

Submission status: Runtime Error

Solution code:
    def main():
        # Input
        [N, M] = list(map(int, input().rstrip().split(" ")))
        a, b = [], []
        for i in range(M):
            [_a, _b] = list(map(int, input().rstrip().split(" ")))
            a.append(_a)
            b.append(_b)
        output = solve(N, M, a, b)
        print(output)
     
    def solve(N, M, a, b):
        # 切断したい橋の候補をboolean値で表す
        bool_list = []
        for i in range(M):
            bool_list.append([True if (a[i] <= j+1) and (j+1 < b[i]) else False for j in range(N-1) ])
     
        S = [bool_list]
        counter = 0
        while S:
            C1 = S.pop()
            C2 = []
            l1 = C1.pop(0)
            for l2 in C1:
                l3 = l1 and l2
                l3 = [l1[i] and l2[i] for i in range(len(l1))]
                if sum(l3) == 0:
                    # 積が「すべてFalseになった場合」は別のループを回す
                    C2.append(l2)
                else:
                    l1 = l3
            if C2:
                # 別のループを回すためにSにpush
                S.append(C2)
            counter += 1
        return counter
     
    if __name__ == "__main__":
        main()

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
for i in range(M):
    a[i]=input().rstrip().split()
# 左側の島の一番大きい島の１個→に橋をたてていく
#　全て分割されたら終了
#　左側は昇順になっている？なっていなかったらそこ修正
a = [[]*2]*M
sum = 0#分割の数
hasi = [0]*(N-1)#どこの橋を壊したか
for i in range(0,M):
    c1 = int(a[M-1-i][0])
    c2 = int(a[M-1-i][1])
    f = [False]
    for m in range(c1-1,c2-1):
        if hasi[m]==1:
            f[0]=True
    if f[0]==True:
        continue
    else:
        hasi[c1-1]=1
        sum = sum+1



print(sum)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
a,b = [0 for i in range(M)],[0 for i in range(M)]
A,B = [0 for i in range(M)],[0 for i in range(M)]
t = 0
for i in range(M):
	a[i],b[i] = map(int,input().split())
	flug = -1
	for j in range(t):
		if a[i]<A[j] and b[i]>B[j]:
			A[j] = b[i]
			B[j] = a[i]
			flug = 1
	if flug = -1:
		A[t] = b[i]
		B[t] = a[i]
		t = t + 1

print(t)

Submission status: Runtime Error

Solution code:
ab=[]

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

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

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

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

Submission status: Runtime Error

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

Submission status: Runtime Error

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

main()

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
ab=[]

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

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

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

res=0
mark=0
while(1):
    for j in range(len(ab)):
        if abrs[0][1] > ab[j][0]:
            pass
        else:
            if mark!=j:res+=1
            mark=j
            break
    del ab[:mark]
    if len(ab)==1:
        res+=1
        break
    for j in range(len(abrs)):
        if ab[0][0] > abrs[j][0]:
            pass
        else:
            mark=j
            break
    del abrs[:mark]
    
print(res)

Submission status: Runtime Error

Solution code:
ab=[]

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

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

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

res=0
milestone=0
while(1):
    for j in range(len(ab)):
        if ab[0][1] < ab[j][0]:
          milestone=j
          res+=1
          break
    del ab[:milestone]
    if len(ab)==1:
        res+=1
        ab.remove(0)
    if len(ab)==0:
        break

print(res)

Submission status: Runtime Error

Solution code:
ab=[]

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

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

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

res=0
milestone=0
while(1):
    for j in range(len(ab)):
        if ab[0][1] < ab[j][0]:
          milestone=j
          res+=1
          break
    del ab[:milestone]
    if len(ab)==1:
      res+=1
      ab.remove(0)
    if len(ab)==0
      break

print(res)

Submission status: Runtime Error

Solution code:
ab=[]

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

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

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

res=0
milestone=0
while(1):
    for j in range(len(ab)):
        if ab[0][1] < ab[j][0]:
          milestone=j
          res+=1
          break
    ab.remove[0:milestone]
    if len(ab)==0:break

print(res)

Submission status: Runtime Error

Solution code:
ab=[]

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

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


abr=[]
enabled=[]
removed=[]
for i in range(m):
    abr.append(range(ab[i][0],ab[i][1]))
    enabled.append(False)
    removed.append(False)

res=0
for i in range(n):
    for j in range(len(abr)):
        if i == abr[j][0] and not removed[j]:
            enabled[j]=True
    for j in range(len(abr)):
        if i == abr[j][-1] and enabled[j]:
            res+=1
            for k in range(len(abr)):
                if enabled[k] and not removed[k]:
                    enabled[k]=False
                    removed[k]=True

print(res)

Submission status: Runtime Error

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

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

abr=[]
enabled=[]
removed=[]
for i in range(m):
    abr.append(range(ab[i][0],ab[i][1]))
    enabled.append(False)
    removed.append(False)

res=0
for i in range(n):
    for j in range(len(abr)):
        if i == abr[j][0] and not removed[j]:
            enabled[j]=True
    for j in range(len(abr)):
        if i == abr[j][-1]:
            res+=1
            for k in range(len(abr)):
                if enabled[j]:
                    enabled[j]=False
                    removed[j]=True
print(res)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<functional>
#include<numeric>
#include<random>
 
using namespace std;

// 蟻本pp.43f 区間スケジューリング問題

int main() { 
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	pair<int, int> ab[100000];
	for (int i = 0; i < m; i++) {
		cin >> ab[i].second >> ab[i].first;
	}
	sort(ab, ab + m);
	int ans = 0, x = 0;
	for (int i = 0; i < m; i++) {
		if (x <= ab[i].second) {
			ans++;
			x = ab[i].first;
		}
	}
	cout << ans << endl;
	return 0;
}

Submission status: Runtime Error

Solution code:
n,m=map(int, input().split())
a=[list(map(int, input().split())) for i in range(m)]
a.sort()
end=n
ans=0
for i in range(m):
    if a[i][0]>=end:
        ans+=1
        end=n
    end=min(a[i][1],end)
    count+=1
    #print(end,ans)
print(ans+1)

Submission status: Runtime Error

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

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

    if ai <= bridge:
        continue

    else:
        bridge = bi - 1
        cnt += 1

print(cnt)

Submission status: Runtime Error

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

c - []
for i in range(a[1]):
  c.append(list(map(int,input().split())))

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

s = c[0][0]
l = c[0][1]
re = 1

for i in range(1,a[1]):
  if l >= c[i][0]:
    re += 1
    l = c[i][1]
    
print(re)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import copy
tmp = input()
n = int(tmp.split(" ")[0])
m = int(tmp.split(" ")[1])

a=[]
b=[]
c=[]

for i in range(m):
    tmp=input()
    a.append(int(tmp.split(" ")[0])-1)
    b.append(int(tmp.split(" ")[1])-1)
    c.append(int(0))

d=copy.deepcopy(c)

x=int(0)
y=int(0)
z=int(0)
w=[]

for k in range(n-2):
    y=0
    c=copy.deepcopy(d)
    for j in range(k,n-1):
        x=0
        for i in range(m):
            if c[i]==0:
                if b[i]<=j:
                    z=1
                    break
                if a[i]<=j:
                    c[i]=1
                    x=1
        if z==1:
            break
        y=y+x
    if z==1:
        break
    elif y!=0:
        w.append(y)

print(min(w))

Submission status: Runtime Error

Solution code:
import numpy as np
n,m = map(int,input().split())
a = np.zeros(m)
b = np.zeros(m)
for i in range(m):
    a[i] , b[i] = map(int ,input().split())

a -= 1
b -= 1 
cnt = 0

while(a.shape):
    min_b = np.min(b)
    in_task = (a < min_b).astype(np.bool)
    cnt += 1
    tmp = np.logical_not(in_task)
    a = a[tmp]
    b = b[tmp]
    
print(cnt)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

N, M = map(int, input().split())
a = []
b = []

for j in range(M):
    ta, tb = map(int, input().split())
    a.append(ta)
    b.append(tb)

# print(a)
# print(b)

br_tbl = np.zeros((N-1, M), dtype=np.bool)
for j in range(M):
    for i in range(a[j]-1,b[j]-1):
        br_tbl[i,j] = 1

max_list = []
skip_list = np.zeros((M), dtype=np.bool)
br_cnt = 0
for j in range(M):
    # print('j=',j)
    max_col = 0
    if skip_list[j] == 1:
        continue
    sum_list = np.zeros((N-1), dtype=np.uint)
    for i in range(N-1):
        if  br_tbl[i,j] == 1:
            # print('i=',i)
            sum = 0
            for j2 in range(j,M):
                # print('j2=',j2)
                sum += br_tbl[i,j2]
            sum_list[i] = sum
            # print(sum)
    max_col = np.argmax(sum_list)
    max_list.append(max_col)
    # print('sum_list=',sum_list)
    # print('max_col=',max_col)
    br_cnt += 1

    for j3 in range(j,M):
        # print('j3=',j3)
        if br_tbl[max_col,j3] == 1:
            skip_list[j3] = 1
#     print(skip_list)
#
# print()
# print(br_tbl)

print(br_cnt)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import numpy as np
import pandas as pd
N, M = map(int, input().split())
a = []
b = []
for i in range(M):
  a_, b_ = map(int, input().split())
  a.append(a_ - 1)
  b.append(b_ - 1)

df = pd.DataFrame()
for i in range(N-1):
  NN = 2**(N-2)
  Nr = 2**(N-2-i)
  Nt = int(NN / Nr)
  v = np.array([1, 0])
  v = v.repeat(Nr)
  v = np.tile(v, Nt)
  df['b' + str(i)] = v
df['s'] = np.sum(df.values, axis=1)
df = df[df.s > 0]
df = df.sort_values(by=['s'])

for index, row in df.iterrows():
  all_sat = True
  for i in range(M):
    sat = False
    for j in range(a[i], b[i]):
      if row['b' + str(j)] == 1:
        sat = True
        break
    if not sat:
      all_sat = False
      break
  if all_sat:
    print(row['s'])
    exit()

Submission status: Runtime Error

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

demands= []

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

demans.sort()

cut = []

for d in demands:
    flag = True
    for c in cut:
        if c[0] < d[1] and c[1] > d[0]:
            flag = False
            c[0] = max(c[0],d[0])
            c[1] = min(c[1],d[1])
            break
    if flag:
        cut.append(d)

print(len(cut))

Submission status: Runtime Error

Solution code:
import bisect

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

l = [[int(x) for x in input().split()] for _ in range(M)]



def do(l):
    l1 = [v1 for (v1,_) in l]
    l2 = [v2 for (_,v2) in l]
    l1.sort()
    l2.sort()

    count = 1

    l.sort()

    h = 0
    
    for i in range(len(l)):
        nx = l2[h]
        if l[i][0] >= nx:
            count+=1
            h+=1
            while l2[h] != l2[h+1]:
                if h+1 >= len(l2):
                    break
                h+=1
    return count




result = do(l)
print(result)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import copy
tmp = input()
n = int(tmp.split(" ")[0])
m = int(tmp.split(" ")[1])

a=[]
b=[]
c=[]

for i in range(m):
    tmp=input()
    a.append(int(tmp.split(" ")[0])-1)
    b.append(int(tmp.split(" ")[1])-1)
    c.append(int(0))

d=copy.deepcopy(c)

x=int(0)
y=int(0)
z=int(0)
w=[]

for k in range(n-2):
    y=0
    c=copy.deepcopy(d)
    for j in range(k,n-1):
        x=0
        for i in range(m):
            if c[i]==0:
                if b[i]<=j:
                    z=1
                    break
                if a[i]<=j:
                    c[i]=1
                    x=1
        if z==1:
            break
        y=y+x
    if z==1:
        break
    if y!=0:
        w.append(y)

print(min(w))

Submission status: Runtime Error

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

compressed = []
while demands:
    a, b = demands.pop()

    for i, (ai, bi) in enumerate(compressed):
        if b <= ai or bi <= a:
            continue

        else:
            compressed[i] = [max(a, ai), min(b, bi)]
            break

    else:
        compressed.append([a, b])

print(len(compressed))

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
I = [N + 1 for i in range(N)]
for i in range(M):
  a, b = map(int, input().split())
  I[a - 1] = min(I[a - 1], b - 1)
cut = 0
for i in range(N):
  if I[i] == i + 1:
    cut += 1
  else:
    I[i + 1] = min(I[i + 1], I[i])
print(cut)

Submission status: Runtime Error

Solution code:
def drop(islinds,problems):
    a=set()
    i=0
    while len(a)<len(problems):
        a.add(islinds[i])
        i+=1
    new_islinds=islinds[:i]
    solved_problems=set(islinds[i:])
    if 0 in solved_problems:
        solved_problems.remove(0)
    new_problems=problems.difference(solved_problems)
    return new_islinds,new_problems

N, M=map(int,input().split(' '))
islinds=[0]*N
for i in range(1,M+1):
    a,b=map(int,input().split(' '))
    islinds[a-1]=i
    islinds[b-1]=i
problems=set(range(1,M+1))
count=0
while len(problems)>0:
    islinds,problems=drop(islinds,problems)
    count+=1
print(count)

Submission status: Runtime Error

Solution code:
# coding:utf-8

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

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

#　print(v)

num = 0

while(True):
    # 　aとbから最も離れた中央の橋で割るのが一番利得が大きい
    cent = int((v[0][0] + v[0][1]) / 2)
    num += 1
    pop_list = []

    for i in range(len(v)):
        ai = v[i][0]
        bi = v[i][1]
        if ai <= cent and bi > cent:
            pop_list.append(i)

    for p in pop_list:
        v.pop(p)

    if len(v) == 0:
        break

print(num)

Submission status: Runtime Error

Solution code:
def run(n, m, ab):
    ab = sorted(ab)
    cnt = 1
    b = ab[0][1]
    for i in range(1, m):
        a = ab[i][0]
        if b < a:
            cnt += 1
        b = ab[i][1]
    return cnt


def read_line():
    n, m = list(map(int, input().split()))
    ab = []
    for i in len(m):
        a, b = list(map(int, input().split()))
        ab.append([a, b])
    return (n, m, ab)


def main():
    n, m, ab = read_line()
    print(run(n, m, ab))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

arr = [[] for i in range(n)]

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

cnt = 0	
sting = 0
for i,isl in enumerate(arr):
	sting = isl[0]
	for j in arr[i:sting]:
		if (i == sting):
			cnt += 1
print(cnt)