TnT/Multi_CodeNet4Repair huggingface dataset:
Problem: 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.

Submission attempts (in order):
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)

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)

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):

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

ans = 0
endplace = 0
for ai, bi in ab:
    if endplace <= ai:
        endplace = bi
        ans += 1
print(ans)



n, m = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(m)]
ab.sort(key=lambda x:x[1])
ans = 0
endplace = 0
for ai, bi in ab:
    if endplace <= ai:
        endplace = bi
        ans += 1
print(ans)


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
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)

import sys

N, M = map(int, input().split())
ab = [list(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)

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
N,M = map(int,input().split())
problems =[]

for i in range(0,M):
    a = list(map(int,input().split()))
    problems.append(a)

problems.sort(key=lambda x:x[1])
#print(problems)

x = problems[0][0]
ans = 1

for j in range(1,len(problems)):
    if problems[j][0] <= x:
        continue
    else:
        x = problems[j][0]
        ans += 1

print(ans)



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

for i in range(0,M):
    a = list(map(int,input().split()))
    problems.append(a)

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

x = problems[0][0]
ans = 1

for j in range(1,len(problems)):
    if problems[j][0] <= x:
        continue
    else:
        x = problems[j][0]
        ans += 1
        
print(ans)



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

for i in range(0,M):
    a = list(map(int,input().split()))
    problems.append(a)

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

x = 0
ans = 0

for j in range(0,len(problems)):
    if problems[j][0] <= x:
        continue
    else:
        x = problems[j][0]
        ans += 1

print(ans)



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

for i in range(0,M):
    a = list(map(int,input().split()))
    problems.append(a)

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

x = 0
ans = 0

for j in range(0,len(problems)):
    if problems[j][0] <= x:
        continue
    else:
        x = problems[j][1] - 1
        ans += 1

print(ans)



Verdicts: Wrong Answer

Wrong Answer

Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
n, m = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(m)]

x = m
l = 0
for a, b in reversed(AB):
  if b > x :
    continue
  else:
    x = a
    l += 1
    
print(l)

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

AB.sort(key=lambda x: x[0])
x = n
l = 0
for a, b in reversed(AB):
  if b > x :
    continue
  else:
    x = a
    l += 1
    
print(l)


Verdicts: Wrong Answer

Accepted
Problem: 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.

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

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)

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)
print(ans+1)

Verdicts: Wrong Answer

Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
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])]
    
    for i in range(1, n[0]+1):
        if i in bridge:
            bridge = []
            counter += 1
        for j in range(len(reqs)):
            if reqs[j][0] == i:
                bridge.append(reqs[j][1])
            else:
                reqs = reqs[j:]
                break
            print(reqs)
            print(bridge)
    
    print(counter)

main()

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.clear()
            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()

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
N, M = map(int, input().strip().split())
ablr = {}
ab = []
for _ in range(M):
  a, b = map(int, input().strip().split())
  ab.append((a, 'L'))
  ab.append((b, 'R'))
  if a in ablr:
    ablr[a].add('L')
  else:
    ablr[a] = set(['L'])
  if b in ablr:
    ablr[b].add('R')
  else:
    ablr[b] = set(['R'])

print(ablr)

prevlr = None
previ = None
c = 0
for abi, lr in sorted(ab, key=lambda x: x[0]):
  if previ is None:
    previ = abi
    prevlr = 'L'
  elif previ == abi:
    continue
  else:
    if len(ablr[abi]) == 2:
      if prevlr=='L':
        prevlr = 'L'
        previ = abi
        c += 1
      else:
        prevlr = 'L'
        previ = abi
    else:
      if list(ablr[abi])[0] == 'L':
        prevlr = 'L'
        previ = abi
      else:
        if prevlr == 'L':
          c += 1
        prevlr = 'R'
        previ = abi
print(c)

N, M = map(int, input().strip().split())
ab = []
for _ in range(M):
  ab.append(tuple(map(int, input().strip().split())))

c = 0
prevb = 0

for a, b in sorted(ab, key=lambda x: x[1]):
  if a >= prevb:
    c += 1
    prevb = b
print(c)

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
import numpy as np
N, M = map(int, input().split())

a = np.zeros((M,2))

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

a = a[np.argsort(a[:,1])[::-1]]

prev = 0

