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

def cutset(A, B):
    return {i for i in range(A, B)}

def main(data):
    cut_list = [cutset(req[0], req[1]) for req in data]
    cut_cnt = Counter([i for req in cut_list for i in req])
    tmp = len(cut_list)
    ans = 0
    tmp_list = cut_list
    for idx in [k for k, v in sorted(cut_cnt.items(), key=lambda x: -x[1])]:
        h = len([1 for cs in tmp_list if idx in cs])
        if h > 0: ans += 1
        tmp -= h
        if tmp == 0:
            print(ans)
            exit()
        tmp_list = [cs for cs in tmp_list if not idx in cs]




if __name__ == '__main__':
    data = [list(map(int, line.strip().split(' '))) for line in sys.stdin]
    main(data[1:])

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().strip().split())
ablr = {}
ab = []
for _ in range(M):
  a, b = map(int, input().strip().split())
  ab.append((a, 'L'))
  ab.append((b, 'R'))
  if a in ablr:
    ablr[a].add('L')
  else:
    ablr[a] = set(['L'])
  if b in ablr:
    ablr[b].add('R')
  else:
    ablr[b] = set(['R'])

print(ablr)

prevlr = None
previ = None
c = 0
for abi, lr in sorted(ab, key=lambda x: x[0]):
  if previ is None:
    previ = abi
    prevlr = 'L'
  elif previ == abi:
    continue
  else:
    if len(ablr[abi]) == 2:
      if prevlr=='L':
        prevlr = 'L'
        previ = abi
        c += 1
      else:
        prevlr = 'L'
        previ = abi
    else:
      if list(ablr[abi])[0] == 'L':
        prevlr = 'L'
        previ = abi
      else:
        if prevlr == 'L':
          c += 1
        prevlr = 'R'
        previ = abi
print(c)

Submission status: Wrong Answer

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

ab = []
for _ in range(M):
  a, b = map(int, input().strip().split())
  ab.append((a, 'L'))
  ab.append((b, 'R'))

prevlr = None
c = 0
for abi, lr in sorted(ab, key=lambda x: x[0]):
  if lr == 'L':
    prevlr = 'L'
  elif lr == 'R':
    if prevlr == 'L':
      c += 1
    prevlr = 'R'
print(c)

Submission status: Wrong Answer

Solution code:
N, M = list(map(int, input().split()))
D = []
L = [0] * N
for i in range(M):
  D.append(list(map(int, input().split())))
D.sort(key = lambda x: x[1])

Ans = 0
Re = 0
for i in D:
  if Re < i[0]:
    Re = i[0]
    Ans += 1
print(Ans)

Submission status: Wrong Answer

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

D = [[0] * N for i in range(N)]
L = [0] * (N-1)
for i in range(M):
  a, b = list(map(int, input().split()))
  D[a-1] = D[a-1][:b-1] + [1]*(N-b+1)
  D[b-1] = D[b-1][a:] + [1]*a
  if 1 not in L[a-1:b-1]:
    L[a-1] = 1
    if 1 in L[:a-1]:
      if D[L[:a-1].index(1)][a-1] == 0:
        L[L[:a-1].index(1)] = 0

print(L.count(1))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
AB=[[0,0] for i in range(M)]
for i in range(M):
    AB[i][0],AB[i][1]=map(int,input().split())
l=AB[0][0]
r=AB[0][1]
c=0
x=0
for i in range(1,M):
    if AB[i][0]<r:
        l=AB[i][0]
        if AB[i][1]<r and x==0:
            r=AB[i][1]
            x=i
        elif AB[i][1]<r and i==x+1:
            c+=1
            l=AB[i][0]
            r=AB[i][1]
            x=0
            continue
    else:
        c+=1
        l=AB[i][0]
        r=AB[i][1]
print(c+1)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
AB=[[0,0] for i in range(M)]
for i in range(M):
    AB[i][0],AB[i][1]=map(int,input().split())
l=AB[0][0]
r=AB[0][1]
c=0
for i in range(1,M):
    if AB[i][0]<r:
        l=AB[i][0]
        if AB[i][1]<r:
            r=AB[i][1]
    else:
        c+=1
        l=AB[i][0]
        r=AB[i][1]
print(c-3)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
AB=[[0,0] for i in range(M)]
for i in range(M):
    AB[i][0],AB[i][1]=map(int,input().split())
l=AB[0][0]
r=AB[0][1]
c=0
for i in range(1,M):
    if AB[i][0]<r:
        l=AB[i][0]
        if AB[i][1]<r:
            r=AB[i][1]
    else:
        c+=1
        l=AB[i][0]
        r=AB[i][1]
