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:
def F(X, Y):
    if X[0] > X[1]:
        X[0], X[1] = X[1], X[0]
    if Y[0] > Y[1]:
        Y[0], Y[1] = Y[1], Y[0]
    A = set(range(X[0], X[1] + 1))
    B = set(range(Y[0], Y[1] + 1))
    if len(A & B) != 0:
        return [[max(X[0], Y[0]), min(X[1], Y[1])]]
    else:
        return [X, Y]


n, m = map(int, input(). split())
L1 = list()
for i in range(m):
    p, q = map(int, input().split())
    if p > q:
        p, q = q, p
    L1.append([p, q])
L1 = sorted(L1, key=lambda x: x[0])
L2 = [L1[0]]
del L1[0]
for v in L1:
    B = F(v, L2[-1])
    del L2[-1]
    L2 += B
print(len(L2))

Submission status: Wrong Answer

Solution code:
N, M = list(map(int,input().split()))
a = []
for i in range(M):
    a.append(list(map(int,input().split())))
a = sorted(a, key=lambda x: x[1])
left = -1
ans = 0
for i in range(M):
        if left <= a[i][0]:
            left = a[i][1] - 1
            ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
L = list()
for i in range(m):
    a, b = map(int, input().split())
    if a > b:
        a, b = b, a
    L.append([a, b])
i = 0
while len(L) > 0:
    i += 1
    L = [l for l in L if l[0] > min([L[i][1] for i in range(len(L))])]
print(i)

Submission status: Wrong Answer

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

ans = 1
stock = need[0][1]
for i in range(m):
  if stock <= need[i][0]:
    ans += 1
    stock = need[i][1]
    
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
bridges = [set(range(*map(int, input().split())))]
for _ in range(m - 1):
    a, b = map(int, input().split())
    for i in range(len(bridges)):
        if bridges[i] & set(range(a, b)):
            bridges[i] &= set(range(a, b))
            break
    else:
        bridges.append(set(range(a, b)))
print(len(bridges))

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter
sys.setrecursionlimit(1000000) # 再帰上限を増やす

def main():
    input = sys.stdin.readline  # 文字列に対してinputした場合は、rstripするのを忘れずに！
    N, M = map(int, input().rstrip().split())

    require_list = []
    for _ in range(M):
        s, e = map(int, input().rstrip().split())
        require_list.append([s, e])
    require_list.sort(key=itemgetter(1))
    print(require_list)

    count = 1
    now_require = require_list[0]
    for next_require in require_list[1:]:
        # 前回の終点よりも、今回の始点の方が右にある場合
        if now_require[1] <= next_require[0]:
            count += 1
        else:
            next_require[1] = now_require[1]
        now_require = next_require

    print(count)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
#s=input().rstrip()
n,m=MI()
lis=[]
for i in range(m):
    lis.append(LI())
lis.sort(key=lambda x:x[1])
print(lis)
bri=0
count=0
for i in range(m):
    if bri<=lis[i][0]:
        bri=lis[i][1]
        count+=1
        
print(count)

Submission status: Wrong Answer

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

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


B=sorted(B)
now=-1
pre=1
ans=0
for i in range(M):
    
    left,right=B[i]
    if i==0:
        now=left
        pre=right
        continue
    if i==M-1:
        ans+=1
    if now!=left and pre<=left:
        now=left
        ans+=1
        pre=right
    elif now!=left and pre>left:
        pre=min(pre,right)
        continue
    elif now==left:
        pre=min(pre,right)
    

print(ans)
#print(B)

Submission status: Wrong Answer

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

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
from copy import copy, deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, m = mi()
    edge = set()
    for _ in range(m):
        a, b = mi_0()
        edge.add((a, b - 1))
    
    cnt = 0
    while edge:
        accum = [0] * n
        for start, end in edge:
            accum[start] += 1
            accum[end + 1] -= 1
        prev = 0
        covered_edge_max = 0    # 現時点で残されているインターバルについて最もかぶっているようなポイントを探す。その被っているインターバルの個数
        point_x = 0    # そのポイントの座標
        for i in range(n):
            accum[i] += prev
            prev = accum[i]
            if accum[i] > covered_edge_max:
                covered_edge_max = accum[i]
                point_x = i
        # print(accum)
        cnt += 1
        tmp = copy(edge)
        for elm in edge:
            start, end = elm
            if start <= point_x <= end:
                tmp.remove(elm)
        edge = tmp
        # print(edge)
    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from pprint import pprint

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