a_max = 0
index = M
del_list = []
for i tmp in enumerate(a):
	if tmp[1] == prev:
		if tmp[0] > a_max:
			del_list.append(index)
			index = i
			a_max = tmp[0]
		else:
			del_list.append(i)
	else:
		prev = tmp[1]
		if tmp[0] > a_max:
			del_list.append(index)
			index = i
			a_max = tmp[0]
		elif a_max >= tmp[1]:
			a_max = tmp[0]
		else:
			del_list.append(i)
del del_list[0]
a = np.delete(a, del_list, 0)

prev = 0
b_min = N+1
index = M
del_list = []
for i, tmp in enumerate(a):
	if tmp[0] == prev:
		if tmp[1] < b_min:
			del_list.append(index)
			index = i
			b_min = tmp[1]
		else:
			del_list.append(i)
	else:
		prev = tmp[0]
		if tmp[1] < b_min:
			del_list.append(index)
			index = i
			b_min = tmp[1]
		elif b_min <= tmp[0]:
			b_min = tmp[1]
		else:
			del_list.append(i)
del del_list[0]
a = np.delete(a, del_list, 0)


a = a[np.argsort(a[:,0])]

prev = 0
b_min = N+1
index = M
del_list = []
for i, tmp in enumerate(a):
	if tmp[0] == prev:
		if tmp[1] < b_min:
			del_list.append(index)
			index = i
			b_min = tmp[1]
		else:
			del_list.append(i)
	else:
		prev = tmp[0]
		if tmp[1] < b_min:
			del_list.append(index)
			index = i
			b_min = tmp[1]
		elif b_min <= tmp[0]:
			b_min = tmp[1]
		else:
			del_list.append(i)
del del_list[0]
a = np.delete(a, del_list, 0)



ans = 0
flg = True
for i in range(len(a[:,0])-1):
	if a[i,1] > a[i+1, 0]:
		ans += 1
		flg = False
	elif flg:
		ans += 1
		flg = True
	else:
		flg = True
if flg:
	ans += 1
print(ans)


import numpy as np
N, M = map(int, input().split())

a = np.zeros((M,2))

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

a = a[np.argsort(a[:,1])]

index = 0
ans = 0
for tmp in a:
	if tmp[0] <= index:
		continue
	else:
		ans += 1
		index = tmp[1] - 1

print(ans)

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
import numpy as np
N, M = map(int, input().split())
AB = np.zeros([M, 2])
for i in range(M):
    AB[i, 0], AB[i, 1] = map(int, input().split())

AB = AB[np.argsort(AB[:, 1])]

cut_br = [AB[0, 1]-1]
for i in range(1, M):
    flag = False
    if AB[i, 0] <= cut_br[-1]:
        if cut_br[-1] < AB[i, 1]:
            flag = True
    if flag:
        cut_br.append(AB[i, 1]-1)
    break
print(len(cut_br))


# -*- coding: utf-8 -*-
"""
Created on Thu Aug  9 04:30:54 2018

@author: Yuki
"""
import numpy as np
N, M = map(int, input().split())
AB = np.zeros([M, 2])
for i in range(M):
    AB[i, 0], AB[i, 1] = map(int, input().split())

AB = AB[np.argsort(AB[:, 1])]

cut_br = [AB[0, 1]-1]
for i in range(1, M):
    flag = False
    if AB[i, 0] <= cut_br[-1]:
        if cut_br[-1] < AB[i, 1]:
            flag = True
    if not(flag):
        cut_br.append(AB[i, 1]-1)

print(len(cut_br))


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
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)

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

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

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

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



Verdicts: Runtime Error

Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
n,m = map(int,input().split())
x=y=0
lst=sorted([list(map(int,input().split())) for i in range(m)],key=lambda x:x[1])
for a,b in lst:
  if b<x:
    y+=1
  else:x==a
print(y)
  

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

lst=sorted([list(map(int,input().split())) for i in range(m)],key=lambda x:x[1])

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

Verdicts: Wrong Answer

Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
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))


n, m = map(int, input().split())
l = []
for i in range(m):
    a, b = map(int, input().split())
    l.append((b, a))
l.sort()
answer = 0
last = 0
for b, a in l:
    if a >= last:
        answer += 1
        last = b
print(answer)


Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
import numpy as np

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

a = np.zeros(M, dtype='int')
b = np.zeros(M, dtype='int')
for i in range(M):
    a[i], b[i] = map(int, input().split())

