Problem:


Score : 400 points

Problem Statement

There are N islands lining up from west to east, connected by N-1 bridges.

The i-th bridge connects the i-th island from the west and the (i+1)-th island from the west.

One day, disputes took place between some islands, and there were M requests from the inhabitants of the islands:

Request i: A dispute took place between the a_i-th island from the west and the b_i-th island from the west. Please make traveling between these islands with bridges impossible.

You decided to remove some bridges to meet all these M requests.

Find the minimum number of bridges that must be removed.

Constraints

All values in input are integers.

2 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq a_i < b_i \leq N

All pairs (a_i, b_i) are distinct.

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
a_2 b_2
:
a_M b_M

Output

Print the minimum number of bridges that must be removed.

Sample Input 1

5 2
1 4
2 5

Sample Output 1

1

The requests can be met by removing the bridge connecting the second and third islands from the west.

Sample Input 2

9 5
1 8
2 7
3 5
4 6
7 9

Sample Output 2

2

Sample Input 3

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

Sample Output 3

4



Sample input:
5 2
1 4
2 5


Sample output:
1

Submission status: Wrong Answer

Solution code:
import bisect
import heapq
n,m=map(int,input().split())
ab=[[int(i) for i in input().split()] for j in range(m)]
lia=[]
lib=[]
for a,b in ab:
    lia.append(a)
    lib.append(b)
lia.sort()
lib.sort()

ans=0
while lia:
    num=heapq.heappop(lib)
    idx=bisect.bisect_left(lia,num)
    lia=lia[idx:]
    lib.sort()

    if lia:
        idx=bisect.bisect_right(lib,lia[0])
        lib=lib[idx:]
    ans+=1

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import heapq
n,m=map(int,input().split())
ab=[[int(i) for i in input().split()] for j in range(m)]
lia=[]
lib=[]
for a,b in ab:
    lia.append(a)
    lib.append(b)
lia.sort()
lib.sort()

ans=0
while lia:
    num=heapq.heappop(lib)
    idx=bisect.bisect_left(lia,num)
    lia=lia[idx:]
    if idx!=0:
        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)]
ab.sort(key=lambda x: x[1])
print(ab)
c = 0
d = 0
for t in ab:
  if d < t[0]:
    c += 1
    d = t[1]-1
print(c)

Submission status: Wrong Answer

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

war.sort()
#print(war)
i = 0
j = 0

cnt = 0

while i < m:
    cnt += 1
    b = war[i][1]
    while war[j][0] < b:#等号不可だし[j][1]でない
        j += 1
        #print(i,j)
        if j >= m:
            break
    i = j

print(cnt)

Submission status: Wrong Answer

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

war.sort()
#print(war)
i = 0
j = 0

cnt = 0

while i < m:
    cnt += 1
    b = war[i][1]
    while war[j][1] <= b:
        j += 1
        #print(i,j)
        if j >= m:
            break
    i = j

print(cnt)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
War = [list(map(int,input().split())) for i in range(m)]
Island = [0 for i in range(2*n)]
for war in War:
  Island[war[0]*2-1] = 1
  Island[war[1]*2-2] = 2
count = 0
status = 0
for i in range(len(Island)):
  if Island[i] == 1:
    status = 1
  elif status == 1 and Island[i] == 2:
    count += 1
    status = 0
  else:
    continue
print(count)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
War = [list(map(int,input().split())) for i in range(m)]
Island = [0 for i in range(2*n)]
for war in War:
  Island[war[0]*2-1] = 1
  Island[war[1]*2-2] = 2
count = 0
set = 0
for i in range(len(Island)):
  if Island[i] == 1:
    set = 1
  elif set == 1 and Island[i] == 2:
    count += 1
    set = 0
  else:
    continue
print(count)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
War = [list(map(int,input().split())) for i in range(m)]
Island = [0 for i in range(2*n)]
for war in War:
  Island[war[0]*2-1] = 1
  Island[war[1]*2-2] = 2