# war_arrayの要素が1のところが、取り除く対象に含まれる可能性のある橋
war_array = [[0] * (n-1) for _ in range(m)]

for i in range(m):
    a, b = map(int, input().split())
    war_array[i][a-1:b-1] =  [1] * (b-a)

sum_candidates = [0] * (n-1)
for i in range(m):
    for j in range(n-1):
        sum_candidates[j] += war_array[i][j]

# インデックス付きソート
indicies = list(range(len(sum_candidates)))
sorted_indicies = sorted(indicies, key=lambda i: -sum_candidates[i])
sorted_sum_candidates = [sum_candidates[i] for i in sorted_indicies]

solved = [False] * m
cnt = 0

for i in sorted_indicies:
    breaked = False
    for j in range(m):
        if solved[j] == True:
            continue
        if war_array[j][i] == 1:
            solved[j] = True
            breaked = True
    if breaked:
        cnt += 1
    if all(solved):
        pprint(cnt)
        exit()

Submission status: Wrong Answer

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

import numpy
from collections import defaultdict

def main():
  n, m = map(int, input().split())
  db2a = defaultdict(list)
  for _ in range(m):
    a, b = map(int, input().split())
    db2a[b-1].append(a-1)
    
  cnts = numpy.zeros(n, dtype=numpy.int)
  i = 0
  for b in sorted(db2a.keys()):
    cnts[i:b] = cnts[i-1]
    cnts[b] = cnts[max(db2a[b])] + 1
    i = b + 1
  cnts[i:] = cnts[i-1]
  print(cnts[-1])

if __name__=='__main__':
  main()

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    y = []
    for i in range(M):
        y.append(list(map(int, input().split())))
    youbou = sorted(y, key = lambda x:x[1])
    
    cnt = 1
    k = 0
    for i in range(1, M):
        if(youbou[i][0] >= k):
            cnt += 1
            k = youbou[i][1]
    print(cnt)
main()

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    y = []
    for i in range(M):
        y.append(list(map(int, input().split())))
    youbou = sorted(y, key = lambda x:x[1])
    
    cnt = 1
    k = youbou[0][1]-1
    for i in range(1, M):
        if(youbou[i][0] > k):
            cnt += 1
            k = youbou[i][0]
    print(cnt)
main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    AB = [[int(i) for i in input().split()] for j in range(M)]
    AB.sort(key=lambda p: p[1] - p[0])
    rm = [(AB[0][1]-1, AB[0][1])]
    for a, b in AB[1:]:
        for rl, rr in rm[::-1]:
            if a <= rl and rr <= b:
                break
        else:
            rm.append((b-1, b))
    print(len(rm))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
from collections import deque
def main():
    n, m = MII()
    dq = deque([(0,n+1)])
    for i in range(m):
        a,b = MII()
        d = dq[0]
        if d[0]<a and b<d[1]:
            dq.pop()
            dq.append((a,b))
        elif d[1]<a or b<d[0]:
            dq.append((a,b))
    print(len(dq))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
##### ABC103-D-Islands War
n,m = map(int,input().split())
l = [list(map(int,input().split())) for _ in range(m)]

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

#c -> 区切り
c = 0

ans = 0

for a,b in l:
    if a >= c:
        c = b
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
Alist = []
for i in range(M):
    array = list(map(int, input().strip().split()))
    Alist.append(array)
Alist.sort()
q = 0
p = [Alist[0][0],Alist[0][1]]
for i in range(len(Alist)-1):
    if Alist[i][0] < Alist[i+1][0]:
        p[0] = Alist[i+1][0]
    if p[0] >= p[1]:
        q = q+1
        p = [Alist[i+1][0],Alist[i+1][1]]
    if Alist[i][1] > Alist[i+1][1]:
        p[1] = Alist[i+1][1]
print(q+1)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
Alist = []
for i in range(M):
    array = list(map(int, input().strip().split()))
    Alist.append(array)
