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:
ab=[]
n,m = map(int,input().split())


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

enabled=set()
remain=set()
for i in range(m):
    remain.add(i)

res=0
for i in range(1,n+1):
    for j in remain-enabled:
        if i == ab[j][0]:
            enabled.add(j)
    for j in enabled:
        if i == ab[j][1] and j in remain:
            res+=1
            remain-=enabled
            enabled=set()
            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())))

enabled=set()
remain=set()
for i in range(m):
    remain.add(i)

res=0
for i in range(1,n+1):
    for j in remain-enabled:
        if i == ab[j][0]:
            enabled.add(j)
    for j in enabled:
        if i == ab[j][-1] and j in remain:
            res+=1
            remain-=enabled
            enabled=set()
            break

print(res)

Submission status: Wrong Answer

Solution code:
import sys

N, M = map(int, input().split())
A = [0 for i in range(N+1)]
for i in range(M):
	A1, A2 = map(int, input().split())
	A[A1] = A2
	
ans = 0
min_dir = sys.maxsize
for i in range(1, N+1):
	if A[i] != 0:
		min_dir = min(A[i], min_dir)
	if i >= min_dir:
		ans += 1
		if A[i] != 0:
			min_dir = A[i]
		else:
			min_dir = sys.maxsize
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
A = [0 for i in range(N+1)]
for i in range(M):
	A1, A2 = map(int, input().split())
	A[A1] = A2
	
ans = 0
min_dir = 10000000000000
for i in range(1, N+1):
	if A[i] != 0:
		min_dir = min(A[i], min_dir)
	if i >= min_dir:
		ans += 1
		if A[i] != 0:
			min_dir = A[i]
		else:
			min_dir = 100000000000000
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = list(map(int,input().split()))
data = []
for i in range(m):
	a, b = list(map(int,input().split()))
	data.append((a, b))
data.sort(key=lambda x: x[1])
p = -1
ans = 0
for a, b in data:
	if a <= p:
		continue
	else:
		x = b - 1
		ans += 1
print(ans)

Submission status: Wrong Answer

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

#http://drken1215.hatenablog.com/entry/2018/07/21/224200

# 条件の入力
N,M = map(int, raw_input().split())

orders=[]
for i in range(M):
	first, second = map(int, raw_input().split())
	orders.append((first, second))
	

#secondの値の小さい順に並び替え
cmpFunc = lambda x, y : x[1] - y[1]
sorted_orders = sorted(orders, cmpFunc)
print sorted_orders

#多分、この辺がgreedyにとっていく処理
ret=0
endtime=0
for order in sorted_orders:
	if order[0] >= endtime:
		endtime=order[1]
		ret+=1

#結果の出力
print ret

Submission status: Wrong Answer

Solution code:
#a = int(input())
#b,c = map(int,input().split())
#s = input()
#list_s = list(input())
#list_int = list(map(int,input().split()))

#list = [0 for i in range(n)]
#dp = [[0 for i in range(A)] for j in range(B)]

#list_int 並べて出力 print (' '.join(map(str,ans_li)))
#list_str 並べて出力 print (' '.join(list))

# 2進数 format(10, 'b') # '1010'

# aa=[int(input()) for i in range(n)]

#for i,name in enumerate(list)

''' 二次元配列を一列ずつ
for i in ans:
	print(*i)
'''
''' heapq
queue = []
heapq.heapify(queue) #heapqの作成
heapq.heappush(queue,num) #numのpush(値の追加)
pop = heapq.heappop(queue) #numのpop(最小値の出力)
pop = heapq.heappushpop(queue,num) #push -> pop

'''

from collections import defaultdict
import sys,heapq,bisect,math,itertools,string
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7


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

q.append([1,1])
q.sort(reverse=True)

left = q[0][1]
ans = 0
for i in range(1,M+1):
	if left >= q[i][0]:
		ans += 1
		left = q[i][1]

print(ans)

Submission status: Wrong Answer

Solution code:
#a = int(input())
#b,c = map(int,input().split())
#s = input()
#list_s = list(input())
#list_int = list(map(int,input().split()))