def fun_num_cut_interval(x, a, b):
    return sum( (x >= a[i]) and (x < b[i]) for i in range(len(a)) )

num_cut = 0
while True:
    ind = np.argmin(b - a)
    cut_bridge = a[ind]
    num_cut_interval = fun_num_cut_interval(cut_bridge, a, b)
    for bridge in range(a[ind]+1, b[ind]):
        tmp_num_cut_interval = fun_num_cut_interval(bridge, a, b)
        if tmp_num_cut_interval > num_cut_interval:
            cut_bridge = bridge
            num_cut_interval = tmp_num_cut_interval
            
    num_cut += 1
            
    delete_ind = [i for i in range(len(a)) if ( (cut_bridge >= a[i]) and ( cut_bridge < b[i]) )  ]
    a = np.delete(a, delete_ind)
    b = np.delete(b, delete_ind)
    
    print(cut_bridge, a, delete_ind)
    if len(a) == 0:
        break
        
print(num_cut)

import numpy as np

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

a = np.zeros(M, dtype='int')
b = np.zeros(M, dtype='int')
for i in range(M):
    a[i], b[i] = map(int, input().split())

ind = np.argsort(b)
a = a[ind]
b = b[ind]

num_broken_bridge = 0
last_bridge_position = - float("inf")
for i in range(len(a)):
    if a[i] > last_bridge_position:
        last_bridge_position = b[i] - 1
        num_broken_bridge += 1
    
print(num_broken_bridge)

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
n,m=map(int,input().split())
s=[]
for i in range(m):
    a,b=map(int,input().split())
    s.append([a,b-1])
s.sort(key=lambda x:x[1])
ans=0
t=None
for i,j in s:
    if(t is None or t<i):
        t=i
        ans+=1

print(ans)

n,m=map(int,input().split())
s=[]
for i in range(m):
    a,b=map(int,input().split())
    s.append([a,b-1])
s.sort(key=lambda x:x[1])
ans=0
t=None
for i,j in s:
    if(t is None or t<i):
        t=j
        ans+=1

print(ans)

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
from operator import itemgetter

def overlapped(a, b, p, q):
    #return p <=b and a <= q
    return p <b and a < q


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

a, b = AB[0]
for i in range(1, M):
    p, q = AB[i]
    if overlapped(a, b, p, q):
        pass
    else:
        ans += 1
        a, b = p, q
ans += 1

print(ans)

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


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

Verdicts: Wrong Answer

Accepted
Problem: 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.

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


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


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
import bisect
N,M = map(int,input().split())
l = [0]*M
for i in range(M):
     l[i] = list(map(int,input().split()))
l.sort()
ans = 0
i = 0
while i < M-1:
    min = max(l[i:],key=lambda x:-x[1])[0]
    i += bisect.bisect(l[i:],[min,N])
    ans += 1
ans += 1
print(ans)

import bisect
N,M = map(int,input().split())
l = [0]*M
for i in range(M):
     l[i] = list(map(int,input().split()))
l.sort()
a = [0]*M
b = [0]*M
for i in range(M):
    a[i] = l[i][0]
    b[i] = -l[i][1]
ans = 0
while len(a)>0:
    min = -max(b)
    i = bisect.bisect(a,min-1)
    a = a[i:]
    b = b[i:]
    ans += 1
print(ans)


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
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)





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

request_list = []

for i in range(M):
    request_list.append(list(map(int,input().split())))
    
request_list.sort(key=lambda x: x[1])

ans = 0
f = False

while True:
    ans += 1
    end_point = request_list[0][1]
    for i in range(len(request_list)):
        if request_list[0][0] < end_point:
            del request_list[0]
            if len(request_list) == 0:
                f = True
                break
        else:
            break
            
            
    
    if f:
        break
    
print(ans)



Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
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)

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)

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)

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,M):
    if s[i][0]>=mae:
        count+=1
        mae=s[i][1]

print(count)

Verdicts: Runtime Error

Runtime Error

Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
# -*- 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)


# -*- coding: utf-8 -*-
from collections import deque
N, M = map(int, input().split())
abn = [list(map(int, input().split())) for _ in range(M)]

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

ans = 0
bnum = -1
for a,b in abn:
    if bnum == -1:
        bnum = b - 1
        ans += 1
    elif a <= bnum < b:
        continue
    else:
        bnum = b - 1
        ans += 1

