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

n , m = map(int, input().split())
# ab = [list(map(int, input().split())) for _ in range(m)]
ranges = [[] for _ in range(m)]
for i in range(m):
    a,b = map(int,input().split())
    ranges[i] = [a,b]
ranges = sorted(ranges, key = lambda x:x[1])
MAX = - float("inf")
ans = 0
for i in range(m):
    if MAX < ranges[i][0]:
        MAX = ranges[i][0]
        ans += 1
print(ans)

n , m = map(int, input().split())
# ab = [list(map(int, input().split())) for _ in range(m)]
ranges = [[] for _ in range(m)]
for i in range(m):
    a,b = map(int,input().split())
    ranges[i] = [a,b]
ranges = sorted(ranges, key = lambda x:x[1])
MAX = - float("inf")
ans = 0
for i in range(m):
    if MAX <= ranges[i][0]:
        MAX = ranges[i][1]
        ans += 1
print(ans)

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

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())
	if A[A1] > A2 or A[A1] == 0:
		A[A1] = A2
	
ans = 0
min_dir = sys.maxsize
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.maxsize
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())
A=[]
a=0
b=0
for i in range(m):
  a,b=map(int, input().split())
  A.append([a,b])
  

def kyotu(J,K):
  aa,bb=max(J[0],K[0]),min(J[1],K[1])
  if aa>=bb:
    return 0
  else:
    return [aa,bb]


kyo=[]
kk=[]
def kyotu2(k):
  for i in range(len(kyo)-1,0-1,-1):
    kk=kyotu(kyo[i],A[k])
    
    if kk!=0:
      kyo[i][0]=kk[0]
      kyo[i][1]=kk[1]
      return 0
    
  kyo.append([A[k][0],A[k][1]])



for i in range(m):
  kyotu2(i)
print(kyo)
print(len(kyo))



from operator import itemgetter
 
n,m=map(int, input().split())
A=[]
B=[]
a=0
b=0
for i in range(m):
  a,b=map(int, input().split())
  A.append([a,b])

A.sort(key=itemgetter(1))
bri=0 

count=0

for i in range(m):
  a=A[i][0]
  b=A[i][1]
  
  if a>=bri:
    bri=b
    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):
N,M = list(map(int,input().split(' ')))

abp = []

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

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

dbridge = []

def check(a,b,dbridge):
	for i in range(a,b):
		if i in dbridge:
			return False
	return True

print(abp)

for a,b in abp:
	if check(a,b,dbridge):
		dbridge.append(b-1)
	else:
		pass

print(len(dbridge))

N,M = list(map(int,input().split(' ')))
 
abp = []
 
for i in range(M):
	a,b = list(map(int,input().split(' ')))
	abp.append([a,b])
 
abp.sort(key=lambda x:x[1])
 
ep = 0
ans = 0 
for a,b in abp:
	if a >= ep:
		ep = b
		ans = 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):
N,M = map(int,input().split())
Alist = []
for i in range(M):
    array = list(map(int, input().strip().split()))
    Alist.append(array)
Alist.sort()
q = 0
p = [Alist[0][0],Alist[0][1]]
for i in range(len(Alist)-1):
    print(p)
    if Alist[i][0] < Alist[i+1][0]:
        p[0] = Alist[i+1][0]
    if p[0] >= p[1]:
        print(q)
        q = q+1
        p = [Alist[i+1][0],Alist[i+1][1]]
    if Alist[i][1] > Alist[i+1][1]:
        p[1] = Alist[i+1][1]
print(q+1)

N,M = map(int,input().split())
Alist = []
for i in range(M):
    array = list(map(int, input().strip().split()))
    Alist.append(array)
Alist.sort()
q = 0
p = [Alist[0][0],Alist[0][1]]
for i in range(len(Alist)-1):
    if p[0] < Alist[i+1][0]:
        p[0] = Alist[i+1][0]
    if p[0] >= p[1]:
        q = q+1
        p = [Alist[i+1][0],Alist[i+1][1]]
    if p[1] > Alist[i+1][1]:
        p[1] = Alist[i+1][1]
print(q+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 = [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])


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


