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):
import heapq
from sys import stdin
input = stdin.readline



# n = int(input())
n,m = map(int, input().split())
# a = list(map(int,input().split()))


ab=[]
for i in range(m):
    a,b = map(int, input().split())
    ab.append((a,b))
ab = sorted(ab, key = lambda x: x[1])

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


    
    

if __name__ == '__main__':
    main()

import heapq
from sys import stdin
input = stdin.readline



# n = int(input())
n,m = map(int, input().split())
# a = list(map(int,input().split()))


ab=[]
for i in range(m):
    a,b = map(int, input().split())
    ab.append((a,b))
ab = sorted(ab, key = lambda x: x[1])

     
def main():
    left = 0
    ans = 0
    for a,b in ab:

        if left < a:
            left = b-1
            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):
a_b = []
for _ in range(M):
    a, b = map(int, input().split())
    a_b.append((a, b))
a_b.sort(key=lambda x: x[0])

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

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

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

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):
# -*- coding: utf-8 -*-
import sys
n, m = map(int, input().split())
demands = (tuple(map(int,
                     line.strip().split())) for line in sys.stdin.readlines())
demands.sort(key=lambda demand: demand[1])

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

    if ai <= bridge:
        continue

    else:
        bridge = bi - 1
        cnt += 1

print(cnt)


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

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

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

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

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

print(len(compressed))


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

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

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

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

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

print(len(compressed))


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

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

    if ai <= x:
        continue

    else:
        x = bi - 1
        cnt += 1

print(cnt)

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

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

bridge = []
ans = 0
for i in range(m):
    count = True
    for j in range(a[m - i - 1][0],a[m - i - 1][1]):
        if j in bridge:
            count = False
            
    if count:
        ans += 1
        bridge.append(a[m - i - 1][1]-1)
print(ans)

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

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

bridge = n
ans = 0
for i in range(m):
    count = True
    if a[m - i - 1][1] > bridge:
        count = False
            
    if count:
        ans += 1
        bridge = a[m - i - 1][0]

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 solve(n, pairs):
    pairs.sort(key=lambda pair: pair[1])
    cnt = 0
    while pairs:
        _, b0 = pairs[0]
        cnt += 1
        for (a, b) in pairs:
            if a < b0:
                pairs.remove((a, b))
    return cnt

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


import sys

def solve():
    pairs.sort(key=lambda pair: pair[1])
    cnt = 0
    base = 0
    for (a, b) in pairs:
        if a >= base:
            cnt += 1
            base = b
    return cnt

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

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

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

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


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

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

ans = 0
ed = 0
for _ in lst:
    if _[0] < ed:
      pass
    else:
        ed = _[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 = list(map(int, input().split()))
ab = list(list(map(int, input().split())) for i in range(m))
ab = sorted(ab, key=lambda x: x[1])
bridge = 0
count = 0
for i in range(m):
    if ab[i][0] <= bridge:
        continue
    else:
        bridge = ab[i][0]
        count = count + 1
    if count == n-1:
        break
    else:
        continue
print(count)

n, m = list(map(int, input().split()))
ab = list(list(map(int, input().split())) for i in range(m))
ab = sorted(ab, key=lambda x: x[1])
bridge = 0
count = 0
for i in range(m):
    if ab[i][0] < bridge:
        continue
    else:
        bridge = ab[i][1]
        count = count + 1
    if count == n-1:
        break
    else:
        continue
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):
# Input
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,m = li()
ab = [(-1, -1)]
for _ in range(m):
    ai, bi = li_()
    ab.append((ai, bi))

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

ans = 0
cur = -1
for ai, bi in ab:
    if ai >= cur:
        ans += 1
        cur = bi

print(ans)




# Input
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,m = li()
ab = []
for _ in range(m):
    ai, bi = li_()
    ab.append((ai, bi))

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

ans = 0
cur = -1
for ai, bi in ab:
    if ai >= cur:
        ans += 1
        cur = bi

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 run(n, m, ab):
    ab = sorted(ab)
    cnt = 1
    b = ab[0][1]
    for i in range(1, m):
        a = ab[i][0]
        if b < a:
            cnt += 1
        b = ab[i][1]
    return cnt


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


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