print(c+1)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
AB=[[0,0] for i in range(M)]
for i in range(M):
    AB[i][0],AB[i][1]=map(int,input().split())
l=AB[0][0]
r=AB[0][1]
c=0
for i in range(1,M):
    if AB[i][0]<r:
        l=AB[i][0]
        if AB[i][1]<=r:
            r=AB[i][1]
    else:
        c+=1
        l=AB[i][0]
        r=AB[i][1]
print(c+1)

Submission status: Wrong Answer

Solution code:
import bisect
iipt=lambda:int(input())
miipt=lambda:list(map(int,input().split(" ")))
n, m=miipt()
a=[]
done=[0]*m
for i in range(m):
    a.append(miipt())
a=list(enumerate(a))
b=list(map(lambda x:(x[1][0],x[0]), sorted(a, key=lambda x:x[1])))
a.sort(key=lambda x:x[1][1])
c=0
d=-1
while d<m:
    j, (_, h) = a.pop(0)
    nd = bisect.bisect_left(b, (h,))
    if d<nd:
        c+=1
        d=nd


print(c)

Submission status: Wrong Answer

Solution code:
from operator import attrgetter


class Line:
    def __init__(self, a, b):
        self.a = a
        self.b = b


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

lines = sorted(lines, key=attrgetter("a"))

start_num = lines[0].a
min_num = 1000000
cnt = 0

for line in lines:
    if line.a != start_num:
        if min_num <= line.a:
            cnt += 1
        start_num = line.a
    if line.b < min_num:
        min_num = line.b
cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
a,b = map(int,input().split(" "))
ar = []
br = []
for i in range(b):
    c,d = map(int,input().split(" "))
    ar.append(c)
    br.append(d)
mb = (min(br))
count = 1
for r in set(ar):
    if mb <= r:
        count += 1
print(count)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
N, M = map(int, input().split())
abn = [list(map(int, input().split())) for _ in range(M)]

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

# 爆破した橋
ans = [0 for _ in range(N-1)]
# 爆破ポイントカウント
imosu = [0 for _ in range(N)]
for a,b in abn:
    #一つしか橋がない場合、確実に爆破
    if a+1 == b:
        ans[a-1] = 1

    imosu[a-1] += 1
    imosu[b-1] -= 1

#いもすカウント
bb_cnt = {i: 0 for i in range(N-1)}
tmpcnt = 0
for i in range(N-1):
    tmpcnt += imosu[i]
    bb_cnt[i] = tmpcnt

for a,b in abn:
    if sum(ans[a-1:b-1]) > 0:
        continue

    tmplist = [(k, v) for k, v in bb_cnt.items() if a <= k < b]
    tmplist.sort(key=lambda x: -x[1])
    max_key, max_val = tmplist[0]
    ans[max_key] = 1

print(sum(ans))

Submission status: Wrong Answer

Solution code:

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

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

print(count)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split(" "))
isbr = []
for i in range(M):
  isbr.append(list(map(int,input().split(" "))))
isbr = list(sorted(isbr,key = lambda x: x[1]))
rem = []
i = 0
while i < M:
  a = isbr[i][0]
  b = isbr[i][1]
  flag = 0
  while a < b:
    if b in rem:
      flag = 1
      break
    else:
      b-=1
  if flag == 0:
    rem.append(isbr[i][1]-1)
  i+=1
print(len(rem))

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    ranges = []
    for _ in range(M):
        a, b = map(int, input().split())
        updated = False
        for item in ranges:
            if a <= item[1] and item[0] <= b-1:
                item[0] = max(item[0], a)
                item[1] = min(item[1], b-1)
                updated = True
                break
        if not updated:
            ranges.append([a, b-1])
    print(len(ranges))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
connections = [[] for _ in range(n+1)]  

for _ in range(m):
    i,j = map(int,input().split())
    connections[i].append(j)

ans = 0
cnt = 1

while 1:
    if connections[cnt]:
        cnt = min(connections[cnt])
        ans += 1
    else:
        cnt += 1
        if cnt >= n:
            break

print(ans)

Submission status: Wrong Answer

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

claims = []
for i in range(M):
  claims.append(list(map(int,input().split())))
  
claims.sort()

killed = 0
last_killed = [-1,-1]
for claim in claims:
  if (last_killed[1] < claim[0] or last_killed[0] >= claim[1]):
    last_killed = [claim[0],claim[1] -1]
    killed += 1

