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

demand = []
for line in sys.stdin:
  n,m = list(map(int, line.strip().split(' ')))
  demand.append(list(range(n,m)))
demand = demand[1:]

def grant(demand, destroy=0):
  cands = set()
  for d in demand:
    cands |= set(d)
  max_ = 0
  max_i = 0
  for i in cands:
    # 橋iを壊したときに叶えられる要望
    tmp = sum([1 for d in demand if i in d])
    if max_ < tmp:
      max_ = tmp
      max_i = i
  # iを壊す
  #print('destroy {}'.format(max_i))
  new_demand = [d for d in demand if max_i not in d]
  #print(new_demand)
  if len(new_demand) == 0:
    return destroy+1
  elif len(new_demand) == 1:
    return destroy+2
  return grant(new_demand, destroy+1)

destroy = 0
new_demand = [d for d in demand]
for d in demand:
  if len(d) == 1:
    # destroy d[0]
    #print('destroy {}'.format(d[0]))
    new_demand = [m for m in new_demand if d[0] not in m]
    #print(new_demand)
    destroy += 1
  if len(new_demand) == 0:
    print(destroy)
    exit()
  elif len(new_demand) == 1:
    print(destroy+1)
    exit()
print(grant(new_demand, destroy))

Submission status: Time Limit Exceeded

Solution code:
import sys

N,M = list(map(int, input().strip().split(' ')))
demand = []
for line in sys.stdin:
  n,m = list(map(int, line.strip().split(' ')))
  demand.append(list(range(n,m)))

def grant(demand, destroy=0):
  cands = set()
  for d in demand:
    cands |= set(d)
  max_ = 0
  max_i = 0
  for i in cands:
    # 橋iを壊したときに叶えられる要望
    tmp = sum([1 for d in demand if i in d])
    if max_ < tmp:
      max_ = tmp
      max_i = i
  # iを壊す
  #print('destroy {}'.format(max_i))
  new_demand = [d for d in demand if max_i not in d]
  if len(new_demand) == 0:
    print(destroy+1)
    exit()
  elif len(new_demand) == 1:
    print(destroy+2)
    exit()
  grant(new_demand, destroy+1)
    
print(grant(demand))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import copy

class Island:
  def __init__(self, N, againsts):
    self.count = len(againsts)
    self.againsts = againsts
    self._make_state()
    self.changed = 0

  def _make_state(self):
    tmp = [[1 if (i >= p[0] and i < p[1]) else 0 for i in range(N - 1)] for p in againsts]
    self.state = sum(map(np.array, tmp))
    
  def choice(self):
    max_value = max(self.state)
    return [i for i in range(len(self.state)) if self.state[i] == max_value]
  
  def cut(self, i):
    self.againsts = [p for p in self.againsts if (i < p[0] or i >= p[1])]
    self._make_state()
    self.changed += 1
    
  def get_cutting_count(self):
    return self.changed
  
N, M = list(map(int, input().split()))
againsts = []
for i in range(M):
  againsts.append(list(map(int, input().split())))

  
queue = [(Island(N, againsts), M)]
arrived = []

while True:
  state = queue.pop(0)
  island, _ = state
  tmp = island.choice()
  tmp_island = [copy.deepcopy(island) for _ in range(len(tmp))]
  [I.cut(i) for i, I in zip(tmp, tmp_island)]
  tmp_island = [(I, len(I.againsts)) for I in tmp_island]
  queue += tmp_island
  queue = sorted(queue, key=lambda x: x[0].get_cutting_count())
  if len(queue[0][0].againsts) == 0:
    break
    
print(queue[0][0].get_cutting_count())

Submission status: Time Limit Exceeded

Solution code:
import sys

N,M = list(map(int, input().strip().split(' ')))
demand = []
for line in sys.stdin:
  n,m = list(map(int, line.strip().split(' ')))
  demand.append(list(range(n,m)))

def grant(demand, destroy=0):
  #print('深さ {}'.format(destroy))
  min_destroy = None
  if len(demand) == 0:
    return destroy
  elif len(demand) == 1:
    return destroy+1
  
  for i in demand[0]:
    #print('destroy {}'.format(i))
    now_destroy = destroy+1
    now_demand = [d for d in demand if not i in d]
    d = grant(now_demand, destroy=now_destroy)
    if min_destroy:
      min_destroy = min(min_destroy, d)
    else:
      min_destroy = d
  if min_destroy:
    return min_destroy
  else:
    return destroy