class SegmentTree:
    def __init__(self, size, op, e):
        self._op = op
        self._e = e
        self._size = size
        t = 1
        while t < size:
            t *= 2
        self._offset = t - 1
        self._data = [e] * (t * 2 - 1)

    def __getitem__(self, key):
        return self._data[self._offset + key]

    def __setitem__(self, key, value):
        op = self._op
        data = self._data
        i = self._offset + key
        data[i] = value
        while i >= 1:
            i = (i - 1) // 2
            data[i] = op(data[i * 2 + 1], data[i * 2 + 2])

    def build(self, iterable):
        op = self._op
        data = self._data
        data[self._offset:self._offset + self._size] = iterable
        for i in range(self._offset - 1, -1, -1):
            data[i] = op(data[i * 2 + 1], data[i * 2 + 2])

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

readline = stdin.readline

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

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

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


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

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


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

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

print(len(s))

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):
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(m)]
ab.sort(reverse=True)
L=10**6
ans=0
for a,b in ab[::-1]:
    if not a<=L<b:
        ans+=1
        L=a
print(ans)

n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(m)]
ab.sort()
L=10**6
ans=0
for a,b in ab[::-1]:
    if not a<=L<b:
        ans+=1
        L=a
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())
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)


import sys
from operator import itemgetter
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
 
def main():
    N, M = map(int, readline().split())
    ab = map(int, read().split())
    ab = sorted(zip(ab, ab), key=itemgetter(1))
 
    east_island = ab[0][1]
    answer = 1
 
    for i, j in ab:
        if i >= east_island:
            answer += 1
            east_island = j
 
    print(answer)
 
 
if __name__ == '__main__':
    main()

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):
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

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

ans = 1
ind = 0

print(cut)

s = cut[ind][0]
e = cut[ind][1]
while ind < M:
    n_s, n_e = cut[ind]
    if n_s < e:
        e = min(e, n_e)
    else:
        s = n_s
        e = n_e
        ans += 1
    ind += 1


print(ans)


# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

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

ans = 1
ind = 0


s = cut[ind][0]
e = cut[ind][1]
while ind < M:
    n_s, n_e = cut[ind]
    if n_s < e:
        e = min(e, n_e)
    else:
        s = n_s
        e = n_e
        ans += 1
    ind += 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):
# ABC103D


# ex) 1-10, 2-5, 6-8

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)
ans = 1             
tmp = ab[0][1] - 0.1      
for i in range(1, M):
    if ab[i][0] < tmp < ab[i][1]:   
        pass
    else:                           
        ans += 1
        tmp = ab[i][1] - 0.1

print(ans)

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
ab.sort(key=lambda x: x[1])
ans = 1
tmp = ab[0][1]
for i in range(1, M):
    if tmp <= ab[i][0]:
        ans += 1
        tmp = ab[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):
import bisect
import heapq
import itertools
import math
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

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

heap = []

ans = 0
for a, b in AB:
    if heap and a >= heap[0]:
        heap = []
        ans += 1
    heapq.heappush(heap, b)
if heap:
    ans += 1
print(ans)


import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353

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

AB.sort()

counts = np.zeros(N, dtype=int)
stack = []
ans = 0
p = 0
for a, b in AB:
    a -= 1
    b -= 1
    while True:
        if counts[p] > 0:
            while stack:
                r = stack.pop()
                counts[r] -= 1
            ans += 1
        if p >= a:
            break
        p += 1
    stack.append(b)
    counts[b] += 1
    # print(a, b, p, ans)
if stack:
    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):
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()

from operator import itemgetter
import sys
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()

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 = [int(i) for i in input().split()]
wars = [[int(i) for i in input().split()] for _ in range(M)]

wars.sort(key=lambda x:x[1],reverse=False)
r = set()

for war in wars:
    for i in set():
        if i <= war[1] and i >= war[0]:
            break
    else:
        r.add(war[1]-1)

print(len(r))

N,M = [int(i) for i in input().split()]
wars = [[int(i) for i in input().split()] for _ in range(M)]

wars.sort(key=lambda x:x[1],reverse=False)
r = set()
for war in wars:
    for i in r:
        if war[0] <= i and i <= war[1]:
            break
    else:
        r.add(war[1]-1)
    

print(len(r))

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

from operator import itemgetter
n,m=map(int,input().split())
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)

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

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].append(b - 1)
cut = 0
for i in range(N - 1):
  if min(I[i]) == i + 1:
    cut += 1
  else:
    I[i + 1].append(min(I[i]))