count = 0
set = 0
for i in range(len(Island)):
  if Island[i] == 1:
    set = 1
  if set == 1 and Island[i+1] == 2:
    count += 1
    set = 0
print(count)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b, c = LI()
    ans = 10 ** 5
    ans = min(ans, abs(a - b) + abs(b - c))
    ans = min(ans, abs(a - c) + abs(b - c))
    ans = min(ans, abs(a - c) + abs(a - b))
    print(ans)
    return

#B
def B():
    s, t = S(), S()
    f = 0
    for i in range(len(s)):
        f = f or s[i:] + s[:i] == t
    print(["No","Yes"][f])
    return

#C
def C():
    return

# D
# 解説AC
# 貪欲かよ
# 言われればその通りでbi昇順でソートしていれば
# 直前で取り除いたものに関してはその橋より左側
# の街について絶対に橋が途切れているからね
# fuck!!! 
def D():
    n, m = LI()
    d = defaultdict(int)
    for _ in range(m):
        a, b = LI_()
        d[a] = max(d[a], n-b)
    mi = 0
    ans = 0
    for i in range(n-1):
        before = max(mi, d[i])
        if i == n - before - 1:
            mi = 0
            ans += 1
    print(ans)
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Wrong Answer

Solution code:
import heapq

n, m = map(int, input().split())
ls = [list(map(int, input().split())) for _ in range(m)]
ls2 = [(r, l) for l, r in ls]
heapq.heapify(ls)
heapq.heapify(ls2)
ss = [False for _ in range(n + 1)]
ts = [False for _ in range(n + 1)]
for l, r in ls:
    ss[l] = True
    ts[r] = True
skip_s = True
skip_t = False
index = 0
res = 0
while ls2:
    r, l = heapq.heappop(ls2)
    res += 1
    ls_new = []
    while ls:
        ll, rr = heapq.heappop(ls)
        if ll >= r:
            heapq.heappush(ls_new, (ll, rr))
    ls = ls_new
    ls2 = [(r, l) for l, r in ls]

print(res)

Submission status: Wrong Answer

Solution code:
import sys
from pprint import pprint

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

troubles = []
for _ in range(m):
    a, b = map(int, sys.stdin.readline().strip().split(" "))
    troubles.append((a, b))

min_b = 10 ** 9
max_a = -1
breaked = -1
ans = 0
for a, b in sorted(troubles):
    # print(a, b)
    if a <= breaked < b:
        # print("pass")
        continue

    max_a = max(a, max_a)
    min_b = min(b, min_b)

    if max_a + 1 == min_b:
        # print("break!")
        breaked = max_a
        ans += 1

        min_b = 10 ** 9
        max_a = -1

if breaked < a:
    # print("last break!")
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(M)]
ab.sort()
ans = 1
l, r = ab[0][0], ab[0][1]

for a,b in ab[1:]:
    l = max(l,a)
    if l >= r:
        ans += 1
    
    if min(r,b) == l:
        r = b
    else:
        r = min(r,b)

print(ans)

Submission status: Wrong Answer

Solution code:
#クエリの右端が西に近いものから見る
#その右端より西に左端を持つクエリは同時に遂行できる
#どんよく
from bisect import bisect_right as br
N, M = map(int, input().split())
Q = [list(map(int, input().split())) for _ in range(M)]
Q.sort(key = lambda x: x[1])
Qa = [q[0] for q in Q]
i = 0
res = 0
while i < M:
  b = Q[i][1]
  ind = br(Qa, b - 1)
  #print(b, Q[ind - 1])
  res += 1
  i = ind
print(res)

Submission status: Wrong Answer

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

A=list(set(A))

A.sort(reverse=True)
minB=min(B)

for i,t in enumerate(A):
	if t<minB:
		break
print(i+1)

Submission status: Wrong Answer

Solution code:
N,M = [int(i) for i in input().split()]
wars = [[int(i) for i in input().split()] for _ in range(M)]

wars.sort(key=lambda x:x[1],reverse=False)
r = set()