if __name__ == '__main__':
    main()


def run(n, m, ab):
    ab = sorted(ab)
    cnt = 1
    b = ab[0][1]
    c = b
    for i in range(1, m):
        a = ab[i][0]
        b = ab[i][1]
        if a < c and c <= b:
            pass
        elif c <= a:
            cnt += 1
            c = b
        else:
            c = b
    return cnt


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


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


if __name__ == '__main__':
    main()


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):
from operator import itemgetter
n,m=map(int,input().split())
a=[]
b=[]
for i in range(m):
    a_,b_=map(int,input().split())
    a.append(a_)
    b.append(b_)
ab=sorted([(a[i],b[i]) for i in range(m)],  key=itemgetter(1))  

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

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

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

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

for i,j in ab:
    if i>removed:
        ans+=1
        removed=j-1
print(ans)

Verdicts: 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())
for i in range(M):
    a[i]=input().rstrip().split()



a = [[]*2]*M
sum = 0
hasi = [0]*(N-1)
for i in range(0,M):
    c1 = int(a[M-1-i][0])
    c2 = int(a[M-1-i][1])
    f = [False]
    for m in range(c1-1,c2-1):
        if hasi[m]==1:
            f[0]=True
    if f[0]==True:
        continue
    else:
        hasi[c1-1]=1
        sum = sum+1



print(sum)   


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

a = [[]*2]*M
for i in range(M):
    a[i]=input().rstrip().split()




sum = 0
hasi = [0]*(N-1)
for i in range(0,M):
    c1 = int(a[M-1-i][0])
    c2 = int(a[M-1-i][1])
    f = [False]
    for m in range(c1-1,c2-1):
        if hasi[m]==1:
            f[0]=True
    if f[0]==True:
        continue
    else:
        hasi[c1-1]=1
        sum = sum+1


    
sum    


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


ab.sort(key=lambda x: x[1])
ans = 1
pre = ab[0][1]
for ele in ab[1:]:
    if pre > ele[0]:
        continue
    pre = ele[1]
    ans += 1
print(ans)






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

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

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

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

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

import sys
input = sys.stdin.readline

N, M = (int(i) for i in input().split())
dic = {}
cnt = 0
pos = 0
for i in range(M):
    a, b = map(int, input().split())
    if b not in dic or dic[b] < a:
        dic[b] = a

for j in sorted(dic.keys()):
    if dic[j] >= pos:
        cnt += 1
        pos = j
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):
def main():
    in1 = input()
    n, m = [int(c) for c in in1]

    arr = []
    for i in range(m):
        _in = input()
        a, b = [int(c) for c in _in]
        arr.append((a, b))

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

    n = 0

    mi, ma = sorted_arr[0]
    for a, b in sorted_arr[1:]:
        if ma < a:
            n += 1
            mi, ma = a, b
        if mi < a:
            mi = a
        if ma > b:
            ma = b
    print(n)

if __name__ == "__main__":
    main()


def main():
    in1 = input().split(" ")
    n, m = [int(c) for c in in1]

    arr = []
    for i in range(m):
        _in = input().split(" ")
        a, b = [int(c) for c in _in]
        arr.append((a, b))

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

    n = 1

    mi, ma = sorted_arr[0]
    mi, ma = (mi, ma) if mi < ma else (ma, mi)
    for a, b in sorted_arr[1:]:
        a, b = (a, b) if a < b else (b, a)
        if ma <= a:
            n += 1
            mi, ma = a, b
        if mi < a:
            mi = a
        if ma > b:
            ma = b
    print(n)

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=map(int,input().split())
l=[list(map(int,input().split())) for _ in range(m)]
l.sort(key=lambda x : x[1])
a=0
b=0
for x in l:
  if x[0]>b:
    b=x[0]
    a+=1
print(a)


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


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


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

ans=0
bridge = [0 for _ in range(2*N)]
dic = {}

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

tmp = 0
for x in bridge:
    if tmp == -1 and x == 1:
        ans+=1
        tmp=0
    tmp = min(tmp,x)
print(ans+1)


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

ans=0
st = [[] for _ in range(N+1)]
goal = [0 for _ in range(N+1)]

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

