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: Time Limit Exceeded

Solution code:
import sys
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def Main():
    n,m = IL()
    war = [list(IL()) for _ in range(m)]
    war.sort(key=lambda x: x[1])
    bridge = [1]*n
    for rep in war:
        left = rep[0]-1
        right = rep[1]-1
        if not 0 in bridge[left:right]:
            bridge[right-1] = 0
    print(bridge.count(0))
    return

if __name__=='__main__':
    Main()

Submission status: Time Limit Exceeded

Solution code:
import sys 
from collections import deque
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))

def solve(n,m,a,b):
    t = -1
    for bit in range(2**(n-1)):
        bridge = [1]*(n-1)
        for rep in range(n-1):
            if (bit>>rep)&1:
                bridge[rep] = 0
        for rep in range(m):
            ok = True
            if not 0 in bridge[a[rep]:b[rep]]:
                ok = False
                break
        if ok:
            if t == -1:
                t = bin(bit).count('1')
            else:
                t = min(t,bin(bit).count('1'))
    return t
        

def main():
    tmp = deque(LI())
    N,M = tmp.popleft(),tmp.popleft()
    a,b = deque(),deque()
    for _ in range(M):
        tmp = deque(LI())
        a.append(tmp.popleft()-1)
        b.append(tmp.popleft()-1)
    print(solve(N,M,a,b))
    return

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
L = []
for _ in range(M):
    a,b = map(int,input().split())
    L.append([a,b])
L = sorted(L,key = lambda x:x[1])
cnt = 0
while len(L):
    now = L.pop(0)
    cnt += 1
    while len(L):
        if L[0][0] + 1 <= now[1]  and now[1]  < L[0][1] + 1:
            L.pop(0)
        else:
            break
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
L = []
for _ in range(M):
    a,b = map(int,input().split())
    L.append([a,b])
L = sorted(L,key = lambda x:x[1])
cnt = 0
while len(L):
    now = L.pop(0)
    cnt += 1
    while len(L):
        if L[0][0] <= now[1] - 0.5 and now[1] - 0.5  <= L[0][1]:
            L.pop(0)
        else:
            break
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
ab = []
for i in range(m):
    ab.append(tuple(map(int, input().split())))
sect = sorted(ab, key=lambda x:x[1])
delete = []

for s in sect:
    flag = False
    if not delete:
        delete.append(s[1]-1)
    else:
        for d in delete:
            if s[0]<=d<s[1]: flag = True
        if flag == False:
            delete.append(s[1]-1)

print(len(delete))

Submission status: Time Limit Exceeded

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

query = []
bridge = [1 for _ in range(N-1)]

for _ in range(M):
    a, b = map(int, input().split())
    query.append((a-1, b-1, b-a))

#街が左にある方を優先
query = sorted(query, key=lambda x: x[1])
#喧嘩する街が近い方を優先
# query = sorted(query, key=lambda x: x[2])

for i, j, _ in query:
    # print(i, j)
    # print(bridge[i:j])
    if sum(bridge[i:j]) == j-i:
        bridge[j-1] = 0
        # print("a", bridge[j-1])

# print(bridge)
print(N-1-sum(bridge))

Submission status: Time Limit Exceeded

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

ans = float('inf')
for bit in range(2**(n-1)):
    check = 0
    bre_b = [0 for _ in range(n-1)]
    for i in range(n-1):
        if bit & 1 << i:
            bre_b[i] = 1
    for war in wars:
        if not 1 in bre_b[war[0]-1:war[1]-1]:
            check += 1
    if check == 0:
        ans = min(ans, bre_b.count(1))
print(ans)

Submission status: Time Limit Exceeded

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

lists = []
for i in range(M):
    lists.append(list(map(int,input().split())))
    lists.sort(key=lambda x: x[1])