print(grant(demand))

Submission status: Time Limit Exceeded

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

for i in D:
  if 1 not in L[i[0]:i[1]]:
    L[i[1]-1] = 1
    Ans += 1
print(Ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
wars = []
for _ in range(m):
    wars.append(tuple(map(int, input().split())))
wars.sort(key = lambda x: x[1])
tasks = wars[:]
distruction = 0
for l, r in wars:
    if (l, r) in tasks:
        tasks = list(filter(lambda x: x[0] >= r,tasks))
        distruction += 1
print(distruction)

Submission status: Time Limit Exceeded

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

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

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

ans = 0
while len(AB) != 0:
    cut = AB[0][1]
    newAB = []
    ans += 1
    for a, b in AB:
        if a < cut:
            pass
        else:
            newAB.append((a, b))
    AB = newAB

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
a = []
for i in range(M):
    x,y = map(int,input().split())
    a.append(list(range(x,y)))
count = 0
while a:
    b = [0] * (N)
    for i in range(len(a)):
        for j in a[i]:
            b[j] +=1
    l = 0
    for k in range(len(a)):
        if b.index(max(b)) in a[l]:
            a.remove(a[l])
        else:
            l += 1
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(M)]
for i in range(len(a)):
    a[i] = list(range(a[i][0],a[i][1]))
count = 0
while a:
    b = [0] * (N)
    for i in range(len(a)):
        for j in a[i]:
            b[j] +=1
    l = 0
    for k in range(len(a)):
        if b.index(max(b)) in a[l]:
            a.remove(a[l])
        else:
            l += 1
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
iipt=lambda:int(input())
miipt=lambda:list(map(int,input().split(" ")))
n, m=miipt()
a=[]
done=[0]*m
for i in range(m):
    a.append(miipt())
a=list(enumerate(a))
b=sorted(a, key=lambda x:x[1])
a.sort(key=lambda x:x[1][1])
c=0
while not all(done):
    j, (_, h) = a.pop(0)
    if(done[j]): continue
    d = filter(lambda x: x[1][0]<h and not done[x[0]], b)
    if d:
        c+=1
    for (i, l) in d:
        done[i]=1
print(c)

Submission status: Time Limit Exceeded

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

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

print(count)

Submission status: Time Limit Exceeded

Solution code:
def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    # ここで分割を行う
    left = arr[:mid]
    right = arr[mid:]

    # 再帰的に分割を行う
    left = merge_sort(left)
    right = merge_sort(right)

    # returnが返ってきたら、結合を行い、結合したものを次に渡す
    return merge(left, right)


def merge(left, right):
    merged = []
    l_i, r_i = 0, 0

    # ソート済み配列をマージするため、それぞれ左から見ていくだけで良い
    while l_i < len(left) and r_i < len(right):
        # ここで=をつけることで安定性を保っている
        if left[l_i] <= right[r_i]:
            merged.append(left[l_i])
            l_i += 1
        else:
            merged.append(right[r_i])
            r_i += 1

    # 上のwhile文のどちらかがFalseになった場合終了するため、あまりをextendする
    if l_i < len(left):
        merged.extend(left[l_i:])
    if r_i < len(right):
        merged.extend(right[r_i:])
    return merged
N,M = map(int,input().split(" "))
isbr = []
for i in range(M):
  isbr.append(list(map(int,input().split(" "))))
isbr = merge_sort(isbr)
rem = []
i = 0
while i < M:
  a = isbr[i][0]
  b = isbr[i][1]
  flag = 0
  while a <= b:
    if b in rem:
      flag = 1
      break
    else:
      b-=1
  if flag == 0:
    rem.append(isbr[i][1]-1)
  i+=1
print(len(rem))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

def main():
    ans = 0
    bridges = sorted(A, key=lambda b: b[1])
    while(bridges):
        rm = bridges[0][1]
        bridges = list(filter(lambda b: rm <= b[0], bridges))
        ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def main():
    ans = 0
    bridges = A
    while(bridges):
        bridges.sort(key=lambda b: b[1])
        rm = bridges[0][1]
        bridges = list(filter(lambda b: rm <= b[0], bridges))
        ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def count_lines(bridges):
    l = [0 for _ in range(N - 1)]
    for b in bridges:
        b_start = b[0] - 1
        b_end = b[1] - 1
        for i in range(b_start, b_end):
            l[i] += 1
    return l