print(cut)

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

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

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 = set(range(1,N))
ans = 1
m = []
for i in range(M):
    a, b = map(int, input().split())
    m.append((a,b))
i = 0
while i < M:
    a, b = m[i]
    s = s & set(range(a,b))
    print(s)
    if len(s) == 0:
        ans += 1
        s = set(range(1,N))
        i -= 1
    i += 1
print(ans)


N, M = map(int, input().split())
m = []
for i in range(M):
    a, b = map(int, input().split())
    m.append((a,b-1))
ans = 0
t = None
for l,r in sorted(m, key=lambda x:x[1]):
    if t is None or l > t:
        t = r
        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):
N, M = list(map(int, input().split()))
D = []
L = [0] * N
for i in range(M):
  D.append(list(map(int, input().split())))
D.sort(key = lambda x: x[1])

Ans = 0
Re = 0
for i in D:
  if Re < i[0]:
    Re = i[0]
    Ans += 1
print(Ans)

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

Ans = 0
Re = 0
for i in D:
  if Re < i[0]:
    Re = i[1]-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):
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)

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)

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())
mx =[0 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)

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

n,m=map(int,input().split())
mx =[0 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=0
cn=0
for z in range(0,n):
  if cut<mx[z]:
   	cut=z
    cn=cn+1
print(cn)

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)

Verdicts: Wrong Answer

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):
N, M = [int(str) for str in input().strip().split()]
AB = [[int(str) for str in input().strip().split()] for _ in range(M)]

A_B = [[] for i in range(N)]
for ab in AB:
    A_B[ab[0]].append(ab[1])
for a_b in A_B:
    a_b.sort()

print(A_B)

i = 0
left = 10 ** 6
ans = 1
for i in range(N):
    if len(A_B[i]):
        if i > left:
            print(i, A_B[i])
            ans += 1
        left = min(left, A_B[i][0] - 1)
        i += 1

print(ans)

#!/usr/bin/env python3
N, M = [int(str) for str in input().strip().split()]
ab = [[int(str) for str in input().strip().split()] for _ in range(M)]


def solve():
    ab.sort(key=lambda x: x[1])
    ans = 0
    broken = 0
    for a, b in ab:
        if a < broken:
            continue
        broken = b
        ans += 1
    print(ans)

solve()


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

data = []
data2=[]
for i in range(M):
    data.append(list(map(int, input().split())))
    data2.append(list(range(10*data[i][0]+5,10*data[i][1]+1-5,5)))
print(data2)
ans=set(data2[0])
ct=1
for i in range(1,M):
    if len(ans.intersection(set(data2[i])))>0:
        ans = ans.intersection(set(data2[i]))
        print(ans)
    else:
        ct+=1
        ans=set(data2[i])
print(ct)

# A=list(AB[0])
# B=list(AB[1])
#
# print(A)



N,M=map(int, input().split())
AB=list(sorted([list(map(int, input().split())) for _ in range(M)], key=lambda x :x[1]))
ans=1
A=[AB[0]]
for i in range(1,M):
    if AB[i][0]>=A[-1][1]:
        ans+=1
        A.append(AB[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):
import sys




#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

#import numpy as np

def main():
	n,m=MI()
	li=[LI() for _ in range(m)]

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

	now=0
	ans=0

	for a,b in li:
		if now<=a:
			now=b
			ans+=1
	print(ans)

























if __name__ == "__main__":
	main()


import sys
input = sys.stdin.buffer.readline



#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

#import numpy as np

def main():
	n,m=MI()
	li=[LI() for _ in range(m)]

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

	now=0
	ans=0

	for a,b in li:
		if now<=a:
			now=b
			ans+=1
	print(ans)

























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


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(M):
    if last <= ab[i][0]:
        ans += 1
        last = ab[i][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):
islands = []
bridges = []

N, M = map(int, input().split())
# N, M = 10, 5
# islands = [
#     {'a': 1, 'b': 10},
#     {'a': 2, 'b': 5},
#     {'a': 1, 'b': 9},
#     {'a': 2, 'b': 4},
#     {'a': 1, 'b': 2},
# ]

for i in range(M):
    a, b = map(int, input().split())
    islands.append({'a': a, 'b': b})

islands.sort(key=lambda x: (x['a'], x['b']))
# print(islands)

for i in islands:
    b = [j for j in bridges if j >= i['a']]
    b = [j for j in b if j < i['b']]
    if len(b) == 0:
        bridges.append(i['b'] - 1)

print(bridges)


islands = []
bridges = []

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

for i in range(M):
    a, b = map(int, input().split())
    islands.append({'a': a, 'b': b})

islands.sort(key=lambda x: x['b'])
# print(islands)

for i in islands:
    b = [j for j in bridges if j >= i['a']]
    if len(b) == 0:
        bridges.append(i['b'] - 1)

# print(bridges)
print(len(bridges))


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 = (int(i) for i in input().split())
e = [[int(i) for i in input().split()] for i in range(m)]
g = 1
e.sort(key = itemgetter(1))
print(e)
for i in range(m):
    if i == 0:
        a = e[0][1] - 1
        print(a)
    else:
        if a >= e[i][0]:
            pass
        else:
            g += 1
            a = e[i][1] - 1
print(g)

from operator import itemgetter
n, m = (int(i) for i in input().split())
e = [[int(i) for i in input().split()] for i in range(m)]
g = 1
e.sort(key = itemgetter(1))
for i in range(m):
    if i == 0:
        a = e[0][1] - 1
    else:
        if a >= e[i][0]:
            pass
        else:
            g += 1
            a = e[i][1] - 1
print(g)

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(map(int, input().split())) for i in range(M)]
l = sorted(l, key = lambda l:(l[1]))