ans = 0
min_b = 0
for a, b in lists:
    if min_b <= a:
        min_b = b
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
def main():
    n, m = map(int, input().split())
    data = [list(map(int, input().split())) for _ in range(m)]
    rule = [[] for _ in range(n)]
    for i in range(m):
        rule[data[i][0] - 1].append(data[i][1])
        rule[data[i][1] - 1].append(data[i][0])
    res = rule[0][:]
    ans = 0
    for j in range(n - 1):
        if j + 2 not in res:
            res.extend(rule[j + 1])
        else:
            ans += 1
            res = []
            res.extend(rule[j + 1])
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(m)]
rule = [[] for _ in range(n)]
for i in range(m):
    rule[data[i][0] - 1].append(data[i][1])
    rule[data[i][1] - 1].append(data[i][0])
res = rule[0][:]
ans = 0
for j in range(n - 1):
    if j + 2 not in res:
        for k in range(len(rule[j + 1])):
            res.append(rule[j + 1][k])
    else:
        ans += 1
        res = []
        for k in range(len(rule[j + 1])):
            res.append(rule[j + 1][k])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from pprint import pprint
from copy import deepcopy

#N <= 10**5なので、全探索はNG
#Greedyでいける？


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

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

bridge_list = [[] for _ in range(n-1)]

for i in range(m):
    startpoint = requests[i][0]
    endpoint = requests[i][1]
    for j in range(startpoint,endpoint):
        bridge_list[j-1].append(i)

#pprint(bridge_list)

checked_requests = [0] * m

#bridge_list = sorted(bridge_list, key=lambda x: len(x))

counter = 0

while sum(checked_requests) != m:
    #max_index = bridge_list.index(max(list(map(len,bridge_list))))
    length_list = list(map(len,bridge_list))
    max_index = length_list.index(max(length_list))

    #bridge_list[max_index]を直接 for k in に突っ込むと、removeメソッドがあるため動作がおかしくなってしまう。
    temp = deepcopy(bridge_list[max_index])

    for k in temp:
        checked_requests[k] = 1
        for l in range(n-1):
            try:
                bridge_list[l].remove(k)
            except ValueError:
                pass
    
    counter += 1
    
pprint(counter)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split(' '))
war=[tuple(map(int,input().split(' '))) for _ in range(m)]
war.sort(key=lambda x:x[1])
bridge=[0]*n
for w in war:
    if not 1 in set(bridge[w[0]:w[1]]):
        bridge[w[1]-1]=1
print(sum(bridge))

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split(' '))
war=[tuple(map(int,input().split(' '))) for _ in range(m)]
war.sort(key=lambda x:x[1])
bridge=[0]*n
for w in war:
    if sum(bridge[w[0]:w[1]])==0:
        bridge[w[1]-1]=1
print(sum(bridge))

Submission status: Time Limit Exceeded

Solution code:

n,m = list(map(int,input().split()))
d = [0]*m
ma = 0
mi = 0
for i in range(m):
    a,b = list(map(int,input().split()))
    d[i] = ((1<<a)-1) ^ ((1<<b)-1)
    ma = max(ma,a,b)
    mi = min(mi,a,b)
s = ((1<<ma)-1) | ((1<<mi)-1) 
for bit in range(1<<n):
    if bit & s:
      spr = [True]*m
      for k in range(m):
        if (d[k] & bit) > 0:
          spr[k] = False
      if sum(spr) == 0:
        print(sum([1 for i in range(n) if bit & 1<<i]))
        exit()

Submission status: Time Limit Exceeded

Solution code:
def main():
  n,m = list(map(int,input().split()))
  d = [0]*m
  ma = 0
  mi = 0
  for i in range(m):
    a,b = list(map(int,input().split()))
    d[i] = ((1<<a)-1) ^ ((1<<b)-1)
    ma = max(ma,a,b)
    mi = min(mi,a,b)
  s = ((1<<ma)-1) | ((1<<mi)-1) 
  for bit in range(1<<n):
    if bit & s:
      spr = [True]*m
      for k in range(m):
        if (d[k] & bit) > 0:
          spr[k] = False
      if sum(spr) == 0:
        print(sum([1 for i in range(n) if bit & 1<<i]))
        exit()

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
  n,m = list(map(int,input().split()))
  d = []
  ma = 0
  mi = 0
  for i in range(m):
    a,b = list(map(int,input().split()))
    d.append( ((1<<a)-1) ^ ((1<<b)-1) )
    ma = max(ma,a,b)
    mi = min(mi,a,b)
  s = ((1<<ma)-1) | ((1<<mi)-1) 
  for bit in range(1<<n):
    if bit & s:
      spr = [True]*m
      for k in range(m):
        if (d[k] & bit) > 0:
          spr[k] = False
      if sum(spr) == 0:
        print(sum([1 for i in range(n) if bit & 1<<i]))
        exit()