for war in wars:
    for i in set():
        if i <= war[1] and i >= war[0]:
            break
    else:
        r.add(war[1]-1)

print(len(r))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
def solve():
  n,m = (int(i) for i in input().split())
  query = []
  for i in range(m):
    a,b = (int(i) for i in input().split())
    query.append((b-1,a-1))
  query.sort()
  ans = 0
  bridge = [True]*(n-1)
  remove = 10**15
  for i in range(m):
    b,a = query[i]
    if not remove < a:
      if bridge[b-1]:
        ans += 1
        bridge[b-1] = False
        remove = b-1
  print(ans)
    
solve()

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
ts=time.time()
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
show_flg=False
#show_flg=True

ans=0
n,m=MI()
ed=[-1]*n
A=[0]*n
B=[0]*n
r=[]
for i in range(m):
    a,b=LI_()
    r+=[(a,b)]
    ed[a]=b
    A[a]=1
    B[b]=1

show(r,A,B)
q=[]
for i in range(n):
    show(i,'q=',q,ans,end=' | ')
    if B[i]==1:
        ans+=1
        for j in q:
            B[ed[j]]=0
        q=[]
    if A[i]==1:
        q.append(i)
    show(i,'q=',q,ans,A,B)    
print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def show(*inp):
    if show_flg:
        print(*inp)
YN=['Yes','No']
mo=10**9+7
ts=time.time()
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
show_flg=False
show_flg=True

ans=0
n,m=MI()
ed=[-1]*n
A=[0]*n
B=[0]*n
for i in range(m):
    a,b=LI_()
    ed[a]=b
    A[a]=1
    B[b]=1
    
q=[]
for i in range(n):
    if A[i]==1:
        q.append(i)
    if B[i]==1:
        ans+=1
        for j in q:
            ed[j]=0
        q=[]
        
print(ans)

Submission status: Wrong Answer

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

start = [0] * (N+1)
end = [0] * (N+1)

for i in range(M):
    a,b = map(int,input().split())
    start[a] += 1
    end[b] += 1

status = 0
count = 0

for j in range(1,N+1):
    if status == 1 and end[j] > 0:
        status = 0
        count += 1
    if start[j] > 0:
        status = 1
    #print(j,status,count)

print(count)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
a=[]
b=[]
for _ in range(m):
    l,r=map(int,input().split())
    a.append(l)
    b.append(r)
a=list(set(a))
b=list(set(b))
cnt=0
while max(b)>0:
    M=max(a)
    for i in range(len(b)):
       if b[i]>M:
           b[i]=0
    a.remove(M)
    cnt+=1
print(cnt)

Submission status: Wrong Answer

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

b = a
b.sort(key = lambda x: x[0])
b.sort(key=lambda x: x[1])
b.reverse()

visited = [b[0][1] + 1]
count = 0
for i in range(len(b)):
    c = b[i][1]
    vmin = min(visited)
    if c < vmin:
        visited.append((b[i][0]) + 1)
        count += 1
    else:
        continue

print(count)

Submission status: Wrong Answer

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

b = a
b.sort(key = lambda x: x[0])
b.sort(key=lambda x: x[1])
b.reverse()

visited = []
count = 0
for i in range(len(b)):
    c = b[i][1]
    if c not in visited:
        visited.append(c)
        count += 1
    else:
        continue

print(count)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
breaklist = []
for i in range(m):
    a, b = map(int, input().split())
    if i == 0:
        breaklist.append([a, b])
    else:
        for j in range(len(breaklist)):
            if breaklist[j][0] >= b or breaklist[j][1] <= a:
                if j == len(breaklist) - 1:
                    breaklist.append([a, b])
                    break
                else:
                    continue
            else:
                breaklist[j] = [max([breaklist[j][0], a]), min(breaklist[j][1], b)]
print(len(breaklist))

Submission status: Wrong Answer

