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:
from collections import deque


N , M = map(int,input().split())
ikusa_L = []
for i in range(M):
    ikusa_L.append(list(map(int,input().split())))
ikusa_L.sort(key=lambda x: x[1])
count = 0
while len(ikusa_L) > 0:
    a = ikusa_L.pop(0)
    cut = a[1]
    count += 1
    pop_count = 0
    for i in ikusa_L:
        if i[1] <= cut:
            pop_count += 1
    for i in range(pop_count):
            b = ikusa_L.pop()

print(count)

Submission status: Wrong Answer

Solution code:
import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

N, M = [int(x) for x in input().split()]
AB = []
for _ in range(M):
    a, b = [int(x) for x in input().split()]
    AB.append((a - 1, b - 2))

AB.sort(key=lambda x:(x[0], -x[1]))

cnt = 0
mi = INF
for i in range(M):
    a, b = AB[i][0], AB[i][1]
    mi = min(mi, b)
    if mi < a:
        # print("mi:{}, a:{}, b:{}".format(mi, a, b))
        cnt += 1
        mi = INF

cnt += 1

print(cnt)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
b, n=map(int,input().split())
d=[list(map(int, input().split())) for i in range(n)]

import numpy as np

d2=np.array(d)

#d3=d2[np.argsort(d2[:,1])][::-1]
d3=d2[np.lexsort(d2.T)][::-1]

#print(d3)

cnt=1
i=0

while i<n:
	j=i+1  
	while j<n:
		if d3[j][1]<=d3[i][0]:
			#print(d3[i][0])
			#print(d3[j][1])
			#print(i)
			#print(j)            
			cnt+=1
			i=j-1
			j=n-1
		j+=1
	i+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
b, n=map(int,input().split())
d=[list(map(int, input().split())) for i in range(n)]

import numpy as np

d2=np.array(d)

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

#print(d3)

cnt=1
i=0

while i<n:
	j=i+1  
	while j<n:
		if d3[j][1]<=d3[i][0]:
			#print(d3[i][0])
			#print(d3[j][1])
			#print(i)
			#print(j)            
			cnt+=1
			i=j-1
			j=n-1
		j+=1
	i+=1
print(cnt)

Submission status: Wrong Answer

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

edge = []

last_a = -1
for _ in range(M):
    a, b = map(int, input().split())

    # bがソートされているなら、下のifは消せる
    if a == last_a:
        last_e = edge.pop()
        min_b = min(b, last_e[1])
        edge.append((a, min_b))
    else:
        edge.append((a, b))

    last_a = a

ans = 0
n = len(edge)
i = 0
j = 0

while i < n:
    j = i + 1

    s1, g1 = edge[i]
    set_i = set(range(s1, g1))

    while set_i and j < n:
        s2, g2 = edge[j]
        set_j = set(range(s2, g2))

        set_i = set_i.intersection(set_j)
        if set_i:
            j += 1

    ans += 1
    i = j