#list = [0 for i in range(n)]
#dp = [[0 for i in range(A)] for j in range(B)]

#list_int 並べて出力 print (' '.join(map(str,ans_li)))
#list_str 並べて出力 print (' '.join(list))

# 2進数 format(10, 'b') # '1010'

# aa=[int(input()) for i in range(n)]

#for i,name in enumerate(list)

''' 二次元配列を一列ずつ
for i in ans:
	print(*i)
'''
''' heapq
queue = []
heapq.heapify(queue) #heapqの作成
heapq.heappush(queue,num) #numのpush(値の追加)
pop = heapq.heappop(queue) #numのpop(最小値の出力)
pop = heapq.heappushpop(queue,num) #push -> pop

'''

from collections import defaultdict
import sys,heapq,bisect,math,itertools,string
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7


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

q.sort(reverse=True)

left = q[0][1]
ans = 0
for i in range(1,M):
	if left >= q[i][0]:
		ans += 1
		left = q[i][1]

print(ans+1)

Submission status: Wrong Answer

Solution code:
from collections import OrderedDict
N,M = list(map(int,input().split()))
d = OrderedDict()
for i in range(M):
    a,b = list(map(int,input().split()))
    if not a in d:
        d[a] = b
    elif d[a] > b:
        d[a] = b
ans = 1
end = 0
for  a in sorted(d.keys()):
    if a == end:
        end = 0
        ans += 1
    if end == 0:
        end = d[a]
    if end > d[a]:
        end = d[a]