stack = []
for i in range(1,N+1):
    if goal[i]>0:
        ans+=1
        for x in stack:
            goal[x] -= 1
        stack=[]
    if len(st[i])>0:
        stack += st[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):
from typing import List
from preconditions import preconditions
import heapq


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





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

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



if __name__ == '__main__':
    main()

import heapq


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





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

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



if __name__ == '__main__':
    main()


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

ab.sort(key = lambda x:x[1])
ans = 0
last = -1
for a,b in ab:
    print(a,b)
    if last <= a:
        ans += 1
        last = b
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 = 0
last = -1
for a,b in ab:
    print(a,b)
    if last <= a:
        ans += 1
        last = b
        print('hogehogehoge',last,ans)
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 = 0
last = -1
for a,b in ab:
    if last <= a:
        ans += 1
        last = b
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):
n,m = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(m)]
ab.sort()
cnt=0
while(len(ab)>1 and cnt<10):
    cnt+=1
    mini =min(ab, key=lambda x:x[1])[1]
    for i in range(len(ab)):
        if ab[i][0]>mini: break
    for j in range(i):
        del ab[0]
    if(len(ab)==1):cnt+=1
print(cnt)


n,m = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(m)]
ab.sort(key=lambda x:x[1])
last=-1
cnt=0
for i in range(len(ab)):
    if(ab[i][0]<=last):pass
    else:
        last=ab[i][1]-1
        cnt+=1
print(cnt)

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):
#coding:utf-8
from bisect import bisect_right

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

start,left = map(int,input().split())
right = left
cnt = 0
for i in range(M-1):
    data = list(map(int,input().split()))
    if data[0] != start:
        start = data[0]
        if data[1] >= left:
            cnt += 1
            left = data[1]
            right = left
    else:
        right = data[1]
    
if data[1] >= right:
    cnt += 1

print(cnt)


#coding:utf-8

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

start,left = map(int,input().split())
right = left
cnt = 0
for i in range(M-1):
    data = list(map(int,input().split()))
    if data[0] != start:
        start = data[0]
        if data[1] >= left:
            cnt += 1
            left = data[1]
            right = left
    else:
        right = data[1]
    
if data[1] >= right:
    cnt += 1

print(cnt)


#coding:utf-8

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

cnt = 1
maxa = 0
b = List[0][1]
for i in range(1,M):
    newB = List[i][1]
    maxa = max(maxa,List[i][0])
    if newB > b:
        if maxa >= b:
            cnt += 1
            b = newB
        maxa = 0
        
print(cnt)


Verdicts: 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):
def main():
    n = [int(i) for i in input().split()]
    bridge = []
    counter = 0
    reqs = [[int(j) for j in input().split()] for i in range(n[1])]
    reqs.sort(key=lambda x:(x[0],x[1]))
    prefix = 0
    
    for i in range(1, n[0]+1):
        if i in bridge:
            bridge = []
            counter += 1
        for j in range(len(prefix, reqs)):
            if reqs[j][0] == i:
                bridge.append(reqs[j][1])
            else:
                prefix = j + 1
                break
    
    print(counter)
 
main()

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]))
    prefix = 0
    
    for i in range(1, n[0]+1):
        if i in bridge:
            bridge.clear()
            counter += 1
        for j in range(prefix, len(reqs)):
            if reqs[j][0] == i:
                bridge.add(reqs[j][1])
            else:
                prefix = j
                break
    
    print(counter)
 
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):
# encoding: utf-8
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(M)]

# find maximum a for each b
max_as = [0] * N
for a, b in ab:
    if max_as[b - 1] < b: max_as[b - 1] = a

# count num. of valid bridges (bm = b - 1)
ans = 0
max_max_a = 0
for bm, max_a in enumerate(max_as):
    if max_a < 1: continue
    elif max_a <= max_max_a: continue
    ans += 1
    max_max_a = max_a
        
# WA

# # check value exists in [a] and [b]
# a_exists = [False] * N
# b_exists = [False] * N
# for a, b in ab:
#     a_exists[a - 1] = True
#     b_exists[b - 1] = True