print(l)

p_num = -1
ans = 0

for i in range(M):
	if not l[i][0] <= p_num:
		p_num = l[i][1] - 1
		ans += 1

print(ans)

N, M = map(int, input().split())
l = [list(map(int, input().split())) for i in range(M)]
l = sorted(l, key = lambda l:(l[1]))

p_num = -1
ans = 0

for i in range(M):
	if not l[i][0] <= p_num:
		p_num = l[i][1] - 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):

N,M=map(int,input().split())
kyomu=[]
for i in range(M):
    a,b=map(int,input().split())
    kyomulen=len(kyomu)
    j=0
    flag=0
    for j in range(kyomulen):
        if a>=kyomu[j][0] and b<=kyomu[j][1]:
            del kyomu[j]
            kyomu.append([a,b])
            flag=1
            break
    if flag == 0:
        kyomu.append([a,b])
print(len(kyomu))


N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
AB=sorted(AB, key=lambda x: x[1])
bridges=[]
for i in range(M):
    if len(bridges) == 0:
        bridges.append(AB[i][1]-1)
    elif max(bridges)>=AB[i][0]:
        pass
    else:
        bridges.append(AB[i][1]-1)
print(len(bridges))

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 = []
for i in range(M):
    ab.append(list(map(int,input().split())))
ab.sort(key = lambda ab:ab[1])
count = 0
now = 0
print(ab)
for a,b in ab:
    if a >= now:
        count += 1
        now = b
print(count)

N,M = map(int,input().split())
ab = []
for i in range(M):
    ab.append(list(map(int,input().split())))
ab.sort(key = lambda ab:ab[1])
count = 0
now = 0
for a,b in ab:
    if a >= now:
        count += 1
        now = b
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):
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) 


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


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())
a = [0 for i in range(M)]
b = [0 for i in range(M)]
for i in range(M):
    A,B = map(int,input().split())
    a[i] = A
    b[i] = B

ans = 0
while 1:
    if len(a) == 0:
        break
    maxVal = max(a)
    if ans == 0:
        maxVal = maxVal // 2
    maxIdx = a.index(maxVal)

    for j in reversed(range(len(a))):
        if a[j] <= maxVal <= b[j] - 1:
            a.pop(j)
            b.pop(j)

    ans += 1

print(ans)

N,M = map(int,input().split())
listAB = [list(map(lambda x:int(x),input().split())) for i in range(M)]

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

last = -1
ans = 0
for a,b in listAB:
    
    if last <= a:
        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())
G=[list() for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
ans=0
index=-1
for i in range(1,N):
    for p in G[i]:
        if index<p<i:
            ans+=1
            index=i-1
print(ans)
if N==5 and M==2:
    print("ans")

N,M=map(int, input().split())
G=[list() for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
ans=0
index=-1
for i in range(1,N):
    for p in G[i]:
        if index<p<i:
            ans+=1
            index=i-1
            break
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
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)


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:
    count += 1
    bridge = b-1
print(count)


Verdicts: Runtime Error

Accepted