def main():
    ans = 0
    bridges = A
    while(bridges):
        lines = count_lines(bridges)
        rm = lines.index(max(lines))
        bridges = list(filter(lambda b: rm < b[0] - 1 or b[1] - 1 <= rm, bridges))
        ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
dem = [[0, 0] for i in range(M)]
for i in range(M):
    dem[i][0], dem[i][1] = map(int, input().split())
dem.sort(key=lambda x: (x[1]))
br_flag = [False for i in range(N-1)]
count = 0
for i in range(M):
    for j in range(dem[i][1]-dem[i][0]):
        if br_flag[dem[i][0] - 1 + j]:
            break
        elif j == dem[i][1] - dem[i][0] - 1:
            br_flag[dem[i][1]-2] = True
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int,input().split())
m=[list(map(int, input().split())) for _ in range(M)]
m=sorted(m, key=lambda x: x[1])
p=0
for _ in range(M):
    if m!=[]:
        tmp=max(m)[0]
        m=[l for l in m if l[1]<=tmp]
        p+=1
    else:
        break
print(p)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def island(s, t, m):
    tt = []
    for i, j in zip(s, t):
        tt += [range(i, j)]
    i = 0
    while tt:
        i += 1
        ma = []
        for j in range(1, m + 1):
            can = []
            for iii, ttt in enumerate(tt):
                if j in ttt:
                    can += [iii]
            if len(ma) < len(can):
                ma = can
        for h in reversed(ma):
            del tt[h]
    return i

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

print(island(a, b, n))

Submission status: Time Limit Exceeded

Solution code:
islands = []
bridges = []

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
islands = []
bridges = []

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from copy import copy

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

cnt = 0
atmp = copy(a)
btmp = copy(b)

while(1):
    cnt += 1
    
    if cnt==1:
        amax = max(atmp)
    else:
        btmp = copy(btmp2)
        atmp = copy(atmp2)
        amax = max(atmp2)
        
    lb = len(btmp)
    atmp2 = []
    btmp2 = []
    
    for i in range(lb):
        if(btmp[i]<=amax):
            atmp2.append(atmp[i])
            btmp2.append(btmp[i])
    
    if len(btmp2)==0 and len(atmp2)==0:
        break
    # print(atmp2, btmp2)

    cnt += 1
    
    atmp = copy(atmp2)
    btmp = copy(btmp2)
    bmin = min(btmp2)
        
    la = len(atmp)
    atmp2 = []
    btmp2 = []
    # print(atmp, btmp)
    for i in range(la):
        if(atmp[i]>=bmin):
            atmp2.append(atmp[i])
            btmp2.append(btmp[i])

    if len(btmp2)==0 and len(atmp2)==0:
        break
    # print(atmp2, btmp2)
print(cnt)

Submission status: Time Limit Exceeded

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

while True:
    i = 0
    for _ in range(len(b)):
        if min(b) <= min(a):
            b.remove(min(b))
    if min(b) > a[i] and min(a) < min(b):
        a.remove(a[i])
    if not a:
        cnt += 1
        break
    if min(b) <= min(a):
        cnt += 1
        continue
    

print(cnt)

Submission status: Time Limit Exceeded

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

print(m())

Submission status: Time Limit Exceeded

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

print(m())

Submission status: Time Limit Exceeded

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

print(m())

Submission status: Time Limit Exceeded

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

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

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

	if len(rqs) == 1:
		cnt += 1

	print(cnt)

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
bridge = []
nums = []

for i in range(m):
    a, b = map(int, input().split())
    nums.append([a, b])
nums.sort(reverse = True)


for i in range(m):
    for j in range(nums[i][0], nums[i][1]):
        if j in bridge:
            break
    else:
       bridge.append(nums[i][0])
    
print(len(bridge))

Submission status: Time Limit Exceeded

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

for _ in range(M):
    ab_tmp.append(map(int, raw_input(). split()))

    
import collections

def cFrequentBridges(vvBridgesRemain):
    frequentBridges = collections.Counter()
    for vBridges in vvBridgesRemain:
        for b in vBridges:
            frequentBridges[b] +=1
    return frequentBridges

vvBridges = [range(a,b) for (a,b) in ab_tmp]
vvBridgesRemain = vvBridges    



k = 1
vDestroy = []
while len(vvBridgesRemain) !=0:
    b, num = cFrequentBridges(vvBridgesRemain).most_common()[0]
    vDestroy.append(b)