Solution code:
N, M = (int(x) for x in input().split())
task_list = [
    {
        "index": i,
        "a": 0,
        "b": 0,
    } for i in range(M)
]
for i in range(M):
    task_list[i]["a"], task_list[i]["b"] = (int(x) for x in input().split())

task_list.sort(key=lambda x:x["b"])
ans, pointer = 0, 0
while pointer < M-1:
    task = task_list[pointer]
    j = 1
    while pointer+j < M and task_list[pointer+j]["a"] <= task["b"]\
    and task["b"] <= task_list[pointer+j]["b"]:
        j += 1
    else:
        ans += 1
        if pointer+j == M:
            print(ans)
            exit()
        else:
            pointer += 1
else:
    print(ans+1)
    exit()

Submission status: Wrong Answer

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

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

bridge = []
ans = 0
for i in range(m):
    count = True
    for j in range(a[m - i - 1][0],a[m - i - 1][1]):
        if j in bridge:
            count = False
            
    if count:
        ans += 1
        bridge.append(a[m - i - 1][0]-1)

print(ans)

Submission status: Wrong Answer

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

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

bridge = []
ans = 0
for i in range(m):
    count = True
    for j in range(a[m - i - 1][0],a[m - i - 1][1]):
        if j in bridge:
            count = False
            
    if count:
        ans += 1
        bridge.append(a[m - i - 1][1]-1)
print(ans)

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    req = []
    for i in range(M):
        a, b = map(int, input().split())
        req.append([a, i, 0])
        req.append([b, i, 1])
    req.sort(key = lambda x: x[0])

    tocut = set()
    count = 0
    for i in range(len(req)):
        if req[i][2] == 0:
            tocut.add(req[i][1])
        else:
            if req[i][1] in tocut:
                count += 1
                tocut = set()
    return count



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

Submission status: Wrong Answer

Solution code:
from operator import itemgetter
n, m = map(int, input().split())

ab = [tuple(map(int, input().split())) for i in range(m)]

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

count = 0
cut = 0
for i in range(m):
    if cut < ab[i][0]:
        count += 1
        cut = ab[i][1]

print(count)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(m)]
ab.sort(key=lambda x:-x[1])
r=10**6
l=0
ans=1
for i in range(m):
    r=min(r,ab[i][1])
    l=max(l,ab[i][0])
    if r<=l:
        ans+=1
        l=0
print(ans)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc103/tasks/abc103_d
# D - Islands War

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

for _ in range(m):
    a, b = list(map(int, input().split()))
    ab_list.append((a, b))

# 区間が被っている場合は、一括で分けられる
# 区間が被っていない場合は、個別に分ける必要がある
# 区間が被っている個数を数えればよいはず

# 最小の区間を調べる
ab_list = sorted(ab_list, key=lambda x: (x[0], x[1]))
# print(ab_list)
i = 0
count = 0

while i < len(ab_list):
    count += 1

    a, b = ab_list[i]
    diff_index = 1
    end_index = b

    debug_list = [(a, b)]

    if (i + diff_index) >= len(ab_list):
        break

    # 次の区間について
    while ab_list[i + diff_index][0] < end_index:
        # debug_list.append(ab_list[i + diff_index])

        diff_index += 1

        if (i + diff_index) >= len(ab_list):
            break

        if ab_list[i + diff_index][1] < end_index:
            end_index = ab_list[i + diff_index][1]

    # print('==========')
    # print(debug_list)

    i = i + diff_index

print(count)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc103/tasks/abc103_d
# D - Islands War

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

for _ in range(m):
    a, b = list(map(int, input().split()))
    ab_list.append((a, b))

# 区間が被っている場合は、一括で分けられる
# 区間が被っていない場合は、個別に分ける必要がある
# 区間が被っている個数を数えればよいはず

# 最小の区間を調べる
ab_list = sorted(ab_list, key=lambda x: x[0])
# print(ab_list)
i = 0
count = 0