main()

Submission status: Time Limit Exceeded

Solution code:
n,m = list(map(int,input().split()))
d = []
ma = 0
mi = 0
for i in range(m):
  a,b = list(map(int,input().split()))
  d.append( ((1<<a)-1) ^ ((1<<b)-1) )
  ma = max(ma,a,b)
  mi = min(mi,a,b)
s = ((1<<ma)-1) | ((1<<mi)-1) 
for bit in range(1<<n):
  if bit & s:
    spr = [True]*m
    for k in range(m):
      if (d[k] & bit) > 0:
        spr[k] = False
    if sum(spr) == 0:
      print(sum([1 for i in range(n) if bit & 1<<i]))
      exit()

Submission status: Time Limit Exceeded

Solution code:
n,m = list(map(int,input().split()))
d = []
for i in range(m):
  a,b = list(map(int,input().split()))
  d.append( ((1<<a)-1) ^ ((1<<b)-1) )

for bit in range(1<<n):
    spr = [True]*m
    for k in range(m):
      if (d[k] & bit) > 0:
        spr[k] = False
    if sum(spr) == 0:
      print(sum([1 for i in range(n) if bit & 1<<i]))
      exit()

Submission status: Time Limit Exceeded

Solution code:
n,m = list(map(int,input().split()))
d = []
s = 1<<0
for i in range(m):
  a,b = list(map(int,input().split()))
  d.append( ((1<<a)-1) ^ ((1<<b)-1) )

ans = float('inf')
for bit in range(1<<n):
    spr = [True]*m
    for k in range(m):
      if (d[k] & bit) > 0:
        spr[k] = False
    if sum(spr) == 0:
      ans = min(ans, sum([1 for i in range(n) if bit & 1<<i]))
      print(ans)
      exit()

Submission status: Time Limit Exceeded

Solution code:

n,m = list(map(int,input().split()))
d = []
spr = [[False]*m]
s = 1<<0
for i in range(m):
  a,b = list(map(int,input().split()))
  d.append( ((1<<a)-1) ^ ((1<<b)-1) )

for bit in range(1<<n):
  spr = [True for _ in range(m)]
  for k in range(m):
      if (d[k] & bit) > 0:
        spr[k] = False
  if sum(spr) == 0:
      print(sum([1 for i in range(n) if bit & 1<<i]))
      exit()

Submission status: Time Limit Exceeded

Solution code:

n,m = list(map(int,input().split()))
d = []
spr = [[False]*m]
s = 1<<0
for i in range(m):
  a,b = list(map(int,input().split()))
  d.append( ((1<<a)-1) ^ ((1<<b)-1) )

ans = float('inf')
for bit in range(1<<n):
  spr = [True for _ in range(m)]
  for k in range(m):
      if (d[k] & bit) > 0:
        spr[k] = False
  if sum(spr) == 0:
      ans = min(ans, sum([1 for i in range(n) if bit & 1<<i]))
      print(ans)
      exit()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,m = list(map(int,input().split()))
d = [[1<<n] for _ in range(m)]
s = 1<<0
for i in range(m):
  a,b = list(map(int,input().split()))
  d[i] = ((1<<a)-1) ^ ((1<<b)-1)

spr = [[False] for _ in range(m)]

ans = float('inf')
for bit in range(1<<n):
  spr = [True for _ in range(m)]
  for k in range(m):
      if (d[k] & bit) > 0:
        spr[k] = False
  if sum(spr) == 0:
      ans = min(ans, sum([1 for i in range(n) if bit & 1<<i]))
      print(ans)
      exit()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,m = list(map(int,input().split()))
