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 os
import sys

import numpy as np

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

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

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

AB.sort()

counts = np.zeros(N, dtype=int)
stack = []
ans = 0
for a, b in AB:
    a -= 1
    b -=1
    if counts[a] > 0:
        while stack:
            r = stack.pop()
            counts[r] -= 1
        ans += 1
    stack.append(b)
    counts[b] += 1
if stack:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
N, M = map(int, input().split())
a = [0]*M
b = [0]*M
for i in range(M):
    a[i], b[i] = map(int, input().split())
a.sort()
b.sort()
ans = 0
tmp = -1
for x in a:
    id = bisect.bisect_right(b, x)
    if id != tmp:
        ans += 1
        tmp = id

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
N, M = map(int, input().split())
a = [0]*M
b = [0]*M
for i in range(M):
    a[i], b[i] = map(int, input().split())
a.sort()
b.sort()
ans = 1
tmp = 0
for x in a:
    id = bisect.bisect_right(b, x)
    if id > tmp:
        ans += 1
        tmp = id

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

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

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

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

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
li = [[0,0] for i in range(n)]

memo = 10**6
for i in range(m):
    a,b = map(int,input().split())
    a-=1
    b-=1
    li[a][0] += 1
    li[b][1] += 1
    memo = min(memo,b)

cnt = 1
for i in range(n-1,-1,-1):
    if li[i][0] > 0:
        cnt += 1
    if i==memo:
        print(cnt)
        break
"""
for i in range(n):
    print("{:>2}".format(li[i][0]),end="")
print()
for i in range(n):
    print("{:>2}".format(li[i][1]),end="")
print()
"""

Submission status: Wrong Answer

Solution code:
import numpy as np
import copy
N,M = (int(i) for i in input().split()) 
a_tmp = [[int(i) for i in input().split()] for i in range(M)] 
a = copy.deepcopy(a_tmp)
cnt = 0
def cal(a,cnt):
    l = np.zeros(N+1)
    flg = np.zeros(M)
    for i in range(len(a)):
        l[a[i][0]:a[i][1]] += 1
    tmp = l.argmax()
    cnt += 1
    #print("tmp:"+str(tmp))
    #tmpを区間に含むリストにフラグを立てる
    tmp_index = []
    for j in range(len(a)):
        if a[j][0]<=tmp<a[j][1]:
            #print(j)
            tmp_index.append(j)
    #print(tmp_index)
    if len(tmp_index)>0:
        for k in range(len(tmp_index)-1,-1,-1):
            #print(k)
            a.pop(tmp_index[k])
    #print(a)
    if len(a)<=0:
        return cnt
    else:
        return cal(a,cnt)
print(cal(a,0))

Submission status: Wrong Answer

Solution code:
import numpy as np

temp=list(map(int, input().split()))
N=temp[0]
M=temp[1]

A=np.zeros((M,2)).astype(int)

for i in range(M):
  temp=list(map(int, input().split()))
  temp[0]-=1
  temp[1]-=1
  A[i]=temp
idx=A[:,1].argsort()
a=[0]*M
b=[0]*M
for i in range(M):
  a[i]=A[idx[i],0]
  b[i]=A[idx[i],1]
flag=False
x=-1
ans=0
for i in range(len(a)):
  if a[i]>x:
    x=b[i]
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
print("reference: maspy")