#    print " b = ",b
    
    vvBridgesRemain = []
    for vBridges in vvBridges:
        if not any([b in vBridges for b in vDestroy]):
            vvBridgesRemain.append(vBridges)

    if len(vvBridgesRemain) == 0:
        break
#    print "vvridgesRemain = ",vvBridgesRemain
    k +=1        
#print "Minimum destroy bridge number is ", k

print k

Submission status: Time Limit Exceeded

Solution code:
import collections

def cFrequentBridges(vvBridgesRemain):
    frequentBridges = collections.Counter()
    for vBridges in vvBridgesRemain:
        for b in vBridges:
            frequentBridges[b] +=1
    return frequentBridges



N, M = map(int, raw_input(). split())
ab_tmp = []

for _ in range(M):
    ab_tmp.append(map(int, raw_input(). split()))
    

vvBridges = [range(a,b) for (a,b) in ab_tmp]
vvBridgesRemain = vvBridges    



k = 1
vDestroy = []
while len(vvBridgesRemain) !=0:
    b, num = cFrequentBridges(vvBridgesRemain).most_common()[0]
    vDestroy.append(b)
#    print " b = ",b
    
    vvBridgesRemain = []
    for vBridges in vvBridges:
        if not any([b in vBridges for b in vDestroy]):
            vvBridgesRemain.append(vBridges)

    if len(vvBridgesRemain) == 0:
        break
#    print "vvridgesRemain = ",vvBridgesRemain
    k +=1        
#print "Minimum destroy bridge number is ", k

print k

Submission status: Time Limit Exceeded

Solution code:

from operator import itemgetter
 
n,m=map(int, input().split())
A=[]
B=[]
a=0
b=0
for i in range(m):
  a,b=map(int, input().split())
  A.append([a,b])

A.sort(key=itemgetter(1))
bri=[1 for i in range(n)] #bri[0]は1,2番目の島をつなぐ

count=0

for i in range(m):
  a=A[i][0]
  b=A[i][1]
  
  if not 0 in bri[a-1:b-1]:
    bri[b-2]=0
    count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:

from operator import itemgetter
 
n,m=map(int, input().split())
A=[]
a=0
b=0
for i in range(m):
  a,b=map(int, input().split())
  A.append([a,b])

A.sort(key=itemgetter(1))
bri=[1 for i in range(n)] #bri[0]は1,2番目の島をつなぐ

count=0

#print(A)
for i in range(m):
  #print(i)
  a=A[i][0]
  b=A[i][1]
  #print(bri[a-1:b-1])

  if not 0 in bri[a-1:b-1]:



    #print(bri[a-1:b-1])
    bri[b-2]=0
    #print(bri)
    #print(A[i])
    #print(A)
    #print(bri)
    count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:

from operator import itemgetter
 
n,m=map(int, input().split())
A=[]
a=0
b=0
for i in range(m):
  a,b=map(int, input().split())
  A.append([a,b])

A.sort(key=itemgetter(1))
bri=[1 for i in range(n)] #bri[0]は1,2番目の島をつなぐ

count=0

#print(A)
for i in range(m):
  #print(i)
  a=A[i][0]
  b=A[i][1]
  #print(bri[a-1:b-1])

  zero=0
  for j in range(a-1,b-1):
    if bri[j]==0:
      zero=1
      
  if zero==0:


    #print(bri[a-1:b-1])
    bri[b-2]=0
    #print(bri)
    #print(A[i])
    #print(A)
    #print(bri)
    count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
def main(N, M, a, b, k):
    if M == 0:
        return k
    else:
        p = min(b)
        c = []
        d = []
        for i in range(M):
            if a[i]>=p or b[i] < p:
                c.append(a[i])
                d.append(b[i])
        return main(N, len(c), c, d, k+1)

if __name__ == '__main__':
    N, M = (int(i) for i in input().split())
    a, b = [], []
    for i in range(M):
        x = input().split()
        a.append(int(x[0]))
        b.append(int(x[1]))
    
    k = 0
    print(main(N, M, a, b, k))

Submission status: Time Limit Exceeded

Solution code:
import sys
from operator import itemgetter, attrgetter

l1 = sys.stdin.readline()
l2 = sys.stdin.readlines()
lst = []
for item in l2:
	x = tuple([int(x) for x in item.strip().split()])
	lst.append(x)


lst = sorted(lst, key=itemgetter(1))
# print(lst)
lst2 = []
a = 0