while i < len(ab_list):
    count += 1

    a, b = ab_list[i]
    diff_index = 1
    end_index = b

    debug_list = [(a, b)]

    if (i + diff_index) >= len(ab_list):
        break

    # 次の区間について
    while ab_list[i + diff_index][0] < end_index:
        # debug_list.append(ab_list[i + diff_index])

        diff_index += 1

        if (i + diff_index) >= len(ab_list):
            break

        if ab_list[i + diff_index][1] < end_index:
            end_index = ab_list[i + diff_index][1]

    # print('==========')
    # print(debug_list)

    i = i + diff_index

print(count)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc103/tasks/abc103_d
# D - Islands War

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

for _ in range(m):
    a, b = list(map(int, input().split()))
    ab_list.append((a, b))

# 区間が被っている場合は、一括で分けられる
# 区間が被っていない場合は、個別に分ける必要がある
# 区間が被っている個数を数えればよいはず

# 最小の区間を調べる
ab_list = sorted(ab_list, key=lambda x: x[0])
i = 0
count = 0

while i < len(ab_list):
    count += 1

    a, b = ab_list[i]
    diff_index = 1
    end_index = b

    debug_list = [(a, b)]

    if (i + diff_index) >= len(ab_list):
        break

    # 次の区間について
    while ab_list[i + diff_index][0] < end_index:
        debug_list.append(ab_list[i + diff_index])

        diff_index += 1

        if (i + diff_index) >= len(ab_list):
            break

        if ab_list[i + diff_index][1] < end_index:
            end_index = ab_list[i + diff_index][1]

    i = i + diff_index

print(count)

Submission status: Wrong Answer

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

bridges = []

for i in range(M):
    bridges.append(list(map(int, input().split())))

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

#print(bridges)
count = 0
se = []

for bridge in bridges:
    boolean = True
    for s, e in se:
        if e > bridge[0] and bridge[1] > s:
            boolean = False
    if boolean:
        se.append((bridge[0], bridge[1]))
        count += 1
print(count)

Submission status: Wrong Answer

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

bridges = []

for i in range(M):
    bridges.append(list(map(int, input().split())))

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

#print(bridges)
count = 0
s, e = N+1, -1

for bridge in bridges:
    if e <= bridge[0]:
        count += 1
        e = bridge[1]
    elif bridge[1] <= s:
        count += 1
        s = bridge[0]
print(count)

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
#sys.setrecursionlimit(10 ** 9)
import math
import heapq

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

area = list(map(int, input().split()))
areas = [[area[0], area[1] - 1]]
for i in range(M - 1):
	area = list(map(int, input().split()))
	loc = bisect.bisect_right(areas, [area[0], 1000000000])
	if loc != 0 and area[0] <= areas[loc - 1][1]:
		areas[loc - 1] = [area[0], min(areas[loc - 1][1], area[1] - 1)]
	elif loc != len(areas) and area[1] - 1 >= areas[loc][0]:
		areas[loc] = [areas[loc][0], min(areas[loc][1], area[1] - 1)]
	else:
		bisect.insort(areas, [area[0], area[1] - 1])

print(len(areas))

Submission status: Wrong Answer

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

aggregations = []
for ab in AB:
    islands = [x for x in range(ab[0], ab[1] + 1)]
    for agr in aggregations:
        intersection = list(set(islands) & set(agr))
        if len(intersection) > 1:
            aggregations.remove(agr)
            aggregations.append(intersection)
            break
    else:
        aggregations.append(islands)

print(len(aggregations))

Submission status: Wrong Answer

Solution code:
n,m=[int(x) for x in input().split()]
ab=[[int(x) for x in input().split()] for i in range(m)]

ab.sort(key=lambda x:x[1])
#print(ab)
split=[0,]

#while len(ab)!=0:
for item in ab:
  if (item[1]-split[-1]>0 and item[0]-split[-1]<=0)!=True:
    split.append(ab[0][1]-1)
  
  #print(ab)
print(len(split)-1)

Submission status: Wrong Answer

Solution code:
N, M = list(map(int, input().split(' ')))
edges = []
for i in range(M):
    a, b = list(map(int, input().split(' ')))
    edges.append((a, b))
 