N, M = map(int,input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
 
ab.sort(key = lambda x: x[1])
print("ab:", *ab)
  
right = -1 # 最後に破壊されている場所（右のindex）
answer = 0

# 確かにこれでいける。バトンタッチ。
for a, b in ab:
  if a < right:
    print("answer, right:", answer, right)
    continue
  else:
    answer += 1
    right = b
    print("answer, right:", answer, right)
    
print(answer)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys
from operator import itemgetter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = MAP()
edges = []
for i in range(M):
    a, b = MAP()
    edges.append((a, 0))
    edges.append((b, 1))
edges.sort(key=itemgetter(1), reverse=1)
edges.sort(key=itemgetter(0))

# 左右左右ってなる回数を数える
cur = cnt = 0
for _, flag in edges:
    if cur != flag:
        cur = flag
        if cur == 1:
            cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M = MAP()
edges = []
for i in range(M):
    a, b = MAP()
    edges.append((a, 1))
    edges.append((b, 0))
edges.sort()

# 左右左右ってなる回数を数える
cur = 1
cnt = 0
for _, flag in edges:
    if cur != flag:
        cur = flag
        if cur == 0:
            cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
def examD():
    N, M = LI()
    right = defaultdict(bool); left = defaultdict(bool)
    for i in range(M):
        a, b = LI()
        left[a] = True
        right[b] = True
    ans = 0
    cur = False
    for i in range(1,N+1):
        if right[i] and cur:
            ans +=1
            cur = False
        if left[i]:
            cur = True

    print(ans)

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()

Submission status: Wrong Answer

Solution code:

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

from operator import itemgetter
def SectionScheduling(array):
    if len(array)>0:
        array.sort(key=itemgetter(1))
        pos=array[0][1]
        array.sort()
        for i in range(len(array)-1,-1,-1):
            if array[i][0]<pos: #posを含むか注意
                del array[i]
        print(array)

        return 1 + SectionScheduling(array)
    else:
        return 0

print(SectionScheduling(L))

Submission status: Wrong Answer

Solution code:
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<=ab[i][0]:
        last=ab[i][1]
        ans+=1
    else:
        last=ab[i][1]
print(ans)

Submission status: Wrong Answer

Solution code:
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<ab[i][0]:
        last=ab[i][1]
        ans+=1
    else:
        last=ab[i][1]
print(ans)

Submission status: Wrong Answer

Solution code:
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<ab[i][0]:
        last=ab[i][1]
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
a = [tuple(map(int, input().split())) for i in range(M)]
a = [tuple([abs(x[0]-x[1]), x[0], x[1]]) for x in a]
a.sort(key=lambda x:x[0])
divided = [0 for i in range(N-1)]

for i in a:
    # 分断済みなら次の関係へ
    if sum(divided[i[1]-1:i[2]-1]) > 0:
        continue
    
    # 中央の方から分断
    p = i[1] + i[0]//2
    divided[p-1]=1
    
print(sum(divided))

Submission status: Wrong Answer

Solution code:
# ABC103D
# 貪欲法：区間スケジューリング問題に帰着
# ソートして喧嘩している遠い島(b[i])の最も近いところから貪欲に選んでいく
# ex) 1-10, 2-5, 6-8
# なら2-5, 6-8を選ぶ．
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
ab.sort(key=lambda x: x[1])
print(ab)
ans = 1             # 一つ目分
tmp = ab[0][1] - 0.1      # 一つ目の橋は必ず壊すので
for i in range(1, M):
    if ab[i][0] < tmp < ab[i][1]:   # 直近で壊した橋が喧嘩している島の間にある時は何もしない
        pass
    else:                           # 間にない時は新しく橋を壊す
        ans += 1
        tmp = ab[i][1] - 0.1

print(ans)

Submission status: Wrong Answer

Solution code:
# ABC103D
# 貪欲法：区間スケジューリング問題に帰着
# ソートして喧嘩している遠い島(b[i])の最も近いところから貪欲に選んでいく
# ex) 1-10, 2-5, 6-8
# なら2-5, 6-8を選ぶ．
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
ab.sort(key=lambda x: x[1])
ans = 1             # 一つ目分
tmp = ab[0][1]      # 一つ目の橋は必ず壊すので
for i in range(1, M):
    if ab[i][0] < tmp < ab[i][1]:   # 直近で壊した橋が喧嘩している島の間にある時は何もしない
        pass
    else:                           # 間にない時は新しく橋を壊す
        ans += 1
        tmp = ab[i][1]

print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
a = []
for i in range(m):
  x,y = map(int, input().split())
  a.append((x,y))
a.sort()
ans = 1
l,r = a[0]
for x,y in a[1:]:
  if r <= x:
    ans += 1
    l = x
    r = y

print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
a = []
for i in range(m):
  x,y = map(int, input().split())
  a.append((x,y))
a.sort()
ans = 1
l,r = a[0]
for x,y in a[1:]:
  if r <= x:
    ans += 1
    r = x
    l = y

print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
a = []
for i in range(m):
  x,y = map(int, input().split())
  a.append((x,y))
a.sort()
ans = 1
l,r = a[0]
for x,y in a[1:]:
  if r <= x:
    ans += 1
    r = x
    l = y
  else:
    r = max(r, y)
print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

n, m = map(int, input().split())
ab = []
for _ in range(m):
    ab.append(sorted(list(map(int, input().split()))))
abs = sorted(ab, key=itemgetter(1))
abs = sorted(abs, key=lambda x: x[1] - x[0])
ml = [abs[0][1] - 1]
for i in range(1, m):
    for j in ml:
        if j in range(abs[i][0], abs[i][1]):
            break
        if j == ml[-1]:
            ml.append(abs[i][1] - 1)
print(len(ml))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

l_range=[]
for _ in range(m):
    a,b=map(int,input().split())
    
    isExist=False
    for idx in range(len(l_range)):
        if (not (b<=l_range[idx][0] or l_range[idx][1]<=a)):
            isExist=True
            l_range[idx]=(max(a,l_range[idx][0]),min(b,l_range[idx][1]))
            break
    
    if (not isExist):
        l_range.append((a,b))

print(len(l_range))

Submission status: Wrong Answer

Solution code:
island, suppose = map(int, input().split(' '))

mylist = []
for i in range(suppose):
    mylist.append(list(map(int, input().split(' '))))

mylist_2 = sorted(mylist)
mylist.sort(key = lambda x: x[1])

def BinarySearch(x, mylist):
    left = 0
    right = len(mylist) - 1
    while(True):
        center = left + (right - left) // 2
        if mylist[left] == mylist[right]:
            return left
            break
        elif mylist[center] < x:
            left = center + 1
        elif mylist[center] >= x:
            right = center - 1
            
ans = 0            
while mylist != []:
    i = mylist_2[-1][0]
    mylist_01 = [x[1] for x in mylist]
    brbr = BinarySearch(i, mylist_01)
    del mylist[brbr:]
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
l_table = [False for _ in range(N)]
lr_table = {}
for _ in range(M):
    l_n, r_n = map(int, input().split())
    l_table[l_n-1] = True
    lr_table[(l_n-1,r_n-1)] = True

ret = 0
left = -1
for i in range(N):
    if left != -1 and (left,i) in lr_table and lr_table[(left,i)]:
        # print(i,left)
        ret += 1
        left = -1
    if l_table[i]:
        left = i

print(ret)

Submission status: Wrong Answer

Solution code:
def solve():
    N,M = map(int, input().split())
    lr_table = [[False, False] for _ in range(N)] # [n][0]:left,[n][1]:right
    for _ in range(M):
        l_n, r_n = map(int, input().split())
        lr_table[l_n-1][0] = True
        lr_table[r_n-1][1] = True
    
    ret = 0
    left = -1
    for i in range(N):
        if lr_table[i][1] and left != -1:
            # print(i,left)
            ret += 1
            left = -1
        if lr_table[i][0]:
            left = i
            
    print(ret)
    
solve()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
c = [list(map(int, input().split())) for i in range(M)]
r = 0
bridge = N
for i in range(M):
  a, b = c[M-1-i]
  if(a > bridge or bridge >= b):
    r += 1
    bridge = a
print(r)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m=map(int,input().split())
    E=[[] for _ in range(n)]
    for _ in range(m):
        a,b=map(int,input().split())
        a-=1; b-=1
        E[a].append(b)
        E[b].append(a)

    visited=[0]*n
    def dfs(v)->int:
        if(visited[v]): return 0
        visited[v]=1
        Q=[v]
        cnt=0
        while(Q):
            v=Q.pop()
            cnt+=1
            for nv in E[v]:
                if(visited[nv]): continue
                visited[nv]=1
                Q.append(nv)
        return cnt
    print(max(*(dfs(v) for v in range(n)))-1)
resolve()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
points=[]
for i in range(m):
    a,b=map(int,input().split())
    points.append([a,b])
points = sorted(points)
arrow = float('-inf')
res = 0
for l,r in points:
    if l > arrow:
        res += 1
        arrow = r
    elif r < arrow:
        arrow = r
print(res)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
n,m=map(int,input().split())
a=[list(map(int,input().split())) for i in range(m)]
b=sorted(a,key=itemgetter(0))
c=[0]*(n-1)
r=m
ans=0
while r>0:
    c=[0]*(n-1)
    for i in range(n-1):
        for j in range(m):
            if b[j][0]<=i+1 and i+1<=b[j][1]:
                c[i]+=1
    d=c.index(max(c))+1
    for i in range(m):
        if b[i][0]<=d and d<=b[i][1]:
            b[i][0]=0
            b[j][1]=0
    r-=max(c)
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = [int(str) for str in input().strip().split()]
AB = [[int(str) for str in input().strip().split()] for _ in range(M)]

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


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

print(ans)

Submission status: Wrong Answer

Solution code:
N, M = [int(str) for str in input().strip().split()]
AB = [[int(str) for str in input().strip().split()] for _ in range(M)]

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

print(A_B)

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

print(ans)

Submission status: Wrong Answer

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

banned_list = []*M
for i in range(M):
    banned_list.append(tuple(map(int,input().split())))
    
banned_briges = [set() for _ in range(N-1)]
for j,one in enumerate(banned_list):
    for i in range(one[0]-1,one[1]-1):
        banned_briges[i] |= {j}
        
banned_num = [len(one) for one in banned_briges] 

counter = 0
while sum([sum(one) for one in banned_briges]) != 0:
    remove_index = banned_num.index(max(banned_num))
    remove_island = banned_briges[remove_index]
    banned_briges = [one-remove_island for one in banned_briges]
    banned_num = [len(one) for one in banned_briges] 
    counter += 1
    
print(counter)

Submission status: Wrong Answer

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

banned_list = []*M
for i in range(M):
    banned_list.append(tuple(map(int,input().split())))
    
banned_briges = [set() for _ in range(N-1)]
for j,one in enumerate(banned_list):
    for i in range(one[0]-1,one[1]-1):
        banned_briges[i] |= {j}
        
banned_num = [sum(one) for one in banned_briges] 

counter = 0
while sum([sum(one) for one in banned_briges]) != 0:
    remove_index = banned_num.index(max(banned_num))
    remove_island = banned_briges[remove_index]
    banned_briges = [one-remove_island for one in banned_briges]
    banned_num = [sum(one) for one in banned_briges] 
    counter += 1

Submission status: Wrong Answer

Solution code:
#まず、その橋を壊すと何個の問題が解決されるかをリストで取得する。
N,M=map(int,input().split())
mp=[ tuple(map(int,input().split())) for _ in range(M)]
lst=[0]*(N-1)
bridges=[1]*(N-1)
#ここは総当たりでおｋ。オーダーN*Mで済むし。
for i in range(1,N):#問題と対応するように、0から始めない。
    cnt=0
    for j in range(M):
        if mp[j][0] <= i < mp[j][1]:
            cnt+=1
    lst[i-1]=cnt

#argmaxを使いたいのでnumpyを入れる
import numpy as np
lst_=np.array(lst)
ans=0
#そしてもう一回for、多いところを切っていく。
for n in range(M):
    if 0 in bridges[mp[n][0]-1:mp[n][1]-1]:
        continue
    else:
        flg=np.argmax(lst_[mp[n][0]-1:mp[n][1]-1])+mp[n][0]-1
        #↑スライスでインデックスがずれてしまう。それを修正せよ。
        bridges[flg]=0
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
#まず、その橋を壊すと何個の問題が解決されるかをリストで取得する。
N,M=map(int,input().split())
mp=[ tuple(map(int,input().split())) for _ in range(M)]
lst=[0]*(N-1)
bridges=[1]*(N-1)
#ここは総当たりでおｋ。オーダーN*Mで済むし。
for i in range(1,N):#問題と対応するように、0から始めない。
    cnt=0
    for j in range(M):
        if mp[j][0] <= i < mp[j][1]:
            cnt+=1
    lst[i-1]=cnt

#argmaxを使いたいのでnumpyを入れる
import numpy as np
lst_=np.array(lst)
ans=0
#そしてもう一回for、多いところを切っていく。
for n in range(M):
    if 0 in bridges[mp[n][0]-1:mp[n][1]]:
        continue
    else:
        flg=np.argmax(lst_[mp[n][0]-1:mp[n][1]-1])+mp[n][0]-1
        #↑スライスでインデックスがずれてしまう。それを修正せよ。
        bridges[flg]=0
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
mp=[ tuple(map(int,input().split())) for _ in range(M)]
mp.sort(key=lambda x:x[1]-x[0])
#差が小さい順にソートとかもできるんだ！
bridges=[1]*(N-1)
mid=(N-1)//2
for (i,j) in mp:
    if 0 in bridges[i-1:j-1]:#すでに切られてるならセーフ
        continue
    else:#より中心に近い橋を切断する
        if i<=(mid)<j:
            bridges[((N-1)//2)-1]=0
        else:
            if abs(mid-(j-1))<=abs(mid-(i)):
                bridges[(j-1)-1]=0
            else:
                bridges[i-1]=0

print(len(bridges)-sum(bridges))

Submission status: Wrong Answer

Solution code:
#103d(高速化)
import random
N,M = map(int, input().split())

all_candidate_drop_bridge = set()

for i in range(M):
    a,b = map(int, input().split())    
    ab_candidate_drop_bridge = {i for i in range(a,b)}
    #print("#########################")
    #print(a,b)
    #print(ab_candidate_drop_bridge)
    #print("重複チェック")
    
    for candidate_drop_bridge in random.sample(all_candidate_drop_bridge,len(all_candidate_drop_bridge)):
        loaded_candidate_drop_bridge = candidate_drop_bridge
        candidate_drop_bridge = set(candidate_drop_bridge)
        #print(candidate_drop_bridge)
        if len(candidate_drop_bridge & ab_candidate_drop_bridge) != 0:
            #print("重複")
            all_candidate_drop_bridge.discard(loaded_candidate_drop_bridge)
            all_candidate_drop_bridge.add(tuple(candidate_drop_bridge & ab_candidate_drop_bridge))
            break
    else:
        #print("新規追加")
        all_candidate_drop_bridge.add(tuple(ab_candidate_drop_bridge))

#print(all_candidate_drop_bridge)
print(len(all_candidate_drop_bridge))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
l = [[0]*2 for i in range(M)]
sum = 0
for i in range(M):
    l[i][0],l[i][1] = map(int,input().split())
l.sort(key=lambda l:l[1])
x = 0
for i in range(M):
    if x<l[i][0]:
        x=l[i][1]
        sum+=1
print(sum)

Submission status: Wrong Answer

Solution code:
def main():
    n, m = map(int, input().split())
    # ab = [list(map(int, input().split())) for _ in range(m)]
    ab = [[]*2]*m
    for i in range(m):
        ab[i] = list(map(int, input().split()))
    # print(ab)
    ab.sort
    count = 0
    r = ab[0][1] - 1
    count += 1
    for i in range(1, m):
        if ab[i][1] - 1 < r:
            r = ab[i][1] - 1
        if r < ab[i][0]:
            r = ab[i][1] - 1
            count += 1
    print(count)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(m)]
    ab.sort
    count = 0
    r = ab[0][1] - 1
    count += 1
    for i in range(1, m):
        if ab[i][1] - 1 < r:
            r = ab[i][1] - 1
        if r < ab[i][0]:
            r = ab[i][1] - 1
            count += 1
    print(count)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(m)]
    ab.sort
    count = 0
    r = ab[0][1] - 1
    count += 1
    for i in range(1, m):
        if ab[i][1] - 1 < r:
            r = ab[i][1] - 1
        if r < ab[i][0]:
            r = ab[i][0] - 1
            count += 1
    print(count)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    n, m = map(int, input().split())
    ab = [list(map(int, input().split())) for _ in range(m)]
    ab.sort
    r = ab[0][1] - 1
    count = 1
    for i in range(1, m):
        if ab[i][1] - 1 < r:
            r = ab[i][1] - 1
        if r < ab[i][0]:
            r = ab[i][0] - 1
            count += 1
    print(count)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
l=list(list(map(int,input().split())) for i in range(m))
sl=sorted(l, key=lambda x:x[1])

ans=0
count=0

for i in range(m):
  if count<l[i][0]:
    ans+=1
    count=l[i][1]-1
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
count = 0
s = [[]*2]*m
for i in range(0, m):
  s[i] = list(map(int, input().split()))
s.sort(key = lambda x: x[0])
r = s[0][1]
count += 1
for i in range(1, m):
  if r > s[i][0] & r > s[i][1]:
    r = s[i][1]
  if r <= s[i][0]:
    r = s[i][1]
    count += 1
print(count)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
count = 0
s = [[]*2]*m
for i in range(0, m):
  s[i] = list(map(int, input().split()))

r = s[0][1]
count += 1
for i in range(1, m):
  if r > s[i][0] & r > s[i][1]:
    r = s[i][1]
  if r <= s[i][0]:
    r = s[i][1]
    count += 1
print(count)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ab = [[int(i) for i in input().split()] for i in range(m)]
count = 0
while len(ab) > 0:
    ab = sorted(ab, key = lambda x: x[1])
    end = ab[0]
    list.sort(ab, reverse=True)
    remove = ab.index(end)
    del ab[(remove - 1):]
    count += 1
print(int(count))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
count = 0
#二次元配列の宣言の仕方がわからなかったので、調べた
s = [[]*2]*m
for i in range(0, m):
  s[i] = list(map(int, input().split()))

r = s[0][1]
count += 1
for i in range(1, m):
  if r <= s[i][0]:
    r = s[i][1]
    count += 1
print(count)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
mp=[ tuple(map(int,input().split())) for _ in range(M)]
mp.sort(key=lambda x:x[1]-x[0])
#差が小さい順にソートとかもできるんだ！
bridges=[1]*(N-1)
mid=(N-1)//2
for (i,j) in mp:
    #より中心に近い橋を切断する
    if 0 in bridges[i-1:j-1]:
        continue
    else:
        if i<=(mid)<j:
            bridges[((N-1)//2)-1]=0
        else:
            if abs(mid-(j-1))<=abs(mid-(i)):
                bridges[(j-1)-1]=0
            else:
                bridges[i-1]=0

print(len(bridges)-sum(bridges))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# 貪欲法で解く
N, M = map(int, input().split()) # N, Mの入力
ab = [list(map(int, input().split())) for i in range(M)] # ai, biをlistで管理
ans = 0 # 解答の初期化
islands = [list(range(N))] # 島の行き来できる状態をlistで管理
ab.sort(key = lambda x: x[1] -x[0]) # 要望を島間の距離の少ない順に並べる
for request in ab:
    for union in islands: # 島が行き来できる状態なら最も右で分断
        if request[0] - 1 in union and request[1] - 1 in union:
            ans += 1
            islands.append(union[:union.index(request[1] - 1)]) # 分断後の島状況をそれぞれ行き来可能な島のlistとして追加
            islands.append(union[union.index(request[1] - 1):])
            islands.remove(union) # 元のlistを取り除く
print(ans) # 解答の出力

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

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

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

ret = 0
flag = False
for i, f in schedule :
    if f == 0 :
        if flag :
            ret += 1
        flag = False
    else :
        flag = True
print(ret)

Submission status: Wrong Answer

Solution code:
import bisect

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

Bridge = [[-1,0],[10**5+1,10**5+2]]
for a,b in AB:
  rank = bisect.bisect_left(Bridge,[a,b])
  a1,b1 = Bridge[rank-1]
  a2,b2 = Bridge[rank]
  if a1 <= a < b1:
    Bridge[rank-1][0] = a
    if b < b1:
      Bridge[rank-1][1] = b
  elif b1 <= a and b <= a2:
    Bridge.append([a,b])
    Bridge.sort()
  elif a2 < b <= b2:
    Bridge[rank][1] = b
    if a2 < a:
      Bridge[rank][0] = a
#print(Bridge)
print(len(Bridge)-2)

Submission status: Wrong Answer

Solution code:
import bisect

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

Bridge = [[-1,0],[10**5+1,10**5+2]]
for a,b in AB:
  rank = bisect.bisect_left(Bridge,[a,b])
  a1,b1 = Bridge[rank-1]
  a2,b2 = Bridge[rank]
  if a1 < a < b1:
    Bridge[rank-1][0] = a
    if b < b1:
      Bridge[rank-1][1] = b
  elif b1 <= a and b <= a2:
    Bridge.append([a,b])
    Bridge.sort()
  elif a2 < b < b2:
    Bridge[rank][1] = b
    if a2 < a:
      Bridge[rank][0] = a
#print(Bridge)
print(len(Bridge)-2)

Submission status: Wrong Answer

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

imos = [0] * N

for x in AB:
    imos[x[0]-1] += 1
    imos[x[1]-1] -= 1
for i in range(1, N):
    imos[i] += imos[i-1]
# print(imos)
# 0が橋がかかっている状態で1が壊れた状態
bridges = [0] * N
for y in AB:
    if sum(bridges[y[0]-1:y[1]-1]) == 0:
        z = imos[y[0]-1:y[1]-1]
        bridges[y[0]-1 + z.index(max(z))] = 1
# print(bridges)
print(sum(bridges))

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
A=list(tuple(map(int,input().split())) for i in range(m))
A.sort(key=lambda x:x[1])

point,count=0,0
for x,y in A:
    if point<=x:
        point=x
        count +=1

print(count)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
A=list(tuple(map(int,input().split())) for i in range(m))
A.sort(key=lambda x:x[1])

point,count=0,0
for x,y in A:
    if point<x:
        point=x
        count +=1
print(count)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
w = [list(map(int, input().split())) for _ in range(M)]
w.sort(key=lambda x: x[1])
f = 0
ans = 0
for i in range(M):
    if w[i][0] <= f < w[i][1]:
        continue
    f = w[i][1]
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
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)
A.sort(reverse=True)
B.sort()
cnt=1
i=0
while  A[i] >=B[0]:
    i+=1
    cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
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)
A.sort(reverse=True)
B.sort()
cnt=1
i=0
while  A[i] >=B[i]:
    i+=1
    cnt+=1
print(cnt)