Problem:


Score : 400 points

Problem Statement

There are N islands lining up from west to east, connected by N-1 bridges.

The i-th bridge connects the i-th island from the west and the (i+1)-th island from the west.

One day, disputes took place between some islands, and there were M requests from the inhabitants of the islands:

Request i: A dispute took place between the a_i-th island from the west and the b_i-th island from the west. Please make traveling between these islands with bridges impossible.

You decided to remove some bridges to meet all these M requests.

Find the minimum number of bridges that must be removed.

Constraints

All values in input are integers.

2 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq a_i < b_i \leq N

All pairs (a_i, b_i) are distinct.

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
a_2 b_2
:
a_M b_M

Output

Print the minimum number of bridges that must be removed.

Sample Input 1

5 2
1 4
2 5

Sample Output 1

1

The requests can be met by removing the bridge connecting the second and third islands from the west.

Sample Input 2

9 5
1 8
2 7
3 5
4 6
7 9

Sample Output 2

2

Sample Input 3

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

Sample Output 3

4



Sample input:
5 2
1 4
2 5


Sample output:
1

Submission status: Wrong Answer

Solution code:
import sys
import functools

lines = sys.stdin.readlines()
hops = dict()
N, M = None, None
for line in lines:
    a, b = map(int, line.rstrip().split())
    if not N and not M:
        N = a
        M = b
        continue
    if a > b:
        a, b = b, a
    hop = hops.get(b-a)
    if not hop:
        hops[b-a] = hop = set()
    hop.add((a, b))
    M -= 1
    if M == 0:
        break

covered = []
for key in sorted(hops.keys()):
    found = False
    for a, b in hops[key]:
        for area in covered:
            if not (area[0] >= b or area[1] <= a):
                covered.remove(area)
                covered.append((max(area[0], a), min(area[1], b)))
                found = True
                break

        if not found:
            covered.append((a, b))


answer = len(covered)
print(answer)

Submission status: Wrong Answer

Solution code:
import sys
import functools

lines = sys.stdin.readlines()
hops = dict()
N, M = None, None
for line in lines:
    a, b = map(int, line.rstrip().split())
    if not N and not M:
        N = a
        M = b
        continue
    if a > b:
        a, b = b, a
    hop = hops.get(b-a)
    if not hop:
        hops[b-a] = hop = set()
    hop.add((a, b))

covered = []
for key in sorted(hops.keys()):
    found = False
    for a, b in hops[key]:
        for area in covered:
            if not (area[0] >= b or area[1] <= a):
                covered.remove(area)
                covered.append((max(area[0], a), min(area[1], b)))
                found = True
                break

        if not found:
            covered.append((a, b))


answer = len(covered)
print(answer)

Submission status: Wrong Answer

Solution code:
import sys 

lines = sys.stdin.readlines()
hops = dict() 
for line in lines:
    a, b = map(int, line.rstrip().split())
    if a > b:
        a, b = b, a
    hop = hops.get(b-a)
    if not hop:
        hops[b-a] = hop = set()
    hop.add((a, b)) 

covered = []
for key in sorted(hops.keys()):
    found = False
    for a, b in hops[key]:
        for area in covered:
            if not (area[0] >= b or area[1] <= a): 
                covered.remove(area)
                covered.append((max(area[0], a), min(area[1], b)))
                found = True
                break

        if not found:
            covered.append((a, b)) 
    

answer = len(covered)
print(answer)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n, m = list(map(int, input().split()))
ab = []
bridge = []
check = []
for i in range(m):
    check.append([])
for i in range(m):
    a, b = list(map(int, input().split()))
    ab.append([a, b])
def judge(x, y, z):
    if x <= z and z < y:
        return True
    else:
        return False
for i in range(1, n):
    judgeBridge = []
    for j in range(m):
        if judge(ab[j][0], ab[j][1], i):
            judgeBridge.append(j)
        else:
            pass
    bridge.append(judgeBridge)
bridgeSort = []
for i in range(n-1):
    bridgeSort.append([i, len(bridge[i])])
from operator import itemgetter
bridgeSorted = sorted(bridgeSort, key=itemgetter(1), reverse=True)
count = 0
for i in range(n):
    if ab != check:
        flag = False
        for j in range(bridgeSorted[i][1]):
            if ab[bridge[bridgeSorted[i][0]][j]] != []:
                ab[bridge[bridgeSorted[i][0]][j]] = []
                flag = True
            else:
                pass
        if flag:
            count = count + 1
        else:
            pass
    else:
        print(count)
        exit()

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
a = [[]*2]*M
for i in range(M):
    a[i]=input().rstrip().split()