ans = 0
while any(edges):
    hit_index = 0
    max_hit = 0
    start = None
    for i in range(len(edges)):
        if edges[i]:
            l = edges[i][0]
            r = edges[i][1]
            break
    for v in range(l, r):
        hit = 0
        for i in range(M):
            if edges[i] and edges[i][0] <= v < edges[i][1]:
                hit += 1
            if hit > max_hit:
                max_hit = hit
                hit_index = v
    for i in range(len(edges)):
        if edges[i] and edges[i][0] <= hit_index < edges[i][1]:
            edges[i] = False
    ans += 1

print(ans)

Submission status: Wrong Answer

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

ans = 0
alive = [False for _ in range(M)]
while any(edges):
    hit_index = 0
    max_hit = 0
    edge = []
    for i in range(len(edges)):
        if edges[i]:
            edge = edges[i]
            break
    for v in edge:
        hit = 0
        for i in range(M):
            if edges[i] and v in edges[i]:
                hit += 1
            if hit > max_hit:
                max_hit = hit
                hit_index = v
    # print('max_hit')
    # print(max_hit)
    # print('cut here')
    # print(hit_index)
    for i in range(len(edges)):
        if edges[i] and hit_index in edges[i]:
            edges[i] = False
    ans += 1
    # print('cutted')
    # print(edges)
print(ans)

Submission status: Wrong Answer

Solution code:
import os, sys, re, math

lines = sys.stdin.readlines()

(n, m) = [int(v) for v in lines[0].split()]
areas = []
for i in range(m):
    (a, b) = [int(v) for v in lines[i + 1].split()]
    extended = False
    for area in areas:
        if (area[0] <= a < area[1] or area[0] < b <= area[1]):
            area[0] = max(area[0], a)
            area[1] = min(area[1], b)
            extended = True
            break
    if not extended:
        areas.append([a, b])

print (len(areas))

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
s = n + 1
ret = 0
for a, b in ab:
    if s <= a:
        ret += 1
        s = n + 1
    s = min(s, b)
if s != n + 1:
    ret += 1
print(ret)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
ab = sorted(ab, key=lambda x:x[1], reverse=True)
print(ab)

dellist = lambda items,indices: [item for idx,item in enumerate(items) if idx not in indices]

count = 0
while len(ab) != 0:
  p = ab.pop()
  count += 1
  del_idx = []
  for i in range(len(ab)):
    if ab[i][0] < p[1]:
      del_idx.append(i)
  ab = dellist(ab, del_idx) # ['japanese','!!']
print(count)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
a=[]
b=[]
for i in range(m):
    t=input().split()
    a.append(int(t[0]))
    b.append(int(t[1]))
#l.sort(key=sortsecond)
a = list(set(a))
m2 = len(a)

count = 1
for j in range(m2):
  for k in range(m):
    if a[j] >= b[k]:
      count += 1
      break
      
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()

l = ab[0][0]
r = ab[0][1]
ans = 0

if m == 1:
    print(1)

for i in range(1,m):
    if r<=ab[i][0]:
        ans += 1
        l = ab[i][0]
        r = ab[i][1]
    else:
        r = min(r, ab[i][1])

    if i==m-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)]

ab.sort()

l = ab[0][0]
r = ab[0][1]
ans = 0

for i in range(1,m):
    if r<=ab[i][0]:
        ans += 1
        l = ab[i][0]
        r = ab[i][1]
    else:
        r = min(r, ab[i][1])

    if i==m-1:
        ans += 1

print(ans)

Submission status: Wrong Answer

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

import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7

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

x = [0]*(n+2)
ans = 1
k = 0
for a,b in ab:
    y = list(accumulate(x))
    if k not in y[a:b+1]:
        ans += 1
    x[a] += 1
    x[b+1] -= 1
    k += 1
print(ans)

Submission status: Wrong Answer

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