Alist.sort()
q = 0
p = [Alist[0][0],Alist[0][1]]
for i in range(len(Alist)-1):
    print(p)
    if Alist[i][0] < Alist[i+1][0]:
        p[0] = Alist[i+1][0]
    if p[0] >= p[1]:
        print(q)
        q = q+1
        p = [Alist[i+1][0],Alist[i+1][1]]
    if Alist[i][1] > Alist[i+1][1]:
        p[1] = Alist[i+1][1]
print(q+1)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

b = np.array(b)
idx = np.argsort(b)
a=np.array(a)
a=a[idx]

n=1
r = a[0][1]
for i in range(M):
  if r <= a[i][0]:
    n+=1
    r=a[i][0]

print(n)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
X=[]
for i in range(m):
    a,b=map(int,input().split())
    X.append([a,b,b-a])
    
X.sort(key=lambda x:(x[2],x[0]))
M=[0]*(n+1)
cnt=0
s=set()
for i in range(m):
    if s.isdisjoint(set([k for k in range(X[i][0],X[i][1])])):
        for j in range(X[i][0],X[i][1]):
            M[j]=1
            s.add(j)
        cnt+=1
print(cnt)

Submission status: Wrong Answer

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

n, m = [int(x) for x in input().split()]

islands = [set() for _ in range(n + 1)]

for _ in range(m):
    ab = [int(x) for x in input().split()]
    islands[min(ab)].add(max(ab))

ans = 0

for i in range(1, n):
    if i + 1 in islands[i]:
        ans += 1
    else:
        for j in islands[i]:
            islands[j - 1].add(j)

ans += len(islands[n])

print(ans)

Submission status: Wrong Answer

Solution code:
import heapq,sys
from collections import defaultdict
N,M=map(int,input().split())
b=defaultdict(list)
h=[]
for i in range(M):
  x,y=map(int,input().split())
  heapq.heappush(h,(x,y))
while h:
  x,y=heapq.heappop(h)
  b[x].append(y)
cnt=0
prev=-1
l,r=-1,-1
for x in b.keys():
  y=min(b[x])
  if l==r==-1:
    l,r=x,y
    cnt+=1
  else:
    if l<x<r:
      pass
    else:
      cnt+=1
    l,r=x,y
print(cnt)

Submission status: Wrong Answer

Solution code:
import heapq,sys
from collections import defaultdict
N,M=map(int,input().split())
b=defaultdict(list)
h=[]
for i in range(M):
  x,y=map(int,input().split())
  heapq.heappush(h,(x,y))
while h:
  x,y=heapq.heappop(h)
  b[x].append(y)
cnt=0
prev=-1
for x in b.keys():
  nxt=min(b[x])
  if prev<=x:
    cnt+=1
  prev=nxt
print(cnt)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

def overlapped(a, b, p, q):
    #return p <=b and a <= q
    return p <b and a < q


N, M = map(int, input().split())
AB = []
for _ in range(M):
    AB.append(list(map(int, input().split())))
AB.sort(key=itemgetter(0,1))
# print(AB)
ans = 0

a, b = AB[0]
for i in range(1, M):
    p, q = AB[i]
    if overlapped(a, b, p, q):
        pass
    else:
        ans += 1
        a, b = p, q
ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

def overlapped(a, b, p, q):
    #return p <=b and a <= q
    return p <b and a < q


N, M = map(int, input().split())
AB = []
for _ in range(M):
    AB.append(list(map(int, input().split())))
AB.sort(key=itemgetter(0,1))
print(AB)
ans = 0

a, b = AB[0]
for i in range(1, M):
    p, q = AB[i]
    if overlapped(a, b, p, q):
        pass
    else:
        ans += 1
        a, b = p, q
ans += 1

print(ans)

Submission status: Wrong Answer

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

from operator import itemgetter
st = sorted(ab, key=itemgetter(1))
last = 0
ans = 0
for s, t in st:
    #print(x, l)
    if s > last:
        ans += 1
        last = t
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
ts = [list(map(int,input().split()))[::-1] for j in range(m)]


count = 0
t = 0

for j in range(m):
  if ts[j][1]>=t:
    count+=1
    t = ts[j][0]
    