#aをbについて昇順にする。
a=sorted(a, key=lambda x: x[1])
hasi = -1#どこの橋を壊したか
sum = 0

for i in range(0,M):

    c1 = int(a[i][0])
    c2 = int(a[i][1])
    # print(c1,c2,hasi)
    if (hasi >= c1) and  (hasi < c2):
        continue
    hasi = c2-1
    sum = sum+1


print(sum)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
a = [[]*2]*M
for i in range(M):
    a[i]=input().rstrip().split()

#aをbについて昇順にする。
a=sorted(a, key=lambda x: x[1])
hasi = 0#どこの橋を壊したか
sum = 0

for i in range(0,M):
    
    c1 = int(a[i][0])
    c2 = int(a[i][1])
    # print(c1,c2,hasi)
    if hasi >= c1:
        continue
    hasi = c2-1
    sum = sum+1


print(sum)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
a = [[]*2]*M
for i in range(M):
    a[i]=input().rstrip().split()

#aをbについて昇順にする。
a=sorted(a, key=lambda x: x[1])
hasi = 0#どこの橋を壊したか
sum = 0

for i in range(0,M):
    c1 = int(a[i][0])
    c2 = int(a[i][1])
    if hasi >= c1:
        continue
    else:
        hasi = c2-1
        sum = sum+1

print(sum)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
a = [[]*2]*M
for i in range(M):
    a[i]=input().rstrip().split()

#aをbについて昇順にする。
a=sorted(a, key=lambda x: x[1])
hasi = [0]*(N-1)#どこの橋を壊したか
sum = 0