x = n
l = 0
for a, b in reversed(AB):
  if b > x :
    continue
  else:
    x = a
    l += 1
    
print(l)

Submission status: Wrong Answer

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

x = m
l = 0
for a, b in reversed(AB):
  if b > x :
    continue
  else:
    x = a
    l += 1
    
print(l)

Submission status: Wrong Answer

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

x = 0
l = 0
for a, b in reversed(AB):
  if  a <= x and b > x :
    continue
  else:
    x = a
    l += 1
    
print(l)

Submission status: Wrong Answer

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

x.sort()
res = 0
right = 0
for i in range(M):
    if x[i][0] >= right:
        right = x[i][1]
        res += 1

print(res)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
sp=[None for i in range(m)]
for i in range(m):
  l,r=map(int,input().split())
  sp[i]=[l,r]
sp.sort(key=lambda x:x[1])
sp.sort(key=lambda x:x[0])
s=[sp[0]]
for i in sp:
  if i[0]!=s[-1][0]:
    s.append(i)
ans=1
c=s[0]
if len(s)==1:print(1)
else:
  for i in range(1,len(s)):
    if c[1]<=s[i][0]:
      ans+=1
      c=s[i]
    if c[1]>s[i][1]:
      c=s[i]
    else:
      c[0]=s[i][0]
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
AB=[]
for i in range(M):
    ab=list(map(int,input().split()))
    AB.append(ab)
#AB=sorted(AB, key=lambda x:x[0])

ans=[]

for i in range(M):
    #print(AB[i][0],AB[i][1])
    if i==0:
        ans.append([AB[0][0],AB[0][1]])
    else:
        flag=True
        for A in ans:
            if AB[i][0]<A[1] and AB[i][1]>A[1]:
                flag=False
                break
            elif AB[i][0]<A[1] and AB[i][1]<=A[1]:
                A[1]=AB[i][1]
                flag=False
                break
        if flag:
            ans.append([AB[i][0],AB[i][1]])

print(len(ans))
#print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
AB=[]
for i in range(M):
    ab=list(map(int,input().split()))
    AB.append(ab)
#AB=sorted(AB, key=lambda x:x[0])

ans=[]

for i in range(M):
    print(AB[i][0],AB[i][1])
    if i==0:
        ans.append([AB[0][0],AB[0][1]])
    else:
        flag=True
        for A in ans:
            if AB[i][0]<A[1] and AB[i][1]>A[1]:
                flag=False
                break
            elif AB[i][0]<A[1] and AB[i][1]<=A[1]:
                A[1]=AB[i][1]
                flag=False
                break
        if flag:
            ans.append([AB[i][0],AB[i][1]])

print(len(ans))
#print(ans)

Submission status: Wrong Answer

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

def minpair(A,B):
    C = []
    if A[1] > B[0]:
        C = [B[0],A[1]]
    elif B[1] > A[0]:
        C = [A[0],B[1]]
    elif A[0]<=B[0] and B[1]<=A[1]:
        C = B
    elif B[0]<A[0] and A[1]<B[1]:
        C = A
    return C

Bridge.sort(key=lambda x: x[0])
c = 0
ans = 0
while c <= M-2:
    Temp = minpair(Bridge[c],Bridge[c+1])
    if Temp == []:
        ans += 1
    else:
        Bridge[c+1] = Temp
    c += 1
print(ans+1)

Submission status: Wrong Answer

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

def minpair(A,B):
    C = []
    if A[1] > B[0]:
        C = [B[0],A[1]]
    elif B[1] > A[0]:
        C = [A[0],B[1]]
    return C

Bridge.sort(key=lambda x: x[0])
c = 0
ans = 0
while c <= M-2:
    Temp = minpair(Bridge[c],Bridge[c+1])
    if Temp == []:
        ans += 1
    else:
        Bridge[c+1] = Temp
    c += 1
print(ans+1)

Submission status: Wrong Answer

Solution code:
from collections import deque


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

print(count)

Submission status: Wrong Answer

Solution code:
from collections import deque


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

print(count)