print(ans)

Verdicts: Runtime Error

Accepted
Problem: 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.

Submission attempts (in order):
n, m = map(int, input().split())
ab = []
for i in range(m):
    ab.append(list(map(int, input().split())))
ab.sort(reverse = True)
print(ab)
bridge = [float("inf")]
for i in range(m):
    if ab[i][0] <= min(bridge) < ab[i][1]:
        continue
    else:
        bridge.append(ab[i][0])
print(len(bridge) - 1)

n, m = map(int, input().split())
ab = []
for i in range(m):
    ab.append(list(map(int, input().split())))
ab.sort(reverse = True)

bridge = [float("inf")]
for i in range(m):
    if ab[i][0] <= min(bridge) < ab[i][1]:
        continue
    else:
        bridge.append(ab[i][0])
print(len(bridge) - 1)

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab.sort(key=lambda x: x[1])
print(ab)
c = 0
d = 0
for t in ab:
  if d < t[0]:
    c += 1
    d = t[1]-1
print(c)

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
d = 0
for t in ab:
  if d < t[0]:
    c += 1
    d = t[1]-1
print(c)

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
from operator import itemgetter

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


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

print(ab)
removed = -1
ans = 0

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

print(ans)

from operator import itemgetter

n, m = map(int, input().split())
ab = sorted([list(map(int, input().split())) for i in range(m)], key=itemgetter(1))
removed = -1
ans = 0

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

print(ans)

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy
from collections import defaultdict

def main():
  n, m = map(int, input().split())
  db2a = defaultdict(list)
  for _ in range(m):
    a, b = map(int, input().split())
    db2a[b-1].append(a-1)
    
  cnts = numpy.zeros(n, dtype=numpy.int)
  i = 0
  for b in sorted(db2a.keys()):
    cnts[i:b] = cnts[i-1]
    cnts[b] = cnts[max(db2a[b])] + 1
    i = b + 1
  cnts[i:] = cnts[i-1]
  print(cnts[-1])

if __name__=='__main__':
  main()



#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy
from collections import defaultdict

def main():
  n, m = map(int, input().split())
  db2a = defaultdict(list)
  for _ in range(m):
    a, b = map(int, input().split())
    db2a[b-1].append(a-1)
    
  cnt = 0
  end = 0
  for b in sorted(db2a.keys()):
    if end <= max(db2a[b]):
      cnt += 1
      end = b
  print(cnt)

if __name__=='__main__':
  main()



Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
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)


N, *A = map(int, open(0).read().split())
*A, = zip(*[iter(A)]*2)
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)


N,M,*A=map(int,open(0).read().split());c=0
for a,b in sorted(zip(*[iter(A)]*2))[::-1]:
	if b<=N:c+=1;N=a
print(c)

Verdicts: Runtime Error

Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
n,m=map(int,input().split())
l=[]
for i in range(m):
    l.append(list(map(int,input().split())))
l.sort()
s=l[0][1]
ans=0
for i in range(1,m):
    if l[i][0]>=s:
        ans+=1
        s=l[i][1]
print(ans)

n,m=map(int,input().split())
l=[]
for i in range(m):
    l.append(list(map(int,input().split())))
l.sort()
s=l[0][1]
ans=1
for i in range(1,m):
    if l[i][0]>=s:
        ans+=1
        s=l[i][1]
    if l[i][1]<=s:
        s=l[i][1]
print(ans)


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
n, m = map(int, input().split())
L = list()
for i in range(m):
    x, y = map(int, input().split())
    if x > y:
        x, y = y, x
    L.append([x, y])
L = sorted(L, key=lambda x: x[1])
print(L)
A = L[0]
i = 1
for v in L:
    if v[0] >= A[1]:
        A = v
        i += 1
print(i)


n, m = map(int, input().split())
L = list()
for i in range(m):
    x, y = map(int, input().split())
    if x > y:
        x, y = y, x
    L.append([x, y])
L = sorted(L, key=lambda x: x[1])
A = L[0]
i = 1
for v in L:
    if v[0] >= A[1]:
        A = v
        i += 1
print(i)

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):


n, m = map(int, input().strip().split())
a_list = []
b_list = []
for _ in range(m):
    tmp_a, tmp_b = map(int, input().strip().split())
    a_list.append(tmp_a)
    b_list.append(tmp_b)