print(killed)

Submission status: Wrong Answer

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

claims = []
for i in range(M):
  claims.append(list(map(int,input().split())))
  
claims.sort()

killed = 0
last_killed = -1
for claim in claims:
  if (not( claim[0] <= last_killed and last_killed < claim[1]) ):
    last_killed = claim[1] -1
    killed += 1

print(killed)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
AB=[]
for _ in range(M):
    AB.append(tuple(map(int,input().split())))
    
request_max=0
request_num=0

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

Submission status: Wrong Answer

Solution code:
def island(a, n):
    splits = []
    a = sorted(a, key=lambda e: e[1])
    for i in range(0, len(a)):
        aa = a[i]
        included = False
        target = range(aa[0] + 1, aa[1])
        for s in splits:
            if s in target:
                included = True
                break
        if included:
            continue
        splits += [aa[1]]
    return len(splits)

n, m = map(int, input().split())
a = []
for _ in range(m):
    aa, bb = map(int, input().split())
    a += [(aa, bb)]
print(island(a, n))

Submission status: Wrong Answer

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

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

lst.sort()
print lst
pos = 0
ans = 0

for p in lst:
    if p[1] >= pos:
        ans += 1
        pos = p[0]
print ans

Submission status: Wrong Answer

Solution code:
str = raw_input()
N, M = map(int, str.split())
x = []
counter = 0
min = 10**5
for i in range(M):
    str = raw_input()
    ai, bi = map(int, str.split())
    if bi < min:
        min = bi
        counter = 0
    if ai >= min:
        if ai not in x:
            counter += 1
            x.append(ai)
    # print i+1, "counter", counter, "min", min


print counter + 1

Submission status: Wrong Answer

Solution code:
str = raw_input()
N, M = map(int, str.split())
x = []
y = []
for i in range(int(M)):
    str = raw_input()
    ai, bi = map(int, str.split())
    if ai not in x:
        x.append(ai)
    if bi not in y:
        y.append(bi)
x.sort()
y.sort()
counter = 0
result = 1
state = 0
for a in x:
    if a >= y[counter]:
        counter += 1
        result += 1
        state = 1
print result

Submission status: Wrong Answer

Solution code:
str = raw_input()
N, M = map(int, str.split())
x = []
y = []
for i in range(int(M)):
    str = raw_input()
    ai, bi = map(int, str.split())
    if ai not in x:
        x.append(ai)
    if bi not in y:
        y.append(bi)
result = 1
counter = 0
state = 0
for a in x:
    if a >= y[counter]:
        counter += 1
        state = 1
if state == 0:
    result += 1


print result

Submission status: Wrong Answer

Solution code:
str = raw_input()
N, M = map(int, str.split())
x = []
y = []
for i in range(int(M)):
    str = raw_input()
    ai, bi = map(int, str.split())
    if ai not in x:
        x.append(ai)
    if bi not in y:
        y.append(bi)
count = 1
for a in y:
    if len(x) == 0:
        break
    for b in x:
        if b >= a:
            count += 1
            break

print count

Submission status: Wrong Answer

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

p=0
while m!=[]:
    tmp=max(m)[1]
    m=[l for l in m if l[0]<=tmp]
    p+=1
print(p)

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
m=[list(map(int, input().split())) for _ in range(M)]
m=sorted(m, key=lambda x: x[1])
p=0
while m!=[]:
    tmp=m[-1][1]-1
    while m!=[] and m[-1][1]>tmp:
        m.pop()
    p+=1
print(p)

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
m=[list(map(int, input().split())) for _ in range(M)]
m=sorted(m, key=lambda x: x[1])
p=0
while m!=[]:
    a_tmp=m[-1][0]
    while m!=[] and m[-1][1]>a_tmp:
        m.pop()
    p+=1
print(p)

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
m=[list(map(int, input().split())) for _ in range(M)]
a=list(list(zip(*m))[0])
b=list(list(zip(*m))[1])
a.sort()
b.sort()
p=0
while b!=[] and a!=[]:
    while b!=[] and b[-1]>=a[-1]:
        b.pop()
    a.pop()
    p+=1