print(count)

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 = sorted(ab, key=lambda x: x[1])
mn = ab[0][1]
c = 1
for i in ab:
	if i[0] > mn:
		c += 1
		mn = i[1]
print (c)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
c = []
mn = 0
mx = 10**5+1
for i in range(m):
	a, b = map(int, input().split())
	if len(c) == 0:
		c.append([a,b])
	if a > mx or b < mn:
		c.append([a,b])
	mn = max(a,mn)
	mx = min(b,mx)
print (len(c))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
bridge = [0] * (n - 1)
war = [[0] * 2 for i in range(m)]
for i in range(m):
    a, b = map(int, input().split())
    for j in range(a - 1, b - 1):
        bridge[j] += 1
    war[i] = [a -1, b - 1]
ans = 0
cnt = 0

while cnt < m:
    p = max(bridge)
    q = bridge.index(p)
    bridge[q] = 0
    tmp = []
    flag = 0
    for i, j in enumerate(war):
        if q in range(j[0], j[1]):
            tmp.append(i)
            war[i] = [0, 0]
            cnt += 1
            flag = 1
    if flag == 1:
        ans += 1
    
print(ans)

Submission status: Wrong Answer

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

count = 1
b_prev = AB[0][1]
for a, b in AB[1:]:
    if b_prev < b:
        count += 1
        b_prev = b

print(count)

Submission status: Wrong Answer

Solution code:

Submission status: Wrong Answer

Solution code:
n , m = map(int, input().split())
# ab = [list(map(int, input().split())) for _ in range(m)]
ranges = [[] for _ in range(m)]
for i in range(m):
    a,b = map(int,input().split())
    ranges[i] = [a,b]
ranges = sorted(ranges, key = lambda x:x[1])
MAX = - float("inf")
ans = 0#１つめはノーカン
for i in range(m):
    if MAX < ranges[i][0]:
        MAX = ranges[i][0] - 0.1
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n , m = map(int, input().split())
# ab = [list(map(int, input().split())) for _ in range(m)]
ranges = [[] for _ in range(m)]
for i in range(m):
    a,b = map(int,input().split())
    ranges[i] = [a,b]
ranges = sorted(ranges, key = lambda x:x[1])
MAX = - float("inf")
ans = 0#１つめはノーカン
for i in range(m):
    if MAX < ranges[i][0]:
        MAX = ranges[i][0]
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = [int(x) for x in input().split()]
li = []
for _ in range(m):
    li.append([int(x) for x in input().split()])
z = sorted(li,key=lambda x:x[1])
ans = 0
res = 0.5
for i in z:
    if res < i[0]:
        ans += 1
        res += i[1]-1
print(ans)

Submission status: Wrong Answer

Solution code:
N,MM=map(int,input().split())
ab=[]
for _ in range(MM):
    ab.append(list(map(int,input().split())))
ab.sort()
ans=0
st=0
m=ab[st][0]
M=ab[st][1]
while True:
    m=max(m,ab[st][0]);M=min(ab[st][1],M)
    if M<=m:
        ans+=1
        st-=1
        M=ab[st][1]
        m=ab[st][0]
        st+=1
    st+=1
    if st==MM:
        ans+=1
        break
print(ans)

Submission status: Wrong Answer

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

point=10**5+1
ans=0
for a,b in AB:
    if b<point:
        point=b
    elif a>=point:
        ans +=1
        point=b
print(ans+1)

Submission status: Wrong Answer

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

set={(i,i+1) for i in range(a[0],b[0])}
bomb=1
for i in range(1,M):
    testset={(i,i+1) for i in range(a[i],b[i])}
    if len(testset.intersection(set))>=1:
        set=testset.intersection(set)
    else:
        bomb+=1
        set=set.union(testset)
print(bomb)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
ab = []
for _ in range(m):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])
ab = sorted(ab, key=lambda x: x[1])
print(ab)
count = 1
memo = ab[0][1]
for i in range(m):
    if i == 0:
        continue
    if memo <= ab[i][0]:
        count += 1
        memo = ab[i][1]
print(count)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
ab=[]
for m in range(M):
  [a,b]=[int(i) for i in input().split()]
  ab.append([a,b])