# # find minimum a -> find minimum b (> a) -> find minimum a (> =b) -> ...
# state = 1
# ans = 0

#     print("#", state, ans,  a_exist, b_exist)

#     if state == 1 and b_exist:
#         ans += 1
#         state = 0
#     # search minimum a (can occur immediately after state = 0)
#     if state == 0 and a_exist:
#         state = 1

print(ans)

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

ab.sort()

ans = 0
for i, (ai, bi) in enumerate(ab):
    if i == 0:
        ans += 1
        l = ai
        r = bi
    else:
        l_tmp = max(l, ai)
        r_tmp = min(r, bi)
        if l_tmp < r_tmp:
            l = l_tmp
            r = r_tmp
        else:
            ans += 1
            l = ai
            r = bi

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


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

removed = -1
ans = 0
print(ab)

for a, b in ab:
    
    #print(a)
    if a > removed:
        removed = b - 1
        ans += 1
        print("OK")

print(ans)

from operator import itemgetter

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


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

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):
##### ABC103-D-Islands War
n,m = map(int,input().split())
l = [list(map(int,input().split())) for _ in range(m)]

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


c = 0

ans = 0

for a,b in l:
    if a >= c:
        c = b
        ans += 1

print(ans)

##### ABC103-D-Islands War
n,m = map(int,input().split())
l = [list(map(int,input().split())) for _ in range(m)]

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



c = 0

ans = 0

for a,b in l:
    if a >= c:
        c = b
        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):
_, M = map(int, input().split())
Schedule = [list(map(int, input().split())) for _ in range(M)]

Schedule = sorted(Schedule, key=lambda x: x[1])
cnt = 0
before_end = 0
for task in Schedule:
    start = task[0]
    end = task[1]
    if start < before_end:
        continue
    cnt += 1
    before_end = end

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

Schedule = sorted(Schedule, key=lambda x: x[1])
cnt = 0
before_end = 0
for task in Schedule:
    start = task[0]
    end = task[1]
    if start < before_end:
        continue
    cnt += 1
    before_end = end
print(cnt)

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()))
Map = [[] for i in range(N)]
for i in range(M):
    a,b=list(map(int,input().split()))
    Map[a-1].append(b-1)

b_list = [0 for i in range(N)]
count=0   
for i in range(N):
    if b_list[i]==1:
       b_list[i]=0
       count+=1
    for j in Map[i]:
        b_list[j]=1

print(count)


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

b_list = [0 for i in range(N)]
count=0   
for i in range(N):
    if b_list[i]==1:
        b_list=[0 for i in range(N)]
        count+=1
    for j in Map[i]:
        b_list[j]=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 = map(int,input().split())
m=[list(map(int, input().split())) for _ in range(M)]
m=sorted(m, key=lambda x: x[1])
p=0
while m!=[]:
    tmp=m[-1][1]-1
    while m!=[] and m[-1][1]>tmp:
        m.pop()
    p+=1
print(p)

N, M = map(int,input().split())
m=[list(map(int, input().split()))[::-1] for _ in range(M)]
m.sort()

b=[]
for i in m:
    if len([tmp for tmp in b if tmp>=i[1]])==0:
        b.append(i[0]-1)
print(len(b))

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

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

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

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


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

def main():
    input = sys.stdin.readline  
    N, M = map(int, input().rstrip().split())

    require_list = []
    for _ in range(M):
        s, e = map(int, input().rstrip().split())
        require_list.append([s, e])
    require_list.sort(key=itemgetter(1))
    print(require_list)

    count = 1
    now_require = require_list[0]
    for next_require in require_list[1:]:
        
        if now_require[1] <= next_require[0]:
            count += 1
        else:
            next_require[1] = now_require[1]
        now_require = next_require

    print(count)

if __name__ == '__main__':
    main()

import sys
from operator import itemgetter
sys.setrecursionlimit(1000000) 

def main():
    input = sys.stdin.readline  
    N, M = map(int, input().rstrip().split())

    require_list = []
    for _ in range(M):
        s, e = map(int, input().rstrip().split())
        require_list.append([s, e])
    require_list.sort(key=itemgetter(1))

    count = 1
    now_require = require_list[0]
    for next_require in require_list[1:]:
        
        if now_require[1] <= next_require[0]:
            count += 1
        else:
            next_require[1] = now_require[1]
        now_require = next_require

    print(count)

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):
n, m = map(int, input().split())
p = []
for i in range(n):
  r, l = map(int, input().split())
  p.append((r, l))