print(p)

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
m=[list(map(int, input().split())) for _ in range(M)]
a=list(list(zip(*m))[0])
b=list(list(zip(*m))[1])
a.sort()
p=1
while 1:
    if max(a)>=min(b):
        tmp_max=max(a)
        while a[-1]==tmp_max:
            a.pop()
        p+=1
    else:
        print(p)
        break

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
m=[list(map(int, input().split())) for _ in range(M)]
a=list(list(zip(*m))[0])
b=list(list(zip(*m))[1])
p=1
while 1:
    if max(a)>=min(b):
        a.sort()
        tmp_max=max(a)
        while a[-1]==tmp_max:
            a.pop()
        p+=1
    else:
        print(p)
        break

Submission status: Wrong Answer

Solution code:
islands = []
bridges = []

N, M = map(int, input().split())
# N, M = 10, 5
# islands = [
#     {'a': 1, 'b': 10},
#     {'a': 2, 'b': 5},
#     {'a': 1, 'b': 9},
#     {'a': 2, 'b': 4},
#     {'a': 1, 'b': 2},
# ]

for i in range(M):
    a, b = map(int, input().split())
    islands.append({'a': a, 'b': b})

islands.sort(key=lambda x: (x['a'], x['b']))
# print(islands)

for i in islands:
    b = [j for j in bridges if j >= i['a']]
    b = [j for j in b if j < i['b']]
    if len(b) == 0:
        bridges.append(i['b'] - 1)

# print(bridges)
print(len(bridges))

Submission status: Wrong Answer

Solution code:
islands = []
bridges = []

N, M = map(int, input().split())
# N, M = 10, 5
# islands = [
#     {'a': 1, 'b': 10},
#     {'a': 2, 'b': 5},
#     {'a': 1, 'b': 9},
#     {'a': 2, 'b': 4},
#     {'a': 1, 'b': 2},
# ]

for i in range(M):
    a, b = map(int, input().split())
    islands.append({'a': a, 'b': b})

islands.sort(key=lambda x: (x['a'], x['b']))
# print(islands)

for i in islands:
    b = [j for j in bridges if j >= i['a']]
    b = [j for j in b if j < i['b']]
    if len(b) == 0:
        bridges.append(i['b'] - 1)

print(bridges)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
A = []
B = []
count = 1
for i in range(m):
  a,b = map(int,input().split())
  A.append(a)
  B.append(b)

A = sorted(A)
B = sorted(B)
i = 1

for i in A:
  if i > B[0]:
    count += 1
print(count)

Submission status: Wrong Answer

Solution code:
def m():
    n, m = map(int, input().split())
    bridge = [1 for _ in range(n)]
    g = []
    for _ in range(m):
        a, b = map(int, input().split())
        g.append((a, b))
    g.sort(key=lambda x: x[1])
    cnt = 0
    for e in g:
        f = 0
        for j in range(e[0], e[1]):
            if j == 0:
                f = 1
                break
        if f:
            continue
        # if bridge[e[0]:e[1]].count(0):
        #     continue
        bridge[e[1]-1] = 0
        cnt += 1
    return cnt

print(m())

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

Solution code:
il = lambda: list(map(int, input().split()))
ils = lambda n, s="int(input())": [eval(s) for _ in range(n)]

n, m = il()
l = ils(m, "il()")
cut_range = [l[0]]
flag = 0
for i in l[1:]:
    for j, elem in enumerate(cut_range):
        flag = 0
        if not(i[1] <= elem[0] or elem[1] <= i[0]):
            cut_range[j] = [max(i[0], elem[0]), min(i[1], elem[1])]
            flag += 1
    if flag == 0:
        cut_range.append(i)
print(len(cut_range))

Submission status: Wrong Answer

Solution code:
def main():
	n, m = list(map(int, input().split()))
	rqs = [list(map(int, input().split())) for _ in range(m)]

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

	cnt = 0
	while len(rqs) > 1:
		min_b = min([x[1] for x in rqs[1:]])
		rqs = [x for x in rqs[1:] if x[1] > min_b]
		#print(rqs)
		cnt += 1

	if rqs == 1:
		cnt += 1

	print(cnt)

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
# encoding: utf-8
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(M)]

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

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

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

# # find minimum a -> find minimum b (> a) -> find minimum a (> =b) -> ...
# state = 1
# ans = 0
# for a_exist, b_exist in zip(a_exists, b_exists):
#     print("#", state, ans,  a_exist, b_exist)
#     # search minimum b
#     if state == 1 and b_exist:
#         ans += 1
#         state = 0
#     # search minimum a (can occur immediately after state = 0)
#     if state == 0 and a_exist:
#         state = 1

print(ans)

Submission status: Wrong Answer

Solution code:
# encoding: utf-8
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(M)]

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

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

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