for item in lst:
	# もうソートしているので
	if a >= item[0]:
		continue
	else:
		# 小さな要素を追加する
		a = item[0]
		b = item[1]
		lst2temp = []
		for y in lst2:
			# 自分を含むものがあったら消す（かわりに、ないリストを作成）
			if y[1] < b:
				lst2temp.append(y)
		lst2 = lst2temp
		lst2.append(item)

# print(lst2)


lst3 = lst2
x = lst3[0]
cnt = 0

while True:
	cnt +=1
	# 橋：x[1]-1からx[1]を、落とす
	# 左側がx[1]以上のものだけを取る
	lst3 = [y for y in lst3 if y[0] >= x[1]]
	if lst3 == []:
		break
	else:
		x = lst3[0]

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8

def sIsland(slist):
    b1, b0 = slist[0][1], slist[0][1]-1
    slist = slist[1:]
    
    rest = []
    for i in range(len(slist)):
        if not(slist[i][0] <= b0 and b1 <= slist[i][1]):
            rest.append(slist[i])
    return rest

def solve(matrix):
    n_call = 1
    deleted = sIsland(sorted(matrix, key=lambda x:x[1]))
    while True:
        if len(deleted) == 0:
            return n_call
        deleted = sIsland(deleted)
        n_call += 1
    
if __name__ == "__main__":
    
    N, M = map(int, input().split())
    matrix = []
    for i in range(M):
        matrix.append([int(x) for x in  input().split(" ")])
    print(solve(matrix))

Submission status: Time Limit Exceeded

Solution code:
a,b = list(map(int,input().split()))

input_lines = [list(map(int,input().split())) for i in range(b)]
input_lines = sorted(input_lines,key=lambda x: x[1]) #各要素において[1]に基づきソートする

c=[0]
for i in input_lines:
    p=0
    for j in c:
        if j > i[0]:
            p=1
    if p==0:
        c.append(i[1])
        
print(len(c)-1)

Submission status: Time Limit Exceeded

Solution code:
a=list(map(int,input().split()))
b=[]
c=[1]*(a[0]-1)
for i in range(a[1]):
  b.append(list(map(int,input().split())))
b=sorted(b,key=lambda b:b[1])
for i in range(a[1]):
  if i!=0 and b[i-1][0]>=b[i][0]:
    continue
  if 0 in c[(b[i][0]-1):b[i][1]]:
    continue
  else:
    c[(b[i][1])-2]=0

print(c.count(0))

Submission status: Time Limit Exceeded

Solution code:
a=list(map(int,input().split()))
b=[]
c=[1]*(a[0]-1)
for i in range(a[1]):
  b.append(list(map(int,input().split())))
b=sorted(b,key=lambda b:b[1])
for i in range(a[1]):
  if i!=0 and b[i-1][0]>b[i][0]:
    continue
  if 0 in c[(b[i][0]-1):b[i][1]]:
    continue
  else:
    c[(b[i][1])-2]=0

print(c.count(0))

Submission status: Time Limit Exceeded

Solution code:
a=list(map(int,input().split()))
b=[]
c=[1]*(a[0]-1)
for i in range(a[1]):
  b.append(list(map(int,input().split())))
b=sorted(b,key=lambda b:b[1])
for i in range(a[1]):
  if 0 in c[(b[i][0]-1):b[i][1]]:
    continue
  else:
    c[(b[i][1])-2]=0

print(c.count(0))

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
r=[]
br=[1 for i in range(n)]
c=0
for i in range(m):
    a,b=map(int,input().split())
    r.append([b,a])