l_list = []
r_list = []
for a, b in zip(a_list, b_list):
    should_add_a_b = True
    for l, r, i in zip(l_list, r_list, range(len(l_list))):
        if b <= l or r <= a:
            continue
        if l < a:
            l_list[i] = a
        if b < r:
            r_list[i] = b
        should_add_a_b = False
        break
    if should_add_a_b:
        l_list.append(a)
        r_list.append(b)
print(l_list)
print(r_list)
print(len(l_list))


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

res = 0
min_r = 0
for ab in ab_list:
    if min_r <= ab[0]:
        res += 1
        min_r = ab[1]
print(res)


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
import sys

n, m, *ab = map(int, sys.stdin.read().split())
ab = sorted(zip(*[iter(ab)] * 2))

def main():
    r = -1
    cnt = 0
    for a, b in ab:
        if a < r:
            if b < r:
                r = b
            continue
        else:
            print(a, b)
            cnt += 1
            r = b
    return cnt

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

import sys

n, m, *ab = map(int, sys.stdin.read().split())
ab = sorted(zip(*[iter(ab)] * 2))

def main():
    r = ab[0][1]
    cnt = 0
    for a, b in ab[1:]:
        if a < r:
            if b < r:
                r = b
            continue
        else:
            cnt += 1
            r = b
    cnt += 1
    return cnt

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

Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
import sys

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

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

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

print(ans)


import sys

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

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

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

print(ans)


Verdicts: Wrong Answer

Accepted
Problem: 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.

Submission attempts (in order):
NM = list(map(int, input().split()))
b = []
for i in range(NM[1]):
	ab = list(map(int, input().split()))
	flag = 1
	for i in range(len(b)):
		if (b[i][1] < ab[0] and b[i][0] < ab[0] ):
			b[i][0] = ab[0]
			flag = 0
			break
		if(b[i][0] > ab[1] and b[i][1] > ab[1]):
			b[i][1] = ab[1] 
			flag = 0
			break
		if (flag):
			b.append(ab)
			flag = 1

print(len(b))

NM = list(map(int, input().split()))
b = []
for i in range(NM[1]):
	ab = list(map(int, input().split()))
	flag = 1
	for i in range(b):
		if (b[i][1] < ab[0] and b[i][0] < ab[0] ):
			b[i][0] = ab[0]
			flag = 0
			break
		if(b[i][0] > ab[1] and b[i][1] > ab[1]):
			b[i][1] = ab[1] 
			flag = 0
			break
		if (flag):
			b.append(ab)
			flag = 1

print(len(b))

NM = list(map(int, input().split()))
#NM = [5,2]
#A = [[1,4], [2,5]]
b = list(map(int, input().split()))
#b = [[1,4]]
for i in range(NM[1]-1):
	ab = list(map(int, input().split()))

	flag = 1
	for i in range(len(b)):
		if (b[i][1] >= ab[0] and b[i][0] <= ab[0] ):
			b[i][0] = ab[0]
			flag = 0
			break
		if(b[i][0] <= ab[1] and b[i][1] >= ab[1]):
			b[i][1] = ab[1] 
			flag = 0
			break
		if (flag):
			b.append(ab)
			flag = 1

#print(b)
print(len(b))

NM = list(map(int, input().split()))
#NM = [5,2]
#A = [[1,4], [2,5]]
b = list(map(int, input().split()))
#b = [[1,4]]
for i in range(NM[1]-1):
	ab = list(map(int, input().split()))

	flag = 1
	for i in range(len(b)):
		if (b[i][1] >= ab[0] and b[i][0] <= ab[0] ):
			b[i][0] = ab[0]
			flag = 0
			break
		if(b[i][0] <= ab[1] and b[i][1] >= ab[1]):
			b[i][1] = ab[1] 
			print("he")
			flag = 0
			break
		if (flag):
			print("here")
			b.append(ab)
			flag = 1

#print(b)
print(len(b))

N, M = map(int, input().split())
claim = []
for i in range(M):
	claim.append(list(map(int, input().split())))
claim.sort(key=lambda a:a[1])

ans = 0
inter = [-1,-1]
for land in claim:
    if inter[1] <= land[0]:
        inter = land
        ans += 1
print(ans)

Verdicts: Wrong Answer

Runtime Error

Runtime Error

Runtime Error

Accepted