ab.sort(key=lambda x:x[1])
count=[]
bmin=ab[0][1]
count.append(ab[0][1]-1)
for i in range(1,M):
  if ab[i][1]==b:
    count.remove(count[0])
    count.append(ab[i][1])
  else:
    pass
for i in range(1,M):
  if ab[i][0]<=count[-1]<ab[i][1]:
    pass
  else:
    count.append(ab[i][1])
print(len(count))

Submission status: Wrong Answer

Solution code:
import sys
sin = sys.stdin.readline
N, M = map(int, sin().split())
bs = [tuple(map(int, sin().split())) for _ in range(M)]
bs.sort(key=lambda x: x[1] - x[0])

r = []
for a, b in bs:
    for i in range(len(r)):
        a2, b2 = r[i]
        if a < b2 and a2 < b:
            if a2 < a:
                r[i][0] = a
            if b < b2:
                r[i][1] = b
            break
    else:
        r.append([a, b])
ans = len(r)
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
sin = sys.stdin.readline
N, M = map(int, sin().split())
r = []
for _ in range(M):
    a, b = map(int, sin().split())
    for i in range(len(r)):
        a2, b2 = r[i]
        if a < b2 and a2 < b:
            if a2 < a:
                r[i][0] = a
            if b < b2:
                r[i][1] = b
            break
    else:
        r.append([a, b])
ans = len(r)
print(ans)

Submission status: Wrong Answer

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

set={i for i in range(a[0],b[0]+1)}
bomb=1
for i in range(1,M):
    testset={i for i in range(a[i],b[i]+1)}
    if len(testset.intersection(set))>=2:
        set=testset.intersection(set)
    else:
        bomb+=1
        set=set.union(testset)
print(bomb)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
cut = []
for _ in range(m):
  a,b = map(int,input().split())
  cut.append((a,b))
cut.sort(key = lambda x:x[1])

ex_b  = cut[0][1]
count = 0
for a,b in cut[1:]:
  if a > ex_b:
    count += 1
    ex_b = b
print(count+1)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
cut = []
for _ in range(m):
  a,b = map(int,input().split())
  cut.append((a,b))
cut.sort(key = lambda x:x[1])

ex_b  = cut[0][1]
count = 0
flag = 0
for a,b in cut:
  if not flag:
    ex_b = b
    flag = 1
  if a > ex_b:
    count += 1
    flag = 0
print(count+1)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
cut = []
for _ in range(m):
  a,b = map(int,input().split())
  cut.append((a,b))
cut.sort(key = lambda x:x[1])

ex_b  = cut[0][1]
count = 0
for a,b in cut[1:]:
  if a > ex_b:
    count += 1
print(count+1)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
cut = []
for _ in range(m):
  a,b = map(int,input().split())
  cut.append((a,b))
cut.sort(key = lambda x:x[1])

ex_b  = cut[0][1]
count = 0
for a,b in cut[1:]:
  if a > ex_b:
    count += 1
print(count)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline
n, m = map(int, input().split())

request = []
for _ in range(m):
    a, b = map(int, input().split())
    request.append([a, b])

request.sort(key=lambda x: x[1])
pre = - 1
ans = 1
for a, b in request:
    if pre < a:
        ans += 1
        pre = b - 1

print(ans)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline
n, m = map(int, input().split())

request = []
for _ in range(m):
    a, b = map(int, input().split())
    request.append([a, b])

request.sort(key=lambda x: x[1])
first = request.pop(0)[1] - 1
ans = 1
for a, b in request:
    if first < a:
        ans += 1
        first = a

print(ans)

Submission status: Wrong Answer

Solution code:
N,M = list(map(int, input().split()))
ab = sorted([list(map(int, input().split())) for _ in range(M)], key=lambda x:x[1])
last = ab[0][1]
s = 1
for one in ab[1:]:
    a,b = one
    if a>last:
        s+=1
print(s)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
ab=[[0]*2 for _ in range(m)]
for i in range(m):
  a,b=map(int,input().split())
  ab[i][0],ab[i][1]=b,a
ab.sort()
cnt=0
b=0
for i in range(m):
  if b<ab[i][1]:
    cnt+=1
    b=ab[i][0]