for i in range(0,M):
    c1 = int(a[i][0])
    c2 = int(a[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[c2-2]=1
        sum = sum+1

print(sum)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
a = [[]*2]*M
for i in range(M):
    a[i]=input().rstrip().split()

#aをbについて昇順にする。
a=sorted(a, key=lambda x: x[1])
hasi = [0]*(N-1)#どこの橋を壊したか
sum = 0

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

print(sum)

Submission status: Wrong Answer

Solution code:
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



print(sum)

Submission status: Wrong Answer

Solution code:
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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def solve(N, M, a, b):
    pass


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

    ans = 0
    mini = INF
    for a, b in l:
        if mini <= a:
            ans += 1
        mini = min(mini, b)

    print(ans + 1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/python3

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
import sys
sys.setrecursionlimit(10000)
INF = float("inf")
YES, Yes, yes, NO, No, no = "YES", "Yes", "yes", "NO", "No", "no"
dy4, dx4 = [0, 1, 0, -1], [1, 0, -1, 0]


def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W


def solve(N, M, a, b):
    pass


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

    ans = 0
    mini = INF
    for a, b in l:
        if mini < a:
            ans += 1
        mini = min(mini, b)

    print(ans + 1)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
x = [[0, 0] for i in range(m)]
ans = 0
for i in range(m):
    x[i][0], x[i][1] = map(int, input().split())
# for i in range(m):
    # print(x[i])
# print('-'*20)
x = sorted(x, key=lambda y: y[1])
# for i in range(m):
#    print(x[i])
ans += 1
tmp = x[0][1]
for i in range(1, m):
    if x[i][0] < tmp < x[i][1]:
        continue
    else:
        ans += 1
        tmp = x[i][1]
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
x = [[0, 0] for i in range(m)]
ans = 0
for i in range(m):
    x[i][0], x[i][1] = map(int, input().split())
# for i in range(m):
    # print(x[i])
# print('-'*20)
x = sorted(x, key=lambda y: y[1])
# for i in range(m):
#    print(x[i])
tmp = x[0][1]
for i in range(1, m):
    if x[i][0] < tmp < x[i][1]:
        continue
    else:
        ans += 1
        tmp = x[i][1]
        if i == m-1:
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
x = [[0, 0] for i in range(m)]
ans = 0
for i in range(m):
    x[i][0], x[i][1] = map(int, input().split())
# for i in range(m):
    # print(x[i])
# print('-'*20)
x = sorted(x, key=lambda y: y[1])
for i in range(m):
    print(x[i])
tmp = x[0][1]
for i in range(1, m):
    if x[i][0] < tmp < x[i][1]:
        continue
    else:
        ans += 1
        tmp = x[i][1]
        if i == m-1:
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = []
for _ in range(m):
    u, v = map(int, input().split())
    a.append((u, v))
i, j, c = 0, 0, 0
for u, v in a:
    if u >= j:
        c += 1
        i = u
        j = v
    else:
        j = min(j, v)
print(c)

Submission status: Wrong Answer

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

print(t)

Submission status: Wrong Answer

Solution code:
ab=[]

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

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

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

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

Submission status: Wrong Answer

Solution code:
ab=[]

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

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

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

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

Submission status: Wrong Answer

Solution code:
ab=[]

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

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

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

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

Submission status: Wrong Answer

Solution code:
ab=[]

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

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

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

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

Submission status: Wrong Answer

Solution code:
ab=[]

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

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

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

res=0
for z in range(len(ab)): #試行回数制限
    mark=0
    x=ab[0][1] #右端最小
    if x==ab[-1][1]:
        res+=1
        del ab[:]
        break
    for j in range(len(ab)):
        if x > ab[j][0]:
            pass
        else:
            mark=j
            break
    if len(ab[:mark])>0:
        res+=1
        del ab[:mark]
    if len(ab)==0:
        break
    
print(res)

Submission status: Wrong Answer

Solution code:
ab=[]

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

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

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

res=0
for z in range(len(ab)): #試行回数制限
    mark=0
    x=ab[0][1] #右端最小
    if x==ab[-1][1]:
        res+=1
        del ab[:]
        #break
    for j in range(len(ab)):
        if x > ab[j][0]:
            pass
        else:
            mark=j
            break
    if len(ab[:mark])>0:
        res+=1
        del ab[:mark]
    if len(ab)==0:
        break
    
print(res)

Submission status: Wrong Answer

Solution code:
ab=[]

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

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

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

res=0
for z in range(len(ab)): #試行回数制限
    mark=0
    x=ab[0][1] #右端最小
    if x==ab[-1][1]:
        res+=1
        print("last")
        del ab[:]
        #break
    for j in range(len(ab)):
        if x > ab[j][0]:
            pass
        else:
            mark=j
            break
    if len(ab[:mark])>0:
        print("mark")
        res+=1
        del ab[:mark]
    print(res,x,mark,ab)
    if len(ab)==0:
        break
    
print(res)

Submission status: Wrong Answer

Solution code:
def main():
    string = input().split()
    island = int(string[0])
    dispute_num = int(string[1])
    disputes = []
    for i in range(dispute_num):
        string = input().split()
        disputes.append([int(string[0]), int(string[1])])

    cut_count = 1
    left_cut = disputes[0][0]
    right_cut = disputes[0][1]
    for i in range(1, dispute_num):
        left = disputes[i][0]
        right = disputes[i][1]
        if( right_cut > left):
            left_cut = left
            if(right_cut > right):
                right_cut = right
        else:
            cut_count += 1
            right_cut = right
            left_cut = left

    print(cut_count)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
ab=[]

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

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

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

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

Submission status: Wrong Answer

Solution code:
def main():
    """
    2 <= N <= 10^5
    1 <= M <= 10^5
    1 <= ai < bi <= N
    (ai, bi) != (aj, bj)
    """
    N, M = map(int, input().split())
    A, B = zip(*[
        map(int, input().split())
        for _ in range(M)
    ])
    ans = f(N, M, A, B)
    #ans = TLE(N, M, A, B)

    print(ans)


def TLE(N, M, A, B):
    """
    """
    ans = N - 1
    for a in A:
        for b in B:
            pass

    return ans


def f(N, M, A, B):
    """
    ai, bi の分断:

    入力例1
        1, 4 の分断
            橋1-3 のどれかを除去
        2, 5 の分断
            橋2-4 のどれかを除去
        共通部: 2-3
        要望ごとの共通部を探す必要がある
            M^2: TLE

    A_min: 西
    A_max: 東
    B_min: 西
    B_max: 東

    入力例2
    9 5
    1------8
     2----7
      3-5
       4-6
          7-9

    a_min,b_max の順に並べる
    要望の東側が以前の西側未満ならOK
    要望の西側が以前の東側を超えないならOK ? 
    """
    ab = sorted(zip(A, B), key=lambda x: (x[0], -x[1]))
    ans = 0
    bef_a, bef_b = -1, float("inf")
    for i, (a, b) in enumerate(ab):
        #print(" " * (a-1), a, "-" * (b - a - 1), b, sep="")
        if bef_a <= a < b < bef_b:
            pass
        elif bef_b <= a:
            ans += 1
        elif bef_a < a < bef_b < b:
            pass

        bef_a, bef_b = a, b

    return ans + 1


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
ab=[]

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

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

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

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

Submission status: Wrong Answer

Solution code:
ab=[]

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

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

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

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

Submission status: Wrong Answer

Solution code:
ab=[]

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

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

print(ab)

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

Submission status: Wrong Answer

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

main()

Submission status: Wrong Answer

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

main()

Submission status: Wrong Answer

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

main()

Submission status: Wrong Answer

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

main()

Submission status: Wrong Answer

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

disputes = []
for _ in range(m):
    disputes.append([int(a) for a in input().split()])

filtered = [disputes[0]]
for i in range(1, m):
    d = disputes[i]
    for p, f in enumerate(filtered):
        if f[0] < d[0] and d[0] < f[1] <= d[1]:
            f[0] = d[0]

        elif f[0] >= d[0] and f[1] <= d[1]:
            pass

        elif d[0] <= f[0] < d[1] and f[1] > d[1]:
            f[1] = d[1]

        elif f[0] < d[0] and f[1] > d[1]:
            f[0] = d[0]
            f[1] = d[1]

        elif p == len(filtered) - 1:
            filtered.append(d)
            break

print(len(filtered))

Submission status: Wrong Answer

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

disputes = []
for _ in range(m):
    disputes.append([int(a) for a in input().split()])

filtered = [disputes[0]]
for i in range(1, m):
    d = disputes[i]
    for f in filtered:
        if f[0] < d[0] and d[0] < f[1] <= d[1]:
            f[0] = d[0]

        elif f[0] >= d[0] and f[1] <= d[1]:
            pass

        elif d[0] <= f[0] < d[1] and f[1] > d[1]:
            f[1] = d[1]
        
        elif f[0] < d[0] and f[1] > d[1]:
            f[0] = d[0]
            f[1] = d[1]
        
        else:
            filtered.append(d)
            break

print(len(filtered))

Submission status: Wrong Answer

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

disputes = []
for _ in range(m):
    disputes.append([int(a) for a in input().split()])

filtered = [disputes[0]]
for i in range(1, m):
    d = disputes[i]
    for f in filtered:
        if f[0] <= d[0] and d[0] <= f[1] <= d[1]:
            f[0] = d[0]

        elif f[0] >= d[0] and f[1] <= d[1]:
            pass

        elif d[0] <= f[0] <= d[1] and f[1] >= d[1]:
            f[1] = d[1]

        else:
            filtered.append(d)
            break

print(len(filtered))

Submission status: Wrong Answer

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

disputes = []
for _ in range(m):
    disputes.append([int(a) for a in input().split()])

filtered = [disputes[0]]
for i in range(1, m):
    d = disputes[i]
    for f in filtered:
        if f[0] < d[0] and d[0] < f[1] < d[1]:
            f[0] = d[0]

        elif f[0] >= d[0] and f[1] <= d[1]:
            pass

        elif d[0] < f[0] < d[1] and f[1] > d[1]:
            f[1] = d[1]

        else:
            filtered.append(d)
            break

print(len(filtered))

Submission status: Wrong Answer

Solution code:
def main():
    n = [int(i) for i in input().split()]
    bridge = [0 for i in range(n[0]-1)]
    reqs = [[int(j) for j in input().split()] for i in range(n[1])]
    reqs.sort(key=lambda x:(x[1]-x[0]))

    for req in reqs:
        if 1 not in bridge[req[0]-1:req[1]-1]:
            bridge[req[1] - 2] = 1
    print(bridge.count(1))

main()

Submission status: Wrong Answer

Solution code:
def main():
    # get data
    n = [int(i) for i in input().split()]
    bridge = [0 for i in range(n[0]-1)]
    reqs = [[int(j) for j in input().split()] for i in range(n[1])]
    reqs.sort(key=lambda x:(x[1]-x[0]))

    # bridge
    for req in reqs:
        for j in range(req[0], req[1]):
            if bridge[j-1] == 1:
                break
        else:
            bridge[req[1] - 2] = 1
    print(bridge.count(1))

main()

Submission status: Wrong Answer

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

to_right = list(map(lambda x: False, range(N)))
to_left  = list(map(lambda x: False, range(N)))

for _ in range(M):
  s, t = map(int, input().split())
  to_right[s-1] = True
  to_left[t-1] = True

right_searching = True
res = 0
i = 0

while i < N:
  if to_right[i] and right_searching:
    right_searching = False
    i += 1
    continue
  if to_left[i] and not right_searching:
    right_searching = True
    res += 1
    continue
  i += 1

print(res)

Submission status: Wrong Answer

Solution code:
ab=[]

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

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

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

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

Submission status: Wrong Answer

Solution code:
ab=[]

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

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

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

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

Submission status: Wrong Answer

Solution code:
ab=[]

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
ab=[]

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

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

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

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

print(res)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

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

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

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

Submission status: Wrong Answer

Solution code:
ab=[]

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

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

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

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

print(res)

Submission status: Wrong Answer

Solution code:
ab=[]

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

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

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

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

print(res)

Submission status: Wrong Answer

Solution code:
ab=[]

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

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

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

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

print(res)