print(ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007
dire4 = [(1,0), (0,1), (-1,0), (0,-1)]
dire8 = [(1, 0), (1, 1), (0, 1), (-1, 1), (-1, 0), (-1, -1), (0, -1), (1, -1)]

N, M = LI()
ab = LIR(M)

ab = sorted(ab)

left = [0]*N
right = [0]*N

for ai, bi in ab:
    left[ai-1] = 1
    right[bi-1] = 1

l = N-1
r = N-1
ans = 0

flag = False
while (l>=0):
    if (left[l]):
        while (r>l):
            if (right[r]):
                flag = True
            r -= 1
        if (flag):
            ans += 1
            flag = False
    l -= 1

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(N, M, inputs):
    requests = list(map(lambda x: string_to_int(x), inputs))
    requests = sorted(requests, key=lambda x: x[1])

    deleted = []

    for request in requests:
        f = True
        for d in deleted:
            if d >= request[1] and d < request[1]:
                f = False
                break
        if f:
            deleted.append(request[1] - 1)
    return len(deleted)


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    [N, M] = string_to_int(input())
    ret = solve(N, M, inputs(M))
    print(ret)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 19 20:12:17 2019

@author: Owner
"""

from operator import itemgetter
import bisect

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


ab = [(0, 0)]*M
for m in range(M):
    ab[m] = tuple(map(int, input().split()))

ab = tuple(sorted(ab, key = itemgetter(1)))

#print(ab)
x_rm = -1
res = 0
for m in range(M):
    if ab[m][0] <= x_rm:
        continue
    else:
        x_rm = ab[m][1]
        res += 1
    
    
        

print(res)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
ab=[list(map(lambda x:int(x)-1,input().split())) for i in range(M)]
x=[0]*(N-1)
for i in range(M):
    if x[ab[i][0]]>ab[i][1] or x[ab[i][0]]==0:
        x[ab[i][0]]=ab[i][1]
flag=0
a=N
cnt=0
for i in range(N-1):
    if flag==0 and x[i]==0:
        continue
    elif flag==0 and x[i]>0:
        flag=1
        a=x[i]
        cnt+=1
    elif i<a:
        if x[i]<a:
            a=x[i]
    else:
        if x[i]>0:
            a=x[i]
            cnt+=1
        else:
            flag=0
            a=N
print(cnt)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

T = [0] * N

for a,b in ab:
    T[a-1] += 1
    T[b-1] -= 1
S = [0] * N    
cnt = 0
for i in range(N):
    cnt += T[i]
    S[i] = cnt
flag = True
ans = 0
for i in range(N-1):
    if S[i+1] > S[i] and flag:
        ans += 1
        flag = False
    else:
        flag = True
print(ans)

Submission status: Wrong Answer

Solution code:
# 1 2 3 4 5
# 5 2
# 1 4
# 2 5

NM = input()
N = int(NM.split()[0])
M = int(NM.split()[1])

req_list = []

for i in range(M):
    line=input()
    start = int(line.split()[0])
    end = int(line.split()[1])
    req = {"start": start, "end": end}
    req_list.append(req)

req_sorted = sorted(req_list, key=lambda x:x["end"])
#print(req_sorted)

ans = 0
for i, req in enumerate(req_sorted):
    if i == 0:
        dest = req["end"]
        ans += 1
    if req["end"] < dest:
        dest = req["end"]
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
s = [0] * n
g = [0] * n
for i in range(m):
    a, b = list(map(int, input().split()))
    s[a-1] = 1
    g[b-1] = 1

flag = False
res = 0
for i in range(n):
    if g[i] == 1 and flag == True:
        res += 1
        flag = False
    if s[i] == 1 and flag == False:
        flag = True

print(res)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
s = [0] * n
g = [0] * n
for i in range(m):
    a, b = list(map(int, input().split()))
    s[a-1] = 1
    g[b-1] = 1

flag = False
res = 0
for i in range(n):
    if g[i] == 1 and flag == True:
        res += 1
        flag = False
        continue
    if s[i] == 1 and flag == False:
        flag = True

print(res)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 19 20:12:17 2019

@author: Owner
"""

from operator import itemgetter
import bisect

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


ab = [(0, 0)]*M
for m in range(M):
    ab[m] = tuple(map(int, input().split()))

ab = tuple(sorted(ab, key = itemgetter(0)))

a = [0]*M
b = [0]*M
for m in range(M):
    a[m], b[m] = ab[m]
b.sort()
res = 0
n = -1
while True:
    tmp = bisect.bisect_left(a, n)
    
    n = b[bisect.bisect_right(b, a[tmp])]
    res+=1
    if n > a[m]:
        break
    
    
        

print(res)

Submission status: Wrong Answer

Solution code:
def cost(bridge,x,y):
    for i in range(x-1,y-1):
        bridge[i] +=1
    return bridge

n, m = [int(i) for i in input().split()]
a=[]
b=[]
for i in range(m):
    x1, y1 = [int(i) for i in input().split()]
    a.append(x1)
    b.append(y1)

ans = 0
while True:
    bridge = [0]*(n-1)
    for i in range(len(a)):
        bridge = cost(bridge,a[i],b[i])
    r = bridge.index(max(bridge)) + 1

    for i,an,bn in zip(range(len(a)),a,b):
        if an <= r <= bn-1:
            a[i]=0
            b[i]=0

    ans += 1
    if len(set(a))==1 and a[0]==0:
        break

print(ans)

Submission status: Wrong Answer

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

import sys

input = sys.stdin.readline

inf = 1000000

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

    deleted = {}
    cnt = 0
    while len(deleted) != m:
        max_l = -1
        min_r = inf
        for i in range(len(M)):
            if i in deleted:
                continue
            rem = False
            if max_l < M[i][0] and M[i][0] < min_r:
                max_l = M[i][0]
                rem = True
            if max_l < M[i][1] and M[i][1] < min_r:
                min_r = M[i][1]
                rem = True
            if rem:
                deleted[i] = True
            if max_l == -1 or min_r == inf:
                print(cnt)
                return
        cnt += 1
    print(cnt)

main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 19 20:12:17 2019

@author: Owner
"""

import numpy as np
from operator import itemgetter
import bisect

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


ab = [(0, 0)]*M
c = np.zeros(N)
for m in range(M):
    ab[m] = tuple(map(int, input().split()))

ab = tuple(sorted(ab, key = itemgetter(0)))

a = [0]*M
b = [0]*M
for m in range(M):
    a[m], b[m] = ab[m]
b.sort()
res = 0
n = -1
while True:
    tmp = bisect.bisect_left(a, n)
    
    n = b[bisect.bisect_right(b, a[tmp])]
    
    if n > a[m]:
        break
    res+=1
    
        

print(res)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sun May 19 20:12:17 2019

@author: Owner
"""

import numpy as np
from operator import itemgetter
import bisect

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


ab = [(0, 0)]*M
c = np.zeros(N)
for m in range(M):
    ab[m] = tuple(map(int, input().split()))

ab = tuple(sorted(ab, key = itemgetter(0)))

a = [0]*M
b = [0]*M
for m in range(M):
    a[m], b[m] = ab[m]
b.sort()
res = 0
n = -1
while True:
    tmp = bisect.bisect_left(a, n)
    
    n = b[bisect.bisect_right(b, a[tmp])]
    res+=1
    if n > a[m]:
        break
    
    
        

print(res)

Submission status: Wrong Answer

Solution code:
"""
区間スケジューリング
終端で降順にソートすれば良い
"""
n, m=map(int, input().split())
hope=[]
for i in range(m):
    a, b=map(int, input().split())
    hope.append((a, b))
hope.sort(reverse=True, key=lambda x: x[0])
hope.sort(reverse=True, key=lambda x: x[1])
ans=0
for i in range(m-1):
    if i==0:
        target=hope[i][0]+0.5
    if not hope[i+1][0]<target<hope[i+1][1]:
        ans=ans+1
        target=hope[i+1][0]+0.5
print(ans+1)

Submission status: Wrong Answer

Solution code:
"""
区間スケジューリング
終端で降順にソートすれば良い
"""
n, m=map(int, input().split())
hope=[]
for i in range(m):
    a, b=map(int, input().split())
    hope.append((a, b))
hope.sort(reverse=True, key=lambda x: x[0])
hope.sort(reverse=True, key=lambda x: x[1])
ans=0
for i in range(m-1):
    if i==0:
        target=hope[i][0]
    if target>=hope[i+1][1]:
        ans=ans+1
        target=hope[i+1][0]
print(ans+1)

Submission status: Wrong Answer

Solution code:
"""
区間スケジューリング
終端で降順にソートすれば良い
"""
n, m=map(int, input().split())
hope=[]
for i in range(m):
    a, b=map(int, input().split())
    hope.append((a, b))
hope.sort(reverse=True, key=lambda x: x[0])
hope.sort(reverse=True, key=lambda x: x[1])
ans=0
for i in range(m-1):
    if i==0:
        target=hope[i][0]
    if target>hope[i+1][1]:
        ans=ans+1
        target=hope[i+1][0]
print(ans+1)

Submission status: Wrong Answer

Solution code:
n, m=map(int, input().split())
hope=[]
for i in range(m):
    a, b=map(int, input().split())
    hope.append((a, b))
hope.sort(reverse=True, key=lambda x: x[0])
hope.sort(reverse=True, key=lambda x: x[1])
ans=0
for i in range(m-1):
    if i==0:
        target=hope[i][0]
    if not target<hope[i+1][1]:
        ans=ans+1
        target=hope[i+1][0]
print(ans+1)

Submission status: Wrong Answer

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



l = 1
r = n
ans = 1
for i in range(m):
    a,b = map(int, input().split())
    # 現在のl,rでカバーできない場合
    if b < l:
        ans += 1

        r = b
    elif a > r:
        ans += 1

        l = a
    
    if a > l:
        l = a
    if b < r:
        r = b


print(ans)

Submission status: Wrong Answer

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

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

for i in range(M-1):
    a, b = map(int, input().split())
    tmp = len(min_max)
    check = 0
    for j in range(tmp):
        min_, max_ = min_max[j]
        if b <= min_:
            check += 1
        elif a < min_ and b < max_:
            min_max[j] = [min_, b]
        elif b < max_:
            min_max[j] = [a, b]
        elif a >= min_ and a < max_ and b > max_:
            min_max[j] = [a, max_]
        elif a >= max_:
            check += 1
    if check == tmp:
        min_max.append([a, b])

print(len(min_max))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
st=[[] for i in range(n)]
en=[[] for i in range(n)]
ju=[0 for i in range(m)] #0：未処理、1：処理中、－１：処理後
for i in range(m):
    a,b=map(int,input().split())
    st[a-1].append(i)
    en[b-1].append(i)
ans=0
co=0
now=[]
while(co<n):
    if len(now)!=0 and len(en[co])!=0:
        for i in now:
            ju[i]=-1
        ans+=1
        now=[]
    for i in st[co]:
        ju[i]=1
        now.append(i)
    co+=1
print(ans)

Submission status: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

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

left = [""] * n
right = [""] * n

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

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

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

Submission status: Wrong Answer

Solution code:
import sys
input= sys.stdin.readline
N,M =map(int,input().split())

lis = [[0,0]for _ in range(N)]
for _ in range(M):
    a,b = [int(i)-1 for i in input().split()]
    lis[a][0]+=1
    lis[b][1]+=1

ans = 1
sta = 0
for i in range(N):
    if lis[i][sta] != 0:
        ans += 1
        if lis[i][sta-1]!=0:
            ans += 1
        else:
            sta = (sta+1)%2
print(ans//2)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(m)]
L=10**6
ans=0
for a,b in ab[::-1]:
    if not a<=L<b:
        ans+=1
        L=a
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = [int(t) for t in input().split()]
a = [[0]*2 for i in range(M)]  # 始点と距離
for i in range(M):
    s, e = [int(t) for t in input().split()]
    a[i][0] = s - 1
    a[i][1] = e - s

b = sorted(a, key=lambda x: x[1], reverse=True)

ans = []


def judge(b_start, b_goal):
    for j in range(len(ans)):
        a_start = ans[j][0]
        a_goal = a_start + ans[j][1]
        if a_start <= b_start and b_goal <= a_goal:
            ans[j][0] = b_start
            ans[j][1] = b_goal - b_start
            return False

        if a_start < b_goal and b_goal <= a_goal:
            ans[j][1] = b_goal - a_start
            return False

        if a_start <= b_start and b_start < a_goal:
            ans[j][0] = b_start
            ans[j][1] = a_goal - b_start
            return False

    return True


for i in range(M):
    if not ans:
        ans.append(b[i])
    else:
        b_start = b[i][0]
        b_goal = b_start + b[i][1]
        if judge(b_start, b_goal):
            ans.append(b[i])

print(len(ans))

Submission status: Wrong Answer

Solution code:
N, M = [int(t) for t in input().split()]
a = [[0]*2 for i in range(M)]  # 始点と距離
for i in range(M):
    s, e = [int(t) for t in input().split()]
    a[i][0] = s
    a[i][1] = e - s

b = sorted(a, key=lambda x: x[1])

ans = []


def judge(b_start, b_goal):
    for j in range(len(ans)):
        a_start = ans[j][0]
        a_goal = a_start + ans[j][1]
        if a_start < b_goal and b_goal <= a_goal:
            ans[j][1] = b_goal - a_start
            return False

        elif a_start <= b_start and b_start < a_goal:
            ans[j][0] = b_start
            ans[j][1] = a_goal - b_start
            return False

        elif b_start <= a_start and a_goal <= b_goal:
            return False

    return True


for i in range(M):
    if b[i][1] == 1 or not ans:
        ans.append(b[i])
    else:
        b_start = b[i][0]
        b_goal = b_start + b[i][1]
        if judge(b_start, b_goal):
            ans.append(b[i])

print(len(ans))

Submission status: Wrong Answer

Solution code:
N, M = [int(t) for t in input().split()]
a = [[0]*2 for i in range(M)]  # 始点と距離
for i in range(M):
    s, e = [int(t) for t in input().split()]
    a[i][0] = s
    a[i][1] = e - s

b = sorted(a, key=lambda x: x[1])

ans = []


def judge(b_start, b_goal):
    for j in range(len(ans)):
        a_start = ans[j][0]
        a_goal = a_start + ans[j][1]
        if a_start < b_goal and b_goal <= a_goal:
            ans[j][0] = max(a_start, b_start)
            ans[j][1] = b_goal - max(a_start, b_start)
            return False

        elif a_start <= b_start and b_start < a_goal:
            ans[j][0] = b_start
            ans[j][1] = min(a_goal, b_goal) - b_start
            return False

        elif b_start <= a_start and a_goal <= b_goal:
            return False

    return True


for i in range(M):
    if not ans or b[i][1] == 1:
        ans.append(b[i])
    else:
        b_start = b[i][0]
        b_goal = b_start + b[i][1]
        if judge(b_start, b_goal):
            ans.append(b[i])

print(len(ans))

Submission status: Wrong Answer

Solution code:
N, M = [int(t) for t in input().split()]
a = [[0]*2 for i in range(M)]  # 始点と距離
for i in range(M):
    s, e = [int(t) for t in input().split()]
    a[i][0] = s
    a[i][1] = e - s

b = sorted(a, key=lambda x: x[1])

ans = []
for i in range(M):

    if not ans or b[i][1] == 1:
        ans.append(b[i])
        continue

    b_start = b[i][0]
    b_goal = b_start + b[i][1]

    for j in range(len(ans)):
        a_start = ans[j][0]
        a_goal = ans[j][0] + ans[j][1]
        if a_start < b_goal and b_goal <= a_goal:
            ans[j][0] = max(a_start, b_start)
            ans[j][1] = b_goal - max(a_start, b_start)
            break
        elif a_start <= b_start and b_start < a_goal:
            ans[j][0] = b_start
            ans[j][1] = min(a_goal, b_goal) - b_start
            break
        elif b_start <= a_start and a_goal <= b_goal:
            break

        if j == len(ans) - 1:
            ans.append(b[i])

print(len(ans))

Submission status: Wrong Answer

Solution code:
N, M = [int(t) for t in input().split()]
a = [[0]*2 for i in range(M)]  # 始点と距離
for i in range(M):
    s, e = [int(t) for t in input().split()]
    a[i][0] = s
    a[i][1] = e - s

b = sorted(a, key=lambda x: x[1])

ans = []
for i in range(M):

    if not ans or b[i][1] == 1:
        ans.append(b[i])
        continue

    b_start = b[i][0]
    b_goal = b_start + b[i][1]

    for j in range(len(ans)):
        a_start = ans[j][0]
        a_goal = ans[j][0] + ans[j][1]
        if a_start < b_goal and b_goal <= a_goal:
            # 距離は変わる
            ans[j][1] = min(a_goal, b_goal) - a_start
            break
        elif a_start <= b_start and b_start < a_goal:
            # 始点は変わる(=距離も変わる)
            ans[j][1] = a_goal - b_start
            ans[j][0] = max(a_start, b_start)
            break
        elif b_start <= a_start and a_goal <= b_goal:
            break

        if j == len(ans) - 1:
            ans.append(b[i])

print(len(ans))

Submission status: Wrong Answer

Solution code:
N, M = [int(t) for t in input().split()]
a = [[0]*2 for i in range(M)]  # 始点と距離
for i in range(M):
    s, e = [int(t) for t in input().split()]
    a[i][0] = s - 1
    a[i][1] = e - s

b = sorted(a, key=lambda x: x[1])
ans = []
for i in range(M):
    if b[i][1] == 1:
        ans.append(b[i])
        continue

    if not ans:
        ans.append(b[i])
        continue

    b_start = b[i][0]
    b_goal = b_start + b[i][1]

    for j in range(len(ans)):
        a_goal = ans[j][0] + ans[j][1]
        if ans[j][0] < b_goal and b_goal <= a_goal:
            # 距離は変わる
            ans[j][1] = b_goal - ans[j][0]
            break
        elif ans[j][0] <= b_start and b_start < a_goal:
            # 始点は変わる(=距離も変わる)
            ans[j][1] = a_goal - b_start
            ans[j][0] = b_start
            break
        elif b_start <= ans[j][0] and a_goal <= b_goal:
            break

        if j == len(ans) - 1:
            ans.append(b[i])

print(len(ans))

Submission status: Wrong Answer

Solution code:
N, M = [int(t) for t in input().split()]
a = [[0]*2 for i in range(M)]  # 始点と距離
for i in range(M):
    s, e = [int(t) for t in input().split()]
    a[i][0] = s - 1
    a[i][1] = e - s

b = sorted(a, key=lambda x: x[1])
ans = []
for i in range(M):
    if b[i][1] == 1:
        ans.append(b[i])
        continue

    if not ans:
        ans.append(b[i])
        continue

    b_start = b[i][0]
    b_goal = b_start + b[i][1]

    for j in range(len(ans)):
        a_goal = ans[j][0] + ans[j][1]
        if ans[j][0] < b_goal and b_goal <= a_goal:
            # 距離は変わる
            ans[j][1] = b_goal - ans[j][0]
            break
        elif ans[j][0] <= b_start and b_start < a_goal:
            # 始点は変わる(=距離も変わる)
            ans[j][1] = a_goal - b_start
            ans[j][0] = b_start
            break
        elif b_start <= ans[j][0] and b_goal <= a_goal:
            break

        if j == len(ans) - 1:
            ans.append(b[i])

print(len(ans))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
AB=[]
for i in range(m):
  a,b=map(int,input().split())
  AB.append([a,b])
AB.sort()
AB.append([float('inf'),float('inf')])
ans,left,right=0,0,float('inf')
for i in range(m):
    right=min(right,AB[i][1])
    left=AB[i][0]
    if right==left+1 and left!=AB[i+1][0]:
      ans+=1
      right=float('inf')
if right!=float('inf'):
  ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
need=[tuple(map(int,input().split())) for i in range(M)]
need.sort(key=lambda x:x[1])
ans=0
bef=0
for a,b in need:
    if a<=bef<b-1:
        continue
    else:
        ans+=1
        bef=b-1
print(ans)

Submission status: Wrong Answer

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

bridge = [list(map(int,input().split(' '))) for i in range(m)]
bridge=[[bridge[i][0]-1,bridge[i][1]-2] for i in range(m)]
ans = 0
index = -1
# print(bridge)
while(1):
    left = [0 for i in range(n-1)]
    right = [0 for i in range(n-1)]
    flag = False
    for i in range(len(bridge)):
        if not(bridge[i][0]<=index and index<=bridge[i][1]):
            flag = True
            left[bridge[i][0]]+=1
            right[bridge[i][1]]+=1
        else:
            bridge[i][0]=-1
            bridge[i][1]=n
    if flag is False:
        break;
    
    for i in range(1,len(left)):
        left[i] += left[i-1]
    for i in reversed(range(len(right)-1)):
        right[i]+=right[i+1]
    # print(left)
    # print(right)
    
    island = list()
    for i in range(n-1):
        island.append(left[i]-(right[0]-right[i]))
    index = island.index(max(island))
    
    # print("index=",index)
    ans+=1
print(ans)

Submission status: Wrong Answer

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

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

fights = sorted(fights, reverse=True)

import bisect


bridges = []
for a,b in fights:
    a_position = bisect.bisect(bridges, a)
    b_position = bisect.bisect(bridges, b)
    
    if a_position == b_position:
        bisect.insort(bridges, a)
        #print(bridges)

print(len(bridges))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
b_list=[]
INF=10**6
for i in range(n):
    b_list.append(INF)
for i in range(m):
    a,b=map(int,input().split())
    b_list[a-1]=min(b-1,b_list[a-1])
end=INF
count=0
for i in b_list:
    if i==INF:
        pass
    else:
        if i>=end:
            count=count+1
        end=min(end,b_list[i])
print(count+1)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
L = []
for _ in range(M):
    L.append(list(map(int,input().split())))
L = sorted(L,key=lambda x:x[1])
now = -10
cnt = 0
for x in L:
    if now < x[0]:
        now = x[1]
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
n,m=map(int, input().split())
ab=[list(map(int,input().split())) for i in range(m)]
c=[-1]*(n+1)

l=n
r=-1
for i in ab:
    c[i[1]]=max(c[i[1]],i[0])
    l=min(l,i[0])
    r=max(r,i[1])

ans=0
while r>l:
    if c[r]==-1:
        r-=1
    else:
        r=c[r]
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
L = [list(map(int, input().split())) for _ in range(M)]
MAP = [0] * N

counter = 0
f = True
while f:
    ma = 0
    ma_index = 0
    f = False
    
    MAP = [0] * N
    
    for v in L:
        MAP[v[0] - 1] += 1
        MAP[v[1] - 1] -= 1

    for i in range(N - 1):
        MAP[i + 1] += MAP[i]
        if ma < MAP[i]:
            ma = MAP[i]
            ma_index = i + 1
    
    for i in range(len(L)):
        v = L[i]
        if v[0] <= ma_index and v[1] > ma_index:
            L[i][0] = 0
            L[i][1] = 0
            f = True
            
            ma -= 1
            if ma == 0:
                break
            
    if f:
        counter += 1
    
print(counter)

Submission status: Wrong Answer

Solution code:

def main():
    num, younou = map(int, input().split())

    data = list(map(int, input().split()))
    ans_list = [data]

    for j in range(younou - 1):
        data = list(map(int, input().split()))
        for i in range(len(ans_list)):
            if data[1] <= ans_list[i][0] or data[0] >= ans_list[i][1]:
                continue
            else:
                ans_list[i][0] = max(data[0],  ans_list[i][0])
                ans_list[i][1] = min(data[1],  ans_list[i][1])
                break
        else:
            ans_list.append(data)


    print(len(ans_list))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

def main():
    num, younou = map(int, input().split())

    data = list(map(int, input().split()))
    ans_list = [data]

    for j in range(younou - 1):
        data = list(map(int, input().split()))
        for i in range(len(ans_list)):
            if data[0] < ans_list[i][1] and data[1] > ans_list[i][0]:
                ans_list[i][0] = max(data[0],  ans_list[i][0])
                ans_list[i][1] = min(data[1],  ans_list[i][1])
                break
        else:
            ans_list.append(data)

    print(len(ans_list))


if __name__ == '__main__':
    main()