print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int, input().split())
G=[list() for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
ans=0
index=-1
for i in range(1,N):
    for p in G[i]:
        if index<p<i:
            ans+=1
            index=i-1
print(ans)
if N==5 and M==2:
    print("ans")

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ab_list = list()
for _ in range(m):
    a, b = map(int, input().split())
    ab_list.append([a, b])
ab_list = sorted(ab_list, key=lambda x: x[1])
x = -1
ans = 0
for a, b in ab_list:
    if a < x:
        continue
    else:
        x = b-1
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
l = [list(map(int, input().split())) for i in range(m)]
l.sort(key=lambda x: x[1])
cut_points = [l[0][1]]
for i in l:
    for cut_point in cut_points:
        if i[1] < cut_point or cut_point <= i[0]:
            cut_points.append(i[1])
print(len(set(cut_points)))

Submission status: Wrong Answer

Solution code:
n,m=map(int, input().split())
a=[list(map(int, input().split())) for i in range(m)]
a.sort()
count=0
ans=m
end=n
for i in range(m):
    if a[i][0]>=end:
        ans-=count-1
        count=0
        end=n
    end=min(a[i][1],end)
    count+=1
    #print(count,end,ans)
print(ans)

Submission status: Wrong Answer

Solution code:
N,M=list(map(int,input().split()))
a=[]
b=[]
for i in range(0,M):
    ai,bi=input().split()
    a.append(ai)
    b.append(bi)
a=list(map(int,a))
b=list(map(int,b))
i=0
an=[]
bn=[]

while i<M:
    if a[i]!=a[i-1]:
        an.append(a[i])
        bn.append(b[i])
    i+=1

ai=an
bi=bn
c=0
if(len(ai)==1):
    print(c+1)
else:

    i=1
    while(i<len(ai)):
        if(ai[i]<bi[i-1]):
            bi[i]=min(bi[i],bi[i-1])
            if(i==(len(ai)-1)):
                c+=1
        else:
            c+=1
            if(i==(len(ai)-1)):
                c+=1
        i+=1

    print(c)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
s=[]
for i in range(m):
    a,b=map(int,input().split())
    s.append([a,b-1])
s.sort(key=lambda x:x[1])
ans=0
t=None
for i,j in s:
    if(t is None or t<i):
        t=i
        ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map( int, input().split())
Q = []
for i in range(M):
    a,b = map(int,input().split())
    Q.append([a,b])
Q = sorted(Q)
ans = 1
LQ = len(Q)
while LQ != 0:
    stan = Q[0][1]
    k = 1
    if Q[0][0] < stan:
        stan = min(stan,Q.pop(0)[1])
        LQ -= 1
    else:
        ans += 1
        break
print(ans)

Submission status: Wrong Answer

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

for i in range(0,M):
    a = list(map(int,input().split()))
    problems.append(a)

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

x = 0
ans = 0

for j in range(0,len(problems)):
    if problems[j][0] <= x:
        continue
    else:
        x = problems[j][0]
        ans += 1

print(ans)

Submission status: Wrong Answer

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

for i in range(0,M):
    a = list(map(int,input().split()))
    problems.append(a)

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

x = 0
ans = 0

for j in range(1,len(problems)):
    if problems[j][0] <= x:
        continue
    else:
        x = problems[j][0]
        ans += 1

print(ans)

Submission status: Wrong Answer

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

for i in range(0,M):
    a = list(map(int,input().split()))
    problems.append(a)

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

x = problems[0][0]
ans = 1

for j in range(1,len(problems)):
    if problems[j][0] <= x:
        continue
    else:
        x = problems[j][0]
        ans += 1

print(ans)

Submission status: Wrong Answer

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

for i in range(0,M):
    a = list(map(int,input().split()))
    problems.append(a)

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

x = problems[0][0]
ans = 1

for j in range(1,len(problems)):
    if problems[j][0] <= x:
        continue
    else:
        x = problems[j][0]
        ans += 1
        
print(ans)

Submission status: Wrong Answer

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

you = []
for i in range(M):
    s,a =  list(map(int,input().split(" ")))
    you.append([a-s,s])

you.sort()

col=1
cnt = 0
while(True):    
    if(len(you)==0):
        break
    cmp = you[0]
    cp = [i for i in you]
    #print(cp)
    for i in range(len(you)-1,0,-1):
        #print(you[i][0],cmp[0]+cmp[1],you[i][0]+you[i][1])
        if(you[i][1]<cmp[0]+cmp[1]<=you[i][0]+you[i][1]):
            del cp[i]
    del cp[0]
    you = cp
    cnt+=1
print(cnt)

Submission status: Wrong Answer

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

you = []
for i in range(M):
    s,a =  list(map(int,input().split(" ")))
    you.append([a-s,s])

you.sort()

col=1
cnt = 0
while(True):    
    if(len(you)==0):
        break
    cmp = you[0]
    cp = [i for i in you]
    #print(cp)
    for i in range(len(you)-1,0,-1):
        #print(you[i][0],cmp[0]+cmp[1],you[i][0]+you[i][1])
        if(you[i][0]<cmp[0]+cmp[1]<=you[i][0]+you[i][1]):
            del cp[i]
    del cp[0]
    you = cp
    cnt+=1
print(cnt)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

A = sorted(A, key=lambda x: x[0])
count = 0
x = N
for a in A:
    if a[1] < x:
        x = a[0]
        count += 1


print(count)

Submission status: Wrong Answer

Solution code:
from sys import stdin, stdout
input = lambda: stdin.readline()
write = stdout.write

def main():
    N, M = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in [0] * M]

    AB.sort(key=lambda x: x[1])
    cuts, p = 1, AB[0][1]
    for a, b in AB:
        if a > p:
            cuts += 1
    print(cuts)

main()

Submission status: Wrong Answer

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

arr = [[] for i in range(n)]

for i in range(m):
	a, b = list(map(int, input().split()))
	bisect.insort_left(arr[a-1],b)

print(arr)
cnt = 0	
sting = n+1
for i,isl in enumerate(arr):
	if sting == i+1:
		cnt += 1
		sting = n+1

	if len(isl) == 0:
		continue
		
	if isl[0] < sting:
		sting = isl[0]
print(cnt)

Submission status: Wrong Answer

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

arr = [[] for i in range(n)]

for i in range(m):
	ab = input()
	a, b = ab.split()
	a = int(a)
	b = int(b)
	arr[a-1].append(b)	