p.sort()
mr = 0
c = 0
for l, r in p:
  if l >= mr:
    mr = r
    continue
  c += 1
  mr = min(mr, r)

print(c)

n, m = map(int, input().split())
p = []
for i in range(m):
  r, l = map(int, input().split())
  p.append((r, l))

p.sort()
mr = 0
c = 0
for l, r in p:
  if l >= mr:
    mr = r
    c += 1
    continue
  mr = min(mr, r)

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

_a, _b = map(int, input().split())
dict_paths = {}
dict_paths[_a] = _b

for i in range(M - 1) :
    a, b = map(int, input().split())
    
    interleave_flg = False

    for k in dict_paths.keys() :
        k_tmp, k_val_tmp = k, dict_paths[k]
        
        # complete intersect
        if a >= k and b <= dict_paths[k] :
            dict_paths.pop(k)
            dict_paths[a] = b
            interleave_flg = True
            
        # nothing required
        elif a <= k and b >= dict_paths[k] :
            interleave_flg = True
            
        
        elif a < k and b > k and b <= dict_paths[k] :
            dict_paths.pop(k)
            dict_paths[a] = k_val_tmp
            interleave_flg = True
            
        
        elif a > k and a < dict_paths[k] and b >= dict_paths[k] :
            dict_paths.pop(k)
            dict_paths[k] = b
            interleave_flg = True
    
    if interleave_flg == False :
        dict_paths[a] = b
            
print(len(dict_paths))
        
    

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

paths = []

for i in range(M) :
    _a, _b = map(int, input().split())
    paths.append((_a, _b))

st = sorted(paths, key = lambda x : x[1])
cnt = 0
prev_b = -1

for i in st :
    if cnt == 0 :
        cnt += 1
        prev_b = i[1]
    else :
        if i[0] >= prev_b :
            cnt += 1
            prev_b = i[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):
import bisect
N,M = map(int,input().split())
x = []
for i in range(M):
    a,b=[int(i) for i in input().split()]
    x.append([a,b,b-a])
x = sorted(x, key=lambda x:x[2])
zan = []
kota = []
for i in range(M):
  zan = sorted(zan)
  mo = x[i]
  ind = bisect.bisect_left(zan,mo[0])
  if ind >= len(zan):
    zan.append(mo[0])
    kota.append(mo)
  else:
    a = kota[ind]
    if mo[1] >= a[2]:
      pass
    else:
      kota.append(mo)
kota = sorted(kota, key=lambda x:x[0])
ans = len(kota)
z = []
for i in range(len(kota)-1):
  print(z)
  x = kota[i]
  if z !=[]:
    x = z
  y = kota[i+1]
  if x[1] > y[0]:
    ans -= 1
    if z == []:
      z = kota[i]
  else:
    z = []
print(ans)

N,M = map(int,input().split())
x = []
for i in range(M):
    a,b=[int(i) for i in input().split()]
    x.append([a,b])
zan = [x[0]]
for i in range(1,M):
  if zan[-1][0] == x[i][0]:
    pass
  else:
    zan.append(x[i])
ans = 0
while zan:
  are = zan.pop(0)
  are = are[1]
  ans += 1
  i = 0
  while zan:
      if zan[i][0] <= are:
        if zan[i][1] <= are:
          zan.pop(i)
        else:
          i +=1
      else:
        i += 1
      try:
        if zan[i][0] > are:
          break
      except:
        break
print(ans)

N,M = map(int,input().split())
x = []
for i in range(M):
    a,b=[int(i) for i in input().split()]
    x.append([a,b])
x = sorted(x, key=lambda x:x[1])
no = 0
ans = 0
for i in range(M):
  a = x[i]
  if (a[0] <= no and a[1] >= no):
    pass
  else:
    no = a[1] -1
    ans += 1
print(ans)

Verdicts: Wrong Answer

Wrong Answer

Accepted