d = [[1<<n] for _ in range(m)]
s = 1<<0
for i in range(m):
  a,b = list(map(int,input().split()))
  d[i] = ((1<<a)-1) ^ ((1<<b)-1)

spr = [[False] for _ in range(m)]

ans = float('inf')
for bit in range(1<<n):
  spr = [True for _ in range(m)]
  for k in range(m):
      if (d[k] & bit) > 0:
        spr[k] = False
  if sum(spr) == 0:
      ans = min(ans, sum([1 for i in range(n) if bit & 1<<i]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,m = list(map(int,input().split()))
d = [[1<<n] for _ in range(m)]
s = 1<<0
for i in range(m):
  a,b = list(map(int,input().split()))
  d[i] = ((1<<a)-1) ^ ((1<<b)-1)
  s |= d[i]

spr = [[False] for _ in range(m)]

ans = float('inf')
for bit in range(1<<n):
  spr = [True for _ in range(m)]
  if bit & s > 0:
    for k in range(m):
      if (d[k] & bit) > 0:
        spr[k] = False
    if sum(spr) == 0:
      ans = min(ans, sum([1 for i in range(n) if bit & 1<<i]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,m = list(map(int,input().split()))
d = [[1<<n] for _ in range(m)]
s = 1<<0
for i in range(m):
  a,b = list(map(int,input().split()))
  d[i] = ((1<<a)-1) ^ ((1<<b)-1)
  s |= d[i]

spr = [[False] for _ in range(m)]

ans = float('inf')
for bit in range(1<<n):
  spr = [True for _ in range(m)]
  for i in range(n):
    if bit & 1<<i and s & 1<<i:
      for k in range(m):
        if (d[k] & 1<<i) > 0:
          spr[k] = False
      if sum(spr) == 0:
        ans = min(ans, sum([1 for i in range(n) if bit & 1<<i]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,m = list(map(int,input().split()))
d = [[1<<n] for _ in range(m)]
for i in range(m):
  a,b = list(map(int,input().split()))
  d[i] = ((1<<a)-1) ^ ((1<<b)-1)

spr = [[False] for _ in range(m)]
s = 1<<0
for x in d:
  s |= x

ans = float('inf')
for bit in range(1<<n):
  spr = [True for _ in range(m)]
  for i in range(n):
    if bit & 1<<i and s & 1<<i:
      for k in range(m):
        if (d[k] & 1<<i) > 0:
          spr[k] = False
      if sum(spr) == 0:
        ans = min(ans, sum([1 for i in range(n) if bit & 1<<i]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
kukan = sorted([list(map(int, input().split())) for _ in range(M)], key=lambda x: x[1])
ans = 0

while kukan:
    cut = kukan[0][1] - 1
    kukan = list(filter(lambda x: not x[0] <= cut < x[1], kukan))
    ans += 1

print(ans)

Submission status: Time Limit Exceeded

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:
        islands[i + 1] = islands[i] | islands[i + 1]

ans += len(islands[n])

print(ans)

Submission status: Time Limit Exceeded

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[i + 1].add(j)

ans += len(islands[n])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
lst = [list(map(int,input().split())) for _ in range(m)]
lst.sort(key=lambda x:x[1])
res = []
for i in range(m):
    a,b = lst[i][0], lst[i][1]
    flg = False
    if i==0:
        res.append(b-1)
    else:
        for r in res:
            if a<=r<=b:
                flg=True
        if not flg:
            res.append(b-1)
print(len(res))

Submission status: Time Limit Exceeded

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


while new_numbers:
    large = new_numbers[0][0]
    if  not new_numbers[0] in answers:
        answers.append(new_numbers[0])
    new_numbers=[a for a in new_numbers if a[1]>=large]
print(len(answers))

Submission status: Time Limit Exceeded

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

w = [[int(i) for i in range(ab[u][0],ab[u][1])] for u in range(m)]
ans = 0
#print(w)
import collections
while True:
  d = [e for row in w for e in row]
  #print(d)
  if d == []:
    print(ans)
    break
  else:
    # collections.Counter使用時は宣言する
    c = collections.Counter(d)
    t = c.most_common()[0][0]
    ans += 1
    w = [i for i in w if not t in i]
    #print(w)

Submission status: Time Limit Exceeded

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

ab.sort(key = lambda x: x[1])
bridge = [False] * n
ans = 0
for i in range(m):
    sub = bridge[ab[i][0] : ab[i][1]]
    if True in sub:
        continue
    else:
        bridge[ab[i][1] - 1] = True
        ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    ab_list = [tuple(map(int, input().split())) for _ in range(m)]
    deleted = [False for _ in range(n-1)]
    for ab in sorted(ab_list, key = itemgetter(1)):
        if True in set(deleted[ab[0]-1:ab[1]-1]):
            continue
        else:
            deleted[ab[1]-2] = True
    print(len([b for b in deleted if b is True]))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    ab_list = [tuple(map(int, input().split())) for _ in range(m)]
    deleted = [False for _ in range(n-1)]
    for ab in sorted(ab_list, key = itemgetter(1)):
        if True in deleted[ab[0]-1:ab[1]-1]:
            continue
        else:
            deleted[ab[1]-2] = True
    print(len([b for b in deleted if b is True]))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

# 取り除く橋についてbit全探索
bridge_cnt = N - 1
for i in range(2 ** bridge_cnt):

    bridges = [True] * bridge_cnt
    for j in range(bridge_cnt):
        if (i >> j) & 1:
            bridges[bridge_cnt - 1 - j] = False

    # war_pairs間でたどり着けないか確認
    is_unreachable_all = True
    for (a, b) in war_pairs:
        bridges_between_ab = bridges[a - 1:b - 1]
        if all(bridges_between_ab):
            is_unreachable_all = False

    if is_unreachable_all:
        print(bridges.count(False))
        exit()

Submission status: Time Limit Exceeded

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

  flag = True
  tmp = {int(i) for i in range(a, b)}
  for i in range(len(ans_list)):
    if ans_list[i] & tmp != set([]):
      ans_list[i] = ans_list[i] & tmp
      flag = False
  if flag:
    ans_list.append(tmp)
print(len(ans_list))

Submission status: Time Limit Exceeded

Solution code:
def main():
  n,m=map(int,input().split())
  l=[True for _ in range(n+1)]
  q=[]
  for _ in range(m):
    a,b=map(int,input().split())
    q.append([b,a])
  q=sorted(q)
  count=0

  for y,x in q:
    if all(l[x:y])==False:
      continue
    else:
      l[y-1]=False
      count+=1

  print(count)

if __name__=="__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
l=[True for _ in range(n+1)]
q=[]
for _ in range(m):
  a,b=map(int,input().split())
  q.append([b,a])
q=sorted(q)
count=0

for y,x in q:
  if all(l[x:y])==False:
    continue
  else:
    l[y-1]=False
    count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(x) for x in input().split()]
lst = [[int(x) for x in reversed(input().split())] for i in range(M)]
lst.sort()
bridge = [True] * N

def connected(a, b):
    for i in range(a, b):
        if bridge[i] == False:
            return False
    return True

def solve():
    res = 0
    for l in lst:
        a, b = l
        if connected(b, a):
            bridge[a - 1] = False
            res += 1
    return res

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

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(x) for x in input().split()]
lst = [[int(x) for x in reversed(input().split())] for i in range(M)]
lst.sort()
bridge = [True] * N

def connected(a, b):
    for i in range(a, b):
        if bridge[i] == False:
            return False
    return True

def solve():
    res = 0
    for l in lst:
        a, b = reversed(l)
        if connected(a, b):
            bridge[b - 1] = False
            res += 1
    return res

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

Submission status: Time Limit Exceeded

Solution code:
import sys
n,m = map(int,input().split())
lis = [list(map(int,input().split())) for _ in range(m)]
fin_count = 0
flag = True
while flag == True:
    counter = [0]*(n-1)
    for l in lis:
        for i in range(l[0]-1,l[1]-1):
            counter[i] += 1
    #print(counter)
    #print('↑counter')
    #print(counter.index(max(counter)))
    mi = counter.index(max(counter))
    #print(mi)
    #print('入る前')
    fin_count += 1
    tmp = []
    for li,l in enumerate(lis):
        #print(lis)
        #print('↑lis')
        #print(l[0]-1,mi,l[1]-1,l)
        #print('↑l[0]-1,mi,l[1]-1,l)')
        if l[0]-1 > mi or mi >= l[1]-1:
            tmp.append(l)
            #print(lis)
            #print('↑削除後')
    if len(tmp) == 0:
        print(fin_count)
        sys.exit()
    lis = tmp

Submission status: Time Limit Exceeded

Solution code:
def ck(a,b,arr):
  if sum(arr[a:b]) == b - a:
    return 1
  else:
    return 0

N,M=map(int,input().split())
List=[list(map(int,input().split())) for i in range(M)]
List_2 = [0] * M
arr = [1] * N

for i in range(M):
  a = List[i][1]
  b = List[i][0]
  List_2[i] = [a,b]
  
List_2.sort()
  
for i in range(M):
  a = List_2[i][1]
  b = List_2[i][0]

  hantei = ck(a,b,arr)
  if hantei == 1:
    arr[b-1] = 0
  
print(int(N - sum(arr)))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ab_lis =[]
for i in range(m):
    a,b = map(int, input().split())
    ab_lis.append([b,a])
ab_lis.sort()
count = 0
bridge = [1]*(n-1)
for lis in ab_lis:
    b = lis[0]
    a = lis[1]
    if sum(bridge[a-1:b-1])/len(bridge[a-1:b-1]) == 1 and b >= 2:
        bridge[b-2] = 0
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
requests = [tuple(map(int, input().split())) for _ in range(M)]
requests.sort(key=lambda x: x[1])
connects = [1] * N
for a, b in requests:
    if all(connects[a:b]):
        connects[b-1] = 0
print(connects.count(0))

Submission status: Time Limit Exceeded

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()))
    ab.append([a-1,b-1])
ab.sort(key = lambda ab:ab[1])
count = 0
while ab:
    a,b = ab.pop(0)
    for i in range(len(ab)-1,-1,-1):
        if ab[i][0] < b:
            ab.remove(ab[i])
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
bridge=[0]*(n)
AB=[list(map(int,input().split())) for i in range(m)]
AB.sort(key=lambda x:x[1])
cnt=0
for i in range(m):
    p,q=AB[i]
    p-=1
    q-=1
    flag=0
    for j in range(p,q):
        if bridge[j]==1:
            flag=1
            break
    if flag:
        continue
    else:
        bridge[q-1]=1
        cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
bridge=[0]*(n)
AB=[list(map(int,input().split())) for i in range(m)]
AB.sort(key=lambda x:x[1])
cnt=0
for i in range(m):
    p,q=AB[i]
    p-=1
    q-=1
    flag=0
    for j in range(p,q):
        if bridge[j]==1:
            flag=1
    if flag:
        continue
    else:
        bridge[q-1]=1
print(sum(bridge))

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
bridge=[0]*(n)
AB=[list(map(int,input().split())) for i in range(m)]
AB.sort(key=lambda x:x[1])
cnt=0
for i in range(m):
    p,q=AB[i]
    p-=1
    q-=1
    flag=0
    for j in range(p,q):
        if bridge[j]==1:
            flag=1
    if flag:
        continue
    else:
        bridge[q-1]=1
print(sum(bridge))

Submission status: Time Limit Exceeded

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

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


count = 0
while True:
    check = [0]* n

    for i in l:
        a,b = i

        for j in range(a,b):
            check[j] += 1
            


    index = check.index(max(check))
    count += 1
    dellist = []
    for i in range(len(l)):
        a,b = l[i][0],l[i][1]
        if index in range(a,b):
            dellist.append(i)
    num = 0
    for i in dellist:
        del l[i-num]
        num += 1

    if l == []:
        break

print(count)

Submission status: Time Limit Exceeded

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

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

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

ans = 0
pre = 0

while qp:
    a,b = qp.pop(0)
    if pre<a:
        ans += 1
        pre = b-1
print(ans)

Submission status: Time Limit Exceeded

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

import numpy as np
a=np.zeros(M).astype(int)
b=np.zeros(M).astype(int)

check=np.zeros(M).astype(int)

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

bridge=np.zeros(N-1).astype(int)
  
while(sum(check)!=M):
  cnt=np.zeros(N-1).astype(int)
  for i in range(M):
    if check[i]:
      continue
    cnt[a[i]:b[i]]+=1
    
  
  #カウント最大の橋を切る
  val=0
  for i in range(N-1):
    if val<cnt[i]:
      val=cnt[i]
      idx=i
  bridge[idx]=1
  for i in range(M):
    if check[i]:
      continue
    for j in range(a[i],b[i]):
      if bridge[j]:
        check[i]=1
print(sum(bridge))

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
dem=[]
li=[]
isl=[0]*(n-1)
ans=0
for i in range(m):
    a,b=map(int,input().split())
    dem.append([a,b])
while len(dem)!=0:   
    for j in range(len(dem)):
        for k in range(dem[j][0],dem[j][1]):
            isl[k-1]+=1
        x=max(isl)
        y=isl.index(x)+1
    for l in range(len(dem)):
        if dem[l][0]>y or dem[l][1]<=y:
          li.append([dem[l][0],dem[l][1]])
    dem=li
    ans+=1
    isl=[0]*(n-1)  
    li=[]
      
print(ans)

Submission status: Time Limit Exceeded

Solution code:


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

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

        return 1 + SectionScheduling(array)
    else:
        return 0

print(SectionScheduling(L))

Submission status: Time Limit Exceeded

Solution code:

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

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

        return 1 + SectionScheduling(array)
    else:
        return 0

print(SectionScheduling(L))

Submission status: Time Limit Exceeded

Solution code:

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

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

        return 1 + SectionScheduling(array)
    else:
        return 0

print(SectionScheduling(L))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
req = [tuple(map(int, input().split())) for _ in range(M)]
req.sort(key=lambda x: x[1])

res = 0
i = 1
while i <= N:
    remain = [x for x in req if i <= x[0]]
    if len(remain):
        i = remain[0][1]
        res += 1
    else:
        break

print(res)

Submission status: Time Limit Exceeded

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

rmvd = [1]*(n-1)
for a, b in ab:
    if all(rmvd[a-1:b-1]): rmvd[b-2] = 0
print(n-1 - sum(rmvd))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
demand_list = []
for _ in range(M):
    ai, bi = map(int, input().split())
    demand_list.append([ai, bi])

# ソート
demands = sorted(demand_list, key=lambda d: d[1])

# 分断開始 切断されている橋は1で表現される
cut_bilagge_list = [0 for _ in range(N)]

for demand in demands:
    # すでに分断されているのかをチェックする
    if len([1 for i in cut_bilagge_list[demand[0] - 1:demand[1] - 1] if i == 1]) > 0:
        continue

    # 分断されていないので bi - 2の橋を切断する
    cut_bilagge_list[demand[1] - 2] = 1


print(sum(1 for bilagge in cut_bilagge_list if bilagge == 1))

Submission status: Time Limit Exceeded

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

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

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

#print(l_target)

cut_pos=[]
for target in l_target:
    is_ok=False
    for pos in cut_pos:
        if (target[0]<pos<target[1]):
            is_ok=True
            break
    
    if(not is_ok):
        cut_pos.append(target[1]-0.5)

print(len(cut_pos))

Submission status: Time Limit Exceeded

Solution code:
import heapq as h
import math
import numpy as np
import copy
 
n,m = map(int,input().split())
# l = list(map(lambda x:-int(x),input().split()))
ll = []
maxright = 0
for _ in range(m):
    a,b = map(int,input().split())
    ll.append([a,b-1])
    maxright = max(b-1,maxright)
cnt = 0
while ll:
    cnt += 1
    counts = [0]*maxright
    for l in ll:
        for num in range(l[0],l[1]+1):
            counts[num-1] = counts[num-1] + 1
    mostnum = np.argmax(counts)+1
    old = copy.copy(ll)
    ll = []
    for l in old:
        if (l[0] <= mostnum) and (mostnum <= l[1]):
            continue
        ll.append(l)
print(cnt)