cnt = 0	
sting = n+1
for i,isl in enumerate(arr):
	if sting == i+1:
		cnt += 1
		sting = n+1
	if len(isl) == 0:
		continue
		
	if isl[0] < sting:
		sting = isl[0]
print(cnt)

Submission status: Wrong Answer

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

starts = []
ends = []
for i in range(M):
    s,e = map(int,input().split())
    starts.append(s)
    ends.append(e)

starts = sorted(starts)
ends = sorted(ends)

ans = 0
temp = 0

p = 0
for i in range(M):
    while p < M and starts[p] <= ends[i]:
        temp += 1
        p += 1

    if temp != 0:
        ans += 1

    temp = 0

print(ans)

Submission status: Wrong Answer

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

starts = []
ends = []
for i in range(M):
    s,e = map(int,input().split())
    starts.append(s)
    ends.append(e)

starts = sorted(starts)
ends = sorted(ends)

ans = 0
temp = 0

p = 0
for i in range(M):
    while p < M and starts[p] < ends[i]:
        temp += 1
        p += 1

    if temp != 0:
        ans += 1

    temp = 0

print(ans)

Submission status: Wrong Answer

Solution code:
n , m = map(int, input().split())
l = [list(map(int,input().split())) for _ in range(m)]
l.sort()
l = l[::-1]
cnt = 1
key = l[0][0]
for i in range(m):
    if key > l[i][1]:
        cnt += 1
        key = l[i][0]
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)]
links = []
for i in range(M):
    a, b = ab[i]
    flag = True
    for j in range(len(links)):
        x, y = links[j]
        if a <= x and y <= b:
            flag = False
            break
        elif x < a and y <= b and a < y:
            links[j][0] = a
            flag = False
            break
        elif a <= x and b < y and x < b:
            links[j][1] = b
            flag = False
            break
        elif x < a and b < y:
            links[j][0] = a
            links[j][1] = b
            flag = False
            break
    if flag:
        links.append([a, b])
print(len(links))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ab = []
for i in range(m):
    ab.append(list(map(int, input().split())))
ab.sort(reverse = True)
print(ab)
bridge = [float("inf")]
for i in range(m):
    if ab[i][0] <= min(bridge) < ab[i][1]:
        continue
    else:
        bridge.append(ab[i][0])