print(cnt)

Submission status: Wrong Answer

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

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

cnt = 1
s = AB[0][1]
for a, b in AB[1:]:
    if s <= a:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

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

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

cnt = 1
s = AB[0][1]
for a, b in AB[1:]:
    if s < a:
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
##貪欲法(greedy)
#区間スケジューリング
#D - Islands War
#https://atcoder.jp/contests/abc103/tasks/abc103_d

n, m = list(map(int,input().split()))
lst = [list(map(int,input().split())) for _ in range(m)]
lst.sort(key=lambda x: x[1])
ans = []
ans.append(lst[0])

for i in range(1,m):
    if ans[-1][1] < lst[i][0]:
        ans.append(lst[i])

print(len(ans))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab.sort(key=lambda x: (x[1]))
ans = 1
now = ab[0][1]
for i in range(1, len(ab), 1):
    if ab[i][1] == now:
        continue
    else:
        ans += 1
        now = ab[i][1]
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab.sort(key=lambda x: (-x[1], -x[0]))
ans = 1
now = ab[0][0]
for i in range(1, len(ab), 1):
    if ab[i][1] <= now:
        ans += 1
        now = ab[i][0]
    else:
        continue
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
from operator import itemgetter

n,m = map(int, input().split())
ab = sorted([list(map(int, input().split())) for _ in range(m)], key=itemgetter(1))

res = 0
s = 0
for a,b in ab:
    if a<s+1<b:
        continue
    s = b-1
    res += 1

print(res)

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(key = lambda ab:ab[1])
count = 0
now = 0
print(ab)
for a,b in ab:
    if a >= now:
        count += 1
        now = b
print(count)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
ab = []
dp = [0 for i in range(N)]
for i in range(M):
    a,b = list(map(int,input().split()))
    dp[a-1] += 1
    dp[b-1] -= 1
    ab.append([a-1,b-1])

def search(dp,ab,count):
    maxd = max(dp)
    ind = dp.index(maxd)
    dp2 = [0 for i in range(N)]
    delite = []
    for i in range(len(ab)-1,-1,-1):
        if ab[i][0] <= ind <= ab[i][1]-1:
            ab.remove(ab[i])
        else:
            dp2[ab[i][0]] += 1
            dp2[ab[i][1]] -= 1
    for i in range(N-1):
        dp2[i+1] += dp2[i]
    count += 1
    if dp2 == [0 for i in range(N)]:
        return count
    else:
        return search(dp2,ab,count)
count = 1
dp = [0 for i in range(N)]
for i in range(M):
    dp[ab[i][0]] += 1
    dp[ab[i][1]] -= 1
for i in range(N-1):
    dp[i+1] += dp[i]
maxd = max(dp)
if maxd == M:
    print(1)
else:
    print(search(dp,ab,count)-1)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
ab={}
for i in range(m):
    a,b=map(int,input().split())
    if a in ab:
        ab[a]=min(ab[a],b)
    else:
        ab[a]=b
ab = sorted(ab.items(), key=lambda x:x[0])

ans=1
for i in range(1,len(ab)):
    if ab[i][0]>=ab[i-1][1]:
        ans+=1
print(ans)

Submission status: Wrong Answer

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

ab = sorted(ab, key=lambda x: (-x[0], x[1]))

left, right = -1, -1
cnt = 0
for a, b in ab:
    if b <= left or right <= a:
        cnt += 1
        left = a
        right = b
    else:
        left = min(a, left)
        right = max(b, right)
print(cnt)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

N, M = map(int, input().split())
ab = [[int(x) - 1 for x in input().split()] for _ in range(M)]

ab = sorted(ab, key=itemgetter(0), reverse=True)

left, right = -1, -1
cnt = 0
for a, b in ab:
    if b <= left or right <= a:
        cnt += 1
        left = a
        right = b
    else:
        left = min(a, left)
        right = max(b, right)
print(cnt)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
m = map(int,input().split())
AB = list(zip(m,m))
AB.sort(key=lambda x: x[1])
ans = 0
x = 0
for a,b in AB:
    if a < x:
        continue
    x = b-1
    ans += 1
print(ans)