# # find minimum a -> find minimum b (> a) -> find minimum a (> =b) -> ...
# state = 1
# ans = 0
# for a_exist, b_exist in zip(a_exists, b_exists):
#     print("#", state, ans,  a_exist, b_exist)
#     # search minimum b
#     if state == 1 and b_exist:
#         ans += 1
#         state = 0
#     # search minimum a (can occur immediately after state = 0)
#     if state == 0 and a_exist:
#         state = 1



print(ans)

Submission status: Wrong Answer

Solution code:
# encoding: utf-8
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(M)]

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

# find minimum a -> find minimum b (> a) -> find minimum a (> =b) -> ...
state = 1
ans = 0
for a_exist, b_exist in zip(a_exists, b_exists):
    # print(state, ans,  a_exist, b_exist)
    # search minimum b
    if state == 1 and b_exist:
        ans += 1
        state = 0
    # search minimum a (can occur immediately after state = 0)
    if state == 0 and a_exist:
        state = 1

print(ans)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# encoding: utf-8
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(M)]

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

# find minimum a -> find minimum b (> a) -> find minimum a (> =b) -> ...
state = 0
ans = 0
for a_exist, b_exist in zip(a_exists, b_exists):
    # print(state, ans,  a_exist, b_exist)
    # search minimum b
    if state == 1 and b_exist:
        ans += 1
        state = 0
    # search minimum a (can occur immediately after state = 0)
    if state == 0 and a_exist:
        state = 1

print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    # Input
    [N, M] = list(map(int, input().rstrip().split(" ")))
    a, b = [], []
    for i in range(M):
        [_a, _b] = list(map(int, input().rstrip().split(" ")))
        a.append(_a)
        b.append(_b)
    output = solve(N, M, a, b)
    print(output)

def solve(N, M, a, b):
    # 切断したい橋の候補をbit値で表す
    bool_list = []
    for i in range(M):
        val1 = 0b0
        if a[i] == 1:
            val1 = 0b1
        else:
            val1 = val1 << (a[i]-2)
        val2 = b[i] - a[i]

        # (val2)bitの1を加える
        val1 = val1 << val2
        val1 = val1 | (2**val2-1)

        val3 = N - b[i]
        val1 = val1 << val3

        bool_list.append(val1)


    S = [bool_list]
    counter = 0
    while S:
        C1 = S.pop()
        C2 = []
        l1 = C1.pop(0)
        for l2 in C1:
            l3 = l1 & l2
            if l3 == 0:
                # 積が「すべてFalseになった場合」は別のループを回す
                C2.append(l2)
            else:
                l1 = l3
        if C2:
            # 別のループを回すためにSにpush
            S.append(C2)
        counter += 1
    return counter

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    # Input
    [N, M] = list(map(int, input().rstrip().split(" ")))
    a, b = [], []
    for i in range(M):
        [_a, _b] = list(map(int, input().rstrip().split(" ")))
        a.append(_a)
        b.append(_b)
    output = solve(N, M, a, b)
    print(output)

def solve(N, M, a, b):
    # 切断したい橋の候補をboolean値で表す
    bool_list = []
    for i in range(M):
        bool_list.append([True if (a[i] <= j+1) and (j+1 < b[i]) else False for j in range(N-1) ])

    S = [bool_list]
    counter = 0
    while S:
        C1 = S.pop()
        C2 = []
        l1 = C1.pop(0)
        for l2 in C1:
            l3 = l1 and l2
            l3 = [l1[i] and l2[i] for i in range(len(l1))]
            if sum(l3) == 0:
                # 積が「すべてFalseになった場合」は別のループを回す
                C2.append(l2)
            else:
                l1 = l3
        if C2:
            # 別のループを回すためにSにpush
            S.append(C2)
        counter += 1
    return counter

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
def main():
    # Input
    [N, M] = list(map(int, input().rstrip().split(" ")))
    a, b = [], []
    for i in range(M):
        [_a, _b] = list(map(int, input().rstrip().split(" ")))
        a.append(_a)
        b.append(_b)
    output = solve(N, M, a, b)
    print(output)