print(len(bridge) - 1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import copy
tmp = input()
n = int(tmp.split(" ")[0])
m = int(tmp.split(" ")[1])

a=[]
b=[]
c=[]

for i in range(m):
    tmp=input()
    a.append(int(tmp.split(" ")[0])-1)
    b.append(int(tmp.split(" ")[1])-1)
    c.append(int(0))

d=copy.deepcopy(c)

x=int(0)
y=int(0)
z=int(0)
w=[]
for k in range(n-1):
    y=0
    c=copy.deepcopy(d)
    for j in range(k,n-1):
        x=0
        for i in range(m):
            if c[i]==0:
                if b[i]<=j:
                    z=1
                    break
                if a[i]<=j:
                    c[i]=1
                    x=1
        if z==1:
            break
        y=y+x
    if z==1:
        break
    elif y!=0:
        w.append(y)

print(min(w))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python

import sys
import math
import itertools as it
from collections import deque

sys.setrecursionlimit(10000000)

_, M = map(int, raw_input().split())
lst = []

for i in range(M):
    a, b = map(int, raw_input().split())
    lst.append((a, b))

lst.sort()
pos = 0
ans = 0

for p in lst:
    if p[0] > pos:
        ans += 1
        pos = p[1] - 1
    elif p[1] < pos:
        pos = p[1]

print ans

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jul 21 21:41:43 2018
ABC103D
@author: maezawa
"""

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

w = []
cnt = 1

for i in range(m):
    ai, bi = list(map(int, input().split()))
    ci = set(list(range(ai,bi)))
    w.append(ci)

w.sort()
#print(*w)
bsbroken = []
bs0 = w[0]    
for bs in w:
    bsand = bs0 & bs
    if len(bsand) == 0:
        flag = 0
        for seq in bsbroken:
            if len(seq & bs) != 0:
                flag = 1
                break
        if flag == 0:
            cnt += 1
            bsbroken.append(bs0)
            bs0 = bs
    else:
        bs0 = bsand
        
print(cnt)

Submission status: Wrong Answer

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

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

AB.sort(key=lambda x: x[1])
num = 0
p = 0
for i in AB:
    if i[0] > p:
        num += 1
        p = i[1]

print(num)

Submission status: Wrong Answer

Solution code:
N, M = map( int, input().split())
Q = [[int(s) for s in input().split()] for _ in range(M)]
Q = sorted(Q)
ans = 1
LQ = len(Q)
    
while LQ != 0:
    stan = Q[0][1]
    k = 1
    if Q[0][0] < stan:
        stan = min(stan,Q.pop(0)[1])
        LQ -= 1
    else:
        ans += 1
        break
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, raw_input().split(' '))
ab = []

for i in range(M):
    a, b = map(int, raw_input().split(' '))
    ab.append((a, b))

left = 0
right = N
k = 0
count = 0
for i in range(M):
    a, b = ab[i]

    if a <= k < b:
        continue

    if left < a:
        left = a

    if b < right:
        right = b

    if left >= right:
        k = left
        left = a
        right = b
        count += 1


print count + 1

Submission status: Wrong Answer

Solution code:
def main():
        run()

def run():
        n, m = input().split(" ")
        n = int(n)
        m = int(m)
        removed = False
        combs = [(1, n)]
        for _ in range(m):
                a, b = input().split(" ")
                a = int(a)
                b = int(b)
                if a > b:
                        temp = a
                        a = b
                        b = temp
                isNone = False
                if a == b:
                        continue
                removed = True
                for comb in combs:
                        min_, max_ = comb
                        if a < min_ and b > max_:
                                isNone = False
                                break
                        if min_ <= a and a < max_:
                                if max_ >= b and min_ < b: 
                                        combs.remove(comb)
                                        combs.append((a, b))
                                else:
                                        combs.remove(comb)
                                        combs.append((a, max_))
                                isNone = False
                                break


                        else:
                                if max_ >= b and min_ < b:
                                        combs.remove(comb)
                                        combs.append((min_, b))
                                        isNone = False
                                        break
                                else:
                                        isNone = True
                if isNone:
                        combs.append((a, b))
                if removed:
                        print(0)
                else:
                        print(len(combs))
if __name__ == "__main__":
        main()

Submission status: Wrong Answer

Solution code:
import bisect

N,M = [int(x) for x in input().split()]

l = [[int(x) for x in input().split()] for _ in range(M)]



def do(l):
    l1 = [v1 for (v1,_) in l]
    l2 = [v2 for (_,v2) in l]
    l1.sort()
    l2.sort()

    count = 1

    l.sort()

    h = 0
    
    for i in range(len(l)):
        nx = l2[h]
        if l[i][0] >= nx:
            count+=1
            h+=1
            while l2[h] != l2[h+1]:
                h+=1
                if h+1 >= len(l2):
                    return count
    return count




result = do(l)
print(result)

Submission status: Wrong Answer

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

Z = [N+1] * (N + 1)

Z = {}

for i in range(M):
    a, b = map(int, raw_input().split(' '))
    if a not in Z:
        Z[a] = b
    elif b < Z[a]:
        Z[a] = b

l = zip(Z.keys(), Z.values())
count = 0
for i in range(1, len(l)):
    if l[i][0] >= l[i-1][1]:
        count += 1


print count + 1

Submission status: Wrong Answer

Solution code:
import bisect

N,M = [int(x) for x in input().split()]

l = [[int(x) for x in input().split()] for _ in range(M)]



def do(l):
    l1 = [v1 for (v1,_) in l]
    l2 = [v2 for (_,v2) in l]
    l1.sort()
    l2.sort()

    l2 = list(set(l2))

    count = 1

    l.sort()

    h = 0
    
    for i in range(len(l)):
        nx = l2[h]
        if l[i][0] >= nx:
            count+=1
            h+=1
    return count




result = do(l)
print(result)

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

Ans = 0
l,r = 1,N
for ab in AB:
    a,b = ab
    if r <= a:
        Ans += 1
        l,r = a,b
    else:
        l = max(l,a)
        r = min(r,b)
    print(Ans)
#else:
Ans += 1

print(Ans)

Submission status: Wrong Answer

Solution code:
def main():
        run()

def run():
        n, m = input().split(" ")
        n = int(n)
        m = int(m)
        combs = [(1, n)]
        for _ in range(m):
                a, b = input().split(" ")
                a = int(a)
                b = int(b)
                if a > b:
                        temp = a
                        a = b
                        b = temp
                isNone = False
                if a == b:
                        continue
                for comb in combs:
                        min_, max_ = comb
                        if a < min_ and b > max_:
                                isNone = False
                                break
                        if min_ <= a and a < max_:
                                if max_ >= b and min_ < b: 
                                        combs.remove(comb)
                                        combs.append((a, b))
                                else:
                                        combs.remove(comb)
                                        combs.append((a, max_))
                                isNone = False
                                break


                        else:
                                if max_ >= b and min_ < b:
                                        combs.remove(comb)
                                        combs.append((min_, b))
                                        isNone = False
                                        break
                                else:
                                        isNone = True
                if isNone:
                        combs.append((a, b))
        print(len(combs))
if __name__ == "__main__":
        main()

Submission status: Wrong Answer

Solution code:
def drop(islinds,problems):
    a=set()
    i=0
    while len(a)<len(problems):
        a=a|islinds[i]
        i+=1
    new_islinds=islinds[:i]
    solved_problems=set()
    for s in islinds[i:]:
        solved_problems=solved_problems|s
    new_problems=problems.difference(solved_problems)
    return new_islinds,new_problems

N, M=map(int,input().split(' '))
islinds=[set()]*N
for i in range(1,M+1):
    a,b=map(int,input().split(' '))
    islinds[a-1].add(i)
    islinds[b-1].add(i)
problems=set(range(1,M+1))
count=0
while len(problems)>0:
    islinds,problems=drop(islinds,problems)
    count+=1
print(count)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(m)]
ab.sort()
cnt=0
while(len(ab)>1 and cnt<10):
    cnt+=1
    mini =min(ab, key=lambda x:x[1])[1]
    for i in range(len(ab)):
        if ab[i][0]>mini: break
    for j in range(i):
        del ab[0]
    if(len(ab)==1):cnt+=1
print(cnt)

Submission status: Wrong Answer

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

ab = []

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

ab_ = sorted(ab, key=lambda x: x[0])
ab = []
pre = 0

for i in range(len(ab_)-1):
    if ab_[i][0] != ab_[i+1][0]:
        ab.append(min(ab_[pre:i+1], key=lambda x: x[1]))
        pre = i+1

ab.append(min(ab_[pre:], key=lambda x: x[1]))

min_ = ab[0][1]
count = 0
for t in ab[1:]:
    if t[0] > min_:
        count += 1
        min_ = t[1]
    min_ = min(min_, t[1])

if ab[-1][0] < min_:
    count += 1

print(count)

Submission status: Wrong Answer

Solution code:
inp = input().split()
n = int(inp[0])
m = int(inp[1])
inp = [input() for _ in range(m)]
bridge = [0 for _ in range(n-1)]
dem = []
total = 0
for i in inp:
    dem.append(i.split())

for i in dem:
    a = bridge[int(i[0]):int(i[1])-1]
    for j, k in enumerate(a):
        a[j] += 1

bridge.reverse()
count = 0
for i in bridge:
    m -= i
    if m <= 0:
        break
    count += 1

print(count)

Submission status: Wrong Answer

Solution code:
def main():                                                                                                                                                                                                                                   
        run()                                                                                                                                                                                                                                 
                                                                                                                                                                                                                                              
def run():
        n, m = input().split(" ")
        n = int(n)
        m = int(m)
        combs = [(1, n)]
        for _ in range(m):
                a, b = input().split(" ")
                a = int(a)
                b = int(b)
                if a > b:
                        temp = a
                        a = b
                        b = temp
                isNone = False
                for comb in combs:
                        min_, max_ = comb
                        if a < min_ and b > max_:
                                isNone = False
                                break
                        if min_ <= a and a < max_:
                                if max_ >= b and min_ < b:
                                        combs.remove(comb)
                                        combs.append((a, b))
                                else:
                                        combs.remove(comb)
                                        combs.append((a, max_))
                                isNone = False
                                break


                        else:
                                if max_ >= b and min_ < b:
                                        combs.remove(comb)
                                        combs.append((min_, b))
                                        isNone = False
                                        break
                                else:
                                        isNone = True
                if isNone:
                        combs.append((a, b))
        print(len(combs))
if __name__ == "__main__":
        main()

Submission status: Wrong Answer

Solution code:
# your code goes here
import numpy as np
buf = input().split()
n = int(buf[0])
m = int(buf[1])

l = np.zeros((m, 2))
for i in range(m):
	buf = input().split()
	for j in range(2):
		l[i][j] = int(buf[j])
sum = 0
c1 = 0
c2 = 0
for i in range(m):
	b1 = l[i][0]
	b2 = l[i][1]
	if(b1 >= c2):
		sum += 1
		c1 = b1
		c2 = b2
	elif(b2 < c2):
		c2 = b2
	#print(c1, c2, sum)
print(sum)

Submission status: Wrong Answer

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

doubled = set()
s = set()

bridges = {}
conditions = {}
cs = set(range(M)) # conditionのセット
for i in range(M):
    a, b = map(int, input().split(" "))
    for j in range(a - 1, b -1):
        idx = "{}".format(j)
        bridges[idx] = bridges.get(idx, 0) + 1
        conditions.setdefault(idx, []).append(i)
bridges = sorted(bridges.items(), key=lambda x: x[1], reverse=True)

num_break = 0
for b, j in bridges:
    if len(cs) == 0:
        break
    flag = False
    for i in conditions[b]:
        if i in cs:
            flag = True
            cs.remove(i)
    if flag:
        num_break += 1

print(num_break)

Submission status: Wrong Answer

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

demand = []

for i in range(m):
    demand.append(list(map(int,input().split())))

cut = []

for d in demand:
    flag = True
    for c in cut:
        if c[0] < d[1] and c[1] > d[0]:
            flag = False
            c[0] = max(c[0],d[0])
            c[1] = min(c[1],d[1])
            break
    if flag:
        cut.append(d)

print(len(cut))

Submission status: Wrong Answer

Solution code:
from numpy import zeros, all
N, M = map(int, input().split())
points = []
for i in range(M):
    points.append(map(int, input().split()))
v = 10**6
count = 0
for ai, bi in points:
    if v <= ai:
        count += 1
        v = bi
    elif bi < v:
        v = bi
print(count + 1)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
ab = []
a = []
b = []
for tmp in range(M):
    ta, tb = map(int, input().split())
    ab.append([ta, tb])
    a.append(ta)
    b.append(tb)
a.sort()
b.sort()
# print(a)
# print(b)
count = 0
while True:
    amax = a[len(a)-1]
    if(amax > b[0]):
        # max = a[-1:]
        a = a[:-1]
        # min = b[-1:]
        # b = b[:-1]
        count += 1
    else:
        count += 1
        break
print(count)


# for i in range(N):
#     map.appen(i+1)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
a = []
b = []
for i in range(m):
	tmp = list(map(int, input().split()))
	a.append(tmp[0])
	b.append(tmp[1])
count = 0
i = 0
while len(a) != 0:
	now = a.pop(0)
	vs = b.pop(0)
	while now != vs:
		now += 1
		if now in a:
			vs = b.pop(a.index(now))
			a.remove(now)
	count += 1

print(count)