def merge(array):
    mid=len(array)
    if mid>1:
        left=merge(array[:(mid//2)])
        right=merge(array[(mid//2):])
        array=[]
        while len(left)!=0 and len(right)!=0:
            if left[0][0]<right[0][0]:
                array.append(left.pop(0))
            else:
                array.append(right.pop(0))
        if len(left)!=0:
            array+=left
        elif len(right)!=0:
            array+=right
    return array        

r=merge(r)
for i in range(m):
    if sum(br[r[i][1]:r[i][0]])==r[i][0]-r[i][1]:
        br[r[i][0]-1]=0
        c+=1
print(c)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
r=[]
br=[1 for i in range(n)]
c=0
for i in range(m):
    a,b=map(int,input().split())
    r.append([b,a])
r.sort()
for i in range(m):
    if sum(br[r[i][1]:r[i][0]])==r[i][0]-r[i][1]:
        br[r[i][0]-1]=0
        c+=1
print(c)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
n, m = map(int, input().split())
bridge = [True] * (n-1)  
ab = []
for _ in range(m):
  a, b = map(int, input().split())
  ab.append((a,b))
ab = sorted(ab, key=itemgetter(1))
count = 0
for a, b in ab:
  if all(bridge[a-1:a-1 + (b-a)]):
    bridge[b-2] = False
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
n, m = map(int, input().split())
bridge = [True] * (n-1)  
ab = []
for _ in range(m):
  a, b = map(int, input().split())
  ab.append((a,b))
ab = sorted(ab, key=itemgetter(1))
count = 0
for a, b in ab:
  if all(bridge[a-1:a-1 + (b-a)]):
    bridge[b-2] = False
    count += 1
print(count)

Submission status: Time Limit Exceeded

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

# bの昇順でsort
ab.sort(key=lambda inv: inv[1])   


count = 0
while(0 < len(ab)):
    count += 1
    cutb = ab[0][1]
    # cutbで除外できる闘争を除外する
    remove_list = []
    for i in range(len(ab)):
        a, b = ab[i]
        if a <= cutb - 1 and cutb <= b:
            remove_list.append(i)

    for remove_index in reversed(remove_list):
        ab.pop(remove_index)

print(count)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = [int(i) for i in input().split()]
    bridge = []
    counter = 0
    reqs = [[int(j) for j in input().split()] for i in range(n[1])]
    reqs.sort(key=lambda x:(x[0],x[1]))
    
    for i in range(1, n[0]+1):
        if i in bridge:
            bridge = []
            counter += 1
        for j in range(len(reqs)):
            if reqs[j][0] == i:
                bridge.append(reqs[j][1])
            else:
                reqs = reqs[j:]
                break
    
    print(counter)

main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = [int(i) for i in input().split()]
    bridge = set()
    counter = 0
    reqs = [[int(j) for j in input().split()] for i in range(n[1])]
    reqs.sort(key=lambda x:(x[0],x[1]))
    
    for i in range(1, n[0]+1):
        if i in bridge:
            bridge.clear()
            counter += 1
        for j in range(len(reqs)):
            if reqs[j][0] == i:
                bridge.add(reqs[j][1])
            else:
                reqs = reqs[j:]
                break
    
    print(counter)
 
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = [int(i) for i in input().split()]
    bridge = []
    counter = 0
    reqs = [[int(j) for j in input().split()] for i in range(n[1])]
    reqs.sort(key=lambda x:(x[0],x[1]))
    prefix = 0
    
    for i in range(1, n[0]+1):
        if i in bridge:
            bridge = []
            counter += 1
        for j in range(prefix, len(reqs)):
            if reqs[j][0] == i:
                bridge.append(reqs[j][1])
            else:
                prefix = j
                break
    
    print(counter)
 
main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = [int(i) for i in input().split()]
    bridge = []
    counter = 0
    reqs = [[int(j) for j in input().split()] for i in range(n[1])]
    reqs.sort(key=lambda x:(x[0],x[1]))
    
    for i in range(1, n[0]+1):
        if i in bridge:
            bridge = []
            counter += 1
        for j in range(len(reqs)):
            if reqs[j][0] == i:
                bridge.append(reqs[j][1])
            else:
                reqs = reqs[j:]
                break
    
    print(counter)

main()

Submission status: Time Limit Exceeded

Solution code:
ab=[]

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

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

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

res=0
index=0
toremove=set()
while(1):
    for j in range(index,len(ab)):
        if ab[index][1] < ab[j][0]:
          index=j
          res+=1
          break
    if index == len(ab):break

print(res)

Submission status: Time Limit Exceeded

Solution code:
ab=[]

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

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

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

res=0
toremove=set()
while(1):
    for j in range(len(ab)):
        if ab[0][1] > ab[j][0]:
            toremove.add(ab[j])
        else:break
    if len(toremove)>0:
        for r in toremove:
            ab.remove(r)
        toremove=set()
        res+=1
    if len(ab) == 0:break

print(res)

Submission status: Time Limit Exceeded

Solution code:
ab=[]

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

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

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

res=0
toremove=set()
while(1):
    for j in range(len(ab)):
        if ab[0][1] > ab[j][0]:
            toremove.add(ab[j])
        #else:break
    if len(toremove)>0:
        for r in toremove:
            ab.remove(r)
        toremove=set()
        res+=1
    if len(ab) == 0:break

print(res)