def solve(N, M, a, b):
    # 切断したい橋の候補をboolean値で表す
    bool_list = []
    for i in range(M):
        bool_list.append([True if (a[i] <= j+1) and (j+1 < b[i]) else False for j in range(N) ])

    S = [bool_list]
    counter = 0
    while S:
        C1 = S.pop()
        C2 = []
        l1 = C1.pop(0)
        for l2 in C1:
            l3 = l1 and l2
            l3 = [l1[i] and l2[i] for i in range(len(l1))]
            if sum(l3) == 0:
                # 積が「すべてFalseになった場合」は別のループを回す
                C2.append(l2)
            else:
                l1 = l3
        if C2:
            # 別のループを回すためにSにpush
            S.append(C2)
        counter += 1
    return counter

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
req = [list(map(int, input().split())) for i in range(M)]
req.sort
ans = 0
left = 0
right = 0
for i in range(M):
    if req[i][0] >= right:
        ans += 1
        left, right = req[i][0], req[i][1]
    else:
        left = req[i][0]
        right = min(req[i][1], right)

print(ans)

Submission status: Wrong Answer

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

ans = 0
left = 0
right = 0

for i in range(M):
    if req[i][0] >= right:
        ans += 1
        left, right = req[i][0], req[i][1]
    else:
        left = req[i][0]
        right = min(req[i][1], right)

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
N, M = map(int, input().split())
a0, b0 = map(int, input().split())
A = [a0]
B = [b0]

for _ in range(M - 1):
    x, y = map(int, input().split())
    i = bisect.bisect_left(A, x)
    if i == len(A):
        if x >= B[-1]:
            A.append(x)
            B.append(y)
        else:
            A[-1] = x
            B[-1] = min(B[-1], y)
    elif y <= A[i]:
        A.insert(i, x)
        B.insert(i, y)
    else:
        B[i] = min(B[i], y)
print(len(A))

Submission status: Wrong Answer

Solution code:
import numpy as np

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

D = []
dic = dict()

for m in range(M):
    a, b = map(int, input().split())
    D.append((b, a))
    if b in dic.keys() and (dic[b] > a):
        continue
    else:
        dic[b-1] = a-1
    
# print(dic)

dp = np.zeros(N, dtype=int)

dp[0] = 0
for i in range(1, N):
    dp[i] = dp[i-1]
    if i in dic.keys():
        a = dic[i]
        if dp[a] == dp[i]:
            dp[i] = dp[i] + 1
            continue

# print(dp)
print(dp[N-1])

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
cnt = 0
end_time = 0
for _ in range(m):
  a,b = map(int, input().split())
  if end_time <= a:
    end_time = b
    cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-
n, m = map(int, input().split())
d = []
for i in range(m):
    a, b = map(int, input().split())
    d.append([a, b])

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

mn = 100000000
ans = 0
for a, b in d:
    if a >= mn:
        ans += 1
        mn = b
    mn = min(mn, b)

if mn != 100000000:
    ans += 1
print(ans)

print(ans + 1)

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-
n, m = map(int, input().split())
d = []
for i in range(m):
    a, b = map(int, input().split())
    d.append([a, b])

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

mn = 100000000
ans = 0
for a, b in d:
    if a >= mn:
        ans += 1
        mn = b
    mn = min(mn, b)

if mn != 100000000:
    ans += 1
print(ans)

print(ans + 1)

Submission status: Wrong Answer

Solution code:
# -*- coding:utf-8 -*-
n, m = map(int, input().split())
d = []
for i in range(m):
    a, b = map(int, input().split())
    d.append([a, b])

mn = 100000000
ans = 0
for a, b in d:
    if a >= mn:
        ans += 1
        mn = 100000000
    mn = min(mn, b)

if mn != 100000000:
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = map(int, input().split())
AB = np.zeros([M, 2])
for i in range(M):
    AB[i, 0], AB[i, 1] = map(int, input().split())

AB = AB[np.argsort(AB[:, 1])]

cut_br = [AB[0, 1]-1]
for i in range(1, M):
    flag = False
    if AB[i, 0] <= cut_br[-1]:
        if cut_br[-1] < AB[i, 1]:
            flag = True
    if flag:
        cut_br.append(AB[i, 1]-1)
    break
print(len(cut_br))

Submission status: Wrong Answer

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

print(l)

p_num = -1
ans = 0

for i in range(M):
	if not l[i][0] <= p_num:
		p_num = l[i][1] - 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)]
sorted(l, key = lambda l:l[1])

p_num = -1
ans = 0

for i in range(M):
	if l[i][0] > p_num:
		p_num = l[i][1] - 1
		ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
hops = dict()
N, M = map(int, input().split())
for i in range(M):
    a, b = map(int, input().split())
    if a > b:
        a, b = b, a
    hop = hops.get(b-a)
    if not hop:
        hops[b-a] = hop = set()
    hop.add((a, b))

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

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


answer = len(covered)
print(answer)