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:
# ABC103D_IslandsWar.py

import operator

"""
区画スケジューリング
まず、(ai, bi) の組を bi について昇順にソートします。ソートした順に、以下を行う。
• 既にその要望を満たしている場合、何もしない。
• 要望を満たしていない場合、bi − 1 番目の島と bi 番目の島を接続する橋を取り除く。
TLE に注意
"""

n, m = map(int, input().split())
ms = [tuple(map(int, input().split())) for i in range(m)]
bridges = set()
ms2 = sorted(ms, key=operator.itemgetter(1))

for i in range(m):
    if any(x in bridges for x in range(ms2[i][0], ms2[i][1])):
        pass
    else:
        bridges.add(ms2[i][1]-1)

if __name__ == "__main__":
    print(len(bridges))

Submission status: Time Limit Exceeded

Solution code:
# ABC103D_IslandsWar.py

import operator

"""
区画スケジューリング
まず、(ai, bi) の組を bi について昇順にソートします。ソートした順に、以下を行います。
• 既にその要望を満たしている場合、何もしない。
• まだその要望を満たしていない場合、西から bi − 1 番目の島と bi 番目の島を接続する橋を取り除く。
"""

n, m = map(int, input().split())
ms = [tuple(map(int, input().split())) for i in range(m)]
bridges = set()
ms2 = sorted(ms, key=operator.itemgetter(1))

for i in range(m):
    ms2i = tuple(range(ms2[i][0], ms2[i][1]))
    ms2i2 = [x in bridges for x in ms2i]
    if any(ms2i2):
        pass
    else:
        bridges.add(ms2[i][1]-1)

if __name__ == "__main__":
    print(len(bridges))

Submission status: Time Limit Exceeded

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

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])
q = deque(ikusa_L)
q_1 = deque(q)
count = 0
while len(q_1) > 0:
    q_1 = deque([])
    a = q.popleft()
    cut = a[1]
    #print(cut,'aa')
    count += 1
    pop_count = 0
    for i in q:
        if not(i[0] < cut):
            q_1.append(i)
    q = deque(q_1)
    #print(q_1)

print(count)

Submission status: Time Limit Exceeded

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

def main():
    N, M = map(int, input().split())
    ab = sorted([list(map(int, input().split())) for i in range(M)], key = lambda x:x[1])
    bridge = [True] * (N-1)
    count = 0
    start = -1
    for a, b in ab:
        a -= 1; b -= 1;
        if a > start:
            ok = True
            for i in range(a, b):
                if not bridge[i]:
                    ok = False
                    break
            if ok:
                start = a
                bridge[b-1] = False
                count += 1
    print(count)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

def main():
    N, M = map(int, input().split())
    ab = sorted([list(map(int, input().split())) for i in range(M)], key = lambda x:x[1])
    # print(ab)
    bridge = [True] * (N-1)
    count = 0
    for a, b in ab:
        a -= 1; b -= 1;
        ok = True
        for i in range(a, b):
            if not bridge[i]:
                ok = False
                break
        if ok:
            bridge[b-1] = False
            count += 1
    print(count)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, math, itertools, bisect, copy, re
from collections import Counter, deque, defaultdict

# from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
# from functools import reduce
# from math import ceil, floor, log10, log2, factorial
# from pprint import pprint

INF = float('inf')
MOD = 10 ** 9 + 7
EPS = 10 ** -7
sys.setrecursionlimit(1000000)

# N = int(input())
# N,M = [int(x) for x in input().split()]
# V = [[0] * 100 for _ in range(100)]
# A = [int(input()) for _ in range(N)]
# DP = [[0] * 100 for _ in range(100)]
# DP = defaultdict(lambda: float('inf'))

N, M = [int(x) for x in input().split()]
AB = []
for _ in range(M):
    a, b = [int(x) for x in input().split()]
    AB.append((a - 1, b - 2))

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

cnt = 0
while len(AB) != 0:
    cut = AB[0][0]
    # print("AB:{}, cut:{}".format(AB, cut))
    # print(AB)
    newAB = []
    for (a,b) in AB:
        if a <= cut and cut <= b:
            pass
        else:
            newAB.append((a, b))
    AB = newAB
    cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

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

for i in range(M):
  if 0 in state[br[i][0]-1:br[i][1]-1]:
    continue
  else:
    state[br[i][1]-2] = 0
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
b=[]
for i in range(m):
    b.append(list(map(int,input().split())))
    b.sort(key=lambda x:x[1])
time=0
count=0
for k in range(len(b)):
    if b[k][0]>=time:
                time=b[k][1]
                count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
import copy
import numpy as np


def main():
    n, m = [int(x) for x in input().split()]
    path = set([tuple([a, b]) for a in range(1, n + 1) for b in range(a + 1, n + 1)])
    war = sorted([tuple(int(e) for e in input().split()) for _ in range(m)], key=lambda x: x[1] - x[0])
    ans = 0
    for w in war:
        if w in path:
            ans += 1
            pathnext = copy.deepcopy(path)
            for p in path:
                if p[0] <= w[0] < p[1] or p[0] < w[1] <= p[1]:
                    pathnext.remove(p)
            path = pathnext
    print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
ab = [LIST() for _ in range(M)]

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

tmp = ab[0][1]
count = 1
for i in range(M):
	a, b = ab.pop(0)
	# print(a, b)
	if a < tmp:
		continue
	else:
		tmp = b
		count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
def judge(m_set, res_set):
  flag = 1
  if (m_set & res_set) == set():
      flag = 0
  if flag == 1:
    return True
  else:
    return False

n, m = map(int, input().split())
m_list = [list(map(int, input().split())) for i in range(m)]
m_list = sorted(m_list, key=lambda x: x[1], reverse=False)
m_set_list = list(map(lambda x:set([i for i in range(x[0],x[1])]), m_list))
remain_list = [1] * m

res_set = set()
count = 0
for i, rem in enumerate(remain_list):
  if rem == 1:
    res_set.add(m_list[i][1]-1)
    count += 1
    for i, rem in enumerate(remain_list):
      if rem == 1:
        if judge(m_set_list[i], res_set):
          remain_list[i] = 0
print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import copy
n, m = [int(i) for i in input().split()]
a=[]
b=[]
for i in range(m):
    x1, y1 = [int(i) for i in input().split()]
    a.append(x1)
    b.append(y1)

ans = 0
while True:
    bridge = np.array([0]*(n-1))
    for i in range(len(a)):
        bridge[a[i]-1:b[i]-1] += 1
    r = bridge.argmax() + 1

    for i,an,bn in zip(range(len(a)),a,b):
        if an <= r <= bn-1:
            a[i]=0
            b[i]=0

    ans += 1
    if len(set(a))==1 and a[0]==0:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
*D, = open(0)
n, m = map(int, D[0].split())
edges = [list(map(int, it.split())) for it in D[1:]]
edges = sorted(edges, key=lambda x:x[1])

cnt = 0
while len(edges)>0:
    cnt += 1
    new_edges = []
    bridge = edges[0][1]
    for it in edges:
        if it[0]>=bridge:
            new_edges.append(it)
            
    edges = new_edges
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import operator


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):

    AB = list(zip(a,b))
    AB.sort(key=operator.itemgetter(1))

    db = []
    for a,b in AB:
        bAppend = True
        for i in range(a,b):
            if i in db:
                bAppend = False
                break
        if bAppend:
            db.append(b-1)

    print(len(db))


    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]" 
    b = [int()] * (M)  # type: "List[int]" 
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

N, M = LI()
demands = []
for i in range(M):
    demands.append(LI())

demands = sorted(demands, key=lambda x: x[1])
demands_met_flag = [False]*len(demands)

def main():
    counter = 0
    for i in range(len(demands)):
        if demands_met_flag[i] == True: continue
        demand = demands[i]
        demands_met_flag[i] = True
        counter += 1
        deleting_bridge = demand[1]-1
        for j in range(i, len(demands)):
            if demands_met_flag[j] == True: continue
            if demands[j][0] <= deleting_bridge:
                demands_met_flag[j] = True

    print(counter)

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

N, M = LI()
demands = []
for i in range(M):
    demands.append(LI())

demands = sorted(demands, key=lambda x: x[1])

counter = 0
while demands:
    demand = demands.pop(0)
    counter += 1
    deleting_bridge = demand[1]-1
    delete_flag = []
    for i, d in enumerate(demands):
        if d[0] <= deleting_bridge:
            delete_flag.append(i)
    for i in reversed(delete_flag):
        demands.pop(i)

print(counter)

Submission status: Time Limit Exceeded

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

import itertools
bridge = []
for y in range(n-1):
    for x in itertools.combinations([x+1 for x in range(n-1)],y+1):
        bridge.append(x)
        
import numpy as np
flag = 0
for x in bridge:
    all_result = [0 for x in range(m)]
    for y in x:
        result = []
        for route in youbou:
            if (y>=int(route[0]))&(y+1<=int(route[1])):
                result.append(1)
            else:
                result.append(0)
        all_result += np.array(result)
    if 0 not in all_result:
        print(len(x))
        break

Submission status: Time Limit Exceeded

Solution code:
# https://atcoder.jp/contests/abc103/tasks/abc103_d
import sys

def solve():
    pairs.sort(key=lambda pair: pair[1])
    done = set()
    cnt = 0
    i = 0
    while i < m:
        if i in done:
            i += 1
            continue
        _, b0 = pairs[i]
        cnt += 1
        done.add(i)
        for j, (a, _) in enumerate(pairs[i+1:], start=(i+1)):
            if a < b0:
                done.add(j)
    return cnt

n, m = map(int, input().split())
pairs = [tuple(int(c) for c in input().split()) for _ in range(m)]
print(n, pairs, file=sys.stderr)
print(solve())

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

import copy
import collections

fights = AB[:]

fights = sorted(fights)

bridges = []
for a,b in fights:
    bridges.append(
        [x for x in range(a,b)]
    )

ans = 0
while True:
    if not bridges:
        break
    else:
        ans += 1
    
    flat_b = []
    for b in bridges:
        flat_b = flat_b + b

    #print(flat_b)
    max_n = collections.Counter(flat_b).most_common()[0][0]
    
    next_bridges = []
    for b in bridges:
        if max_n in b:
            continue
        else:
            next_bridges.append(b[:])
    bridges = copy.deepcopy(next_bridges)

print(ans)

Submission status: Time Limit Exceeded

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

import heapq

q=[]
heapq.heapify(q)
i=0
j=0
ans=0
while True:
    try:
        if(q[0]==i):
            ans+=1
            q=[]
            heapq.heapify(q)
    except:
        pass
    while j<len(A) and A[j][0]==i :
        heapq.heappush(q,A[j][1])
        j+=1

    i+=1
    if(j>=len(A)):
        break
if(len(q)>0):
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

cut_count = 0
while True:
    summ = [ 0 for _ in range(N)]
    for b in bridge:
        for i in range(N):
            if (b[0] - 1) <= i < (b[1] - 1):
                summ[i] += 1
#     print(summ, bridge)
    maxx = max(summ)
    if maxx < 2:
        print(str(len(bridge) + cut_count))
        break
    else:
        cut_count += 1
        ind = summ.index(maxx)
        new_bridge = []
        for b in bridge:
            for i in range(N):
                if (b[0] - 1) <= ind < (b[1] - 1):
                    pass
                else:
                    new_bridge.append(b)
                    break
        bridge = new_bridge

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())
divide_list = []
for i in range(M):
    newleft,newright = map(int,input().split())
    if i == 0:
        divide_list.append([newleft,newright])
    else:
        for divide in divide_list:
            left = divide[0]
            right = divide[1]
            if newleft >= right or newright <= left:
                divide_list.append([left,right])
            elif left <= newleft and newright <= right:
                divide_list.remove(divide)
                divide_list.append([newleft,newright])
            elif newleft <= left and right <= newright:
                pass
            elif left < newleft < right and right < newright:
                divide_list.remove(divide)
                divide_list.append([newleft,right])
            elif newleft < left < newright and newright < right:
                divide_list.remove(divide)
                divide_list.append([left,newright])
            else:
                print(divide,newleft,newright)
print(len(divide_list))

Submission status: Time Limit Exceeded

Solution code:
N,M = list(map(int,input().split(' ')))
 
abp = []
 
for i in range(M):
	a,b = list(map(int,input().split(' ')))
	abp.append([a,b])
 
abp.sort(key=lambda x:x[1])
 
dbridge = []
 
def check(a,b,dbridge):
	for i in range(a,b):
		if i in dbridge:
			return False
	return True

for a,b in abp:
	if check(a,b,dbridge):
		dbridge.append(b-1)
	else:
		pass
 
print(len(dbridge))

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

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

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

ab.sort(key=itemgetter(1))

fall = [0 for i in range(n-1)]

for i in range(len(ab)):
    flag = True
    for j in range(ab[i][0],ab[i][1]):
        if fall[j]:
            flag = False
            break
    if flag:
        fall[ab[i][1]-1] = 1

print(fall.count(1))

Submission status: Time Limit Exceeded

Solution code:
import heapq
N, M = map(int, input().split())
data = []
for i in range(M):
    a, b = map(int, input().split())
    heapq.heappush(data, (b, a))
bridge = [1] * N

for i in range(M):
    b, a = heapq.heappop(data)
    if sum(bridge[a:b]) == b - a:
        bridge[b-1] = 0

print(N-sum(bridge))

Submission status: Time Limit Exceeded

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

bridge = [1] * N

for a, b in data:
    if sum(bridge[a:b]) == b - a:
        bridge[b-1] = 0

print(N-sum(bridge))

Submission status: Time Limit Exceeded

Solution code:
#方針　もっとも近い敵でない島の集まりを調べると区間スケジュール問題となる。
#一列に並んでいるので飛んだ島とは繋げない
#橋の取り壊しの最小値というが、分割としてはもっとも番号の若いものまでしか無理である。
#最近接の敵である島の数字をもつ配列を考える。
N,M = (int(_) for _ in input().split())
mostNeightborOpponent = [N+1 for _ in range(N)]
#print(mostNeightborOpponent)
for i in range(M):
    a,b = (int(_) for _ in input().split())
    if mostNeightborOpponent[a-1] > b:
        mostNeightborOpponent[a-1] = b
#print(mostNeightborOpponent)
#island:・・・島|島・・・の右の島のindex
island = 1
bridgeWillBreak = 0

while island < N:
    minOpIsland = mostNeightborOpponent[island-1]
    for i in range(island-1,N):
        if minOpIsland > mostNeightborOpponent[i]:
            minOpIsland=mostNeightborOpponent[i]
    #print(minOpIsland)
    island = minOpIsland
    if island > N:
        break
    bridgeWillBreak += 1

print(bridgeWillBreak)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == '__main__':
	islands_count, demands_count = list(map(int, input().split()))
	demands = []
	bridges = [True for _ in range(islands_count - 1)]

	for i in range(demands_count):
		demand = list(map(int, input().split()))
		demands.append(demand)

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

	for demand in demands:
		is_disconnected = False
		for bridge in range(demand[0] - 1, demand[1] - 1):
			if not bridges[bridge]:
				is_disconnected = True
				break
		if not is_disconnected:
			bridges[demand[1] - 2] = False
	print(bridges.count(False))

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
l = [tuple(map(int, input().split())) for _ in range(m)]
l.sort(key=lambda x:x[1],reverse = True)
dec = 0
while l:
  a = l.pop()
  dec += 1
  l = [i for i in l if not (i[0] < a[1] <= i[1])]
print(dec)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a = []
for i in range(m):
    req = [int(i) for i in input().split()]
    a.append(req)
a.sort(key = lambda x: x[1])
b = []
for i in a:
    b_range = set(list(range(i[0], i[1])))
    b_set = set(b)
    if len(b_set & b_range) == 0:
        b.append(i[1] - 1)
print(len(b))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
a_b = sorted([list(map(int, input().split())) + [0] for _ in range(M)])
ans = 0
for i in range(M):
    k = M - i - 1
    if a_b[k][2]:
        continue
    a_b[k][2], c = 1, a_b[k][0]
    for j in range(k):
        if a_b[j][0] <= c < a_b[j][1]:
            a_b[j][2] = 1
    ans += 1
print(ans)

Submission status: Time Limit Exceeded

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
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007
sys.setrecursionlimit(1000000)

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    n,m = LI()
    a = LIR(m)
    d = [0 for i in range(n+1)]
    a.sort()
    for i in range(m):
        d[a[i][0]] = i
    for i in range(n):
        d[i+1] = max(d[i],d[i+1])
    for i in range(n):
        a.sort(key = lambda x:x[1])
        mi = a[0][1]-1
        l = d[mi]-(m-len(a))
        a.sort(key = lambda x:x[0])
        a = a[l+1:]
        if len(a) == 0:
            print(i+1)
            quit()
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

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

Submission status: Time Limit Exceeded

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
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007
sys.setrecursionlimit(1000000)

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    n,m = LI()
    a = LIR(m)
    for i in range(n):
        a.sort(key = lambda x:x[1])
        mi = a[0][1]
        l = 0
        r = len(a)
        a.sort(key = lambda x:x[0])
        while r-l>1:
            j = (l+r)//2
            if a[j][0] < mi:
                l = j
            else:
                r = j
        a = a[l+1:]
        if len(a) == 0:
            print(i+1)
            quit()
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

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

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
a = [list(map(int,input().split())) for _ in range(m)]
a = sorted(a,key=lambda x:x[1])
ans = [0]
for a_ in a:
    for i,k in enumerate(ans):
        if a_[0]<k and a_[1]>=k:
            break
        elif i==len(ans)-1:
            ans.append(a_[1])
            break
print(len(ans)-1)

Submission status: Time Limit Exceeded

Solution code:
from copy import copy
from collections import deque

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

"""
N=10**5
M=10**5
ab=[]
for i in range(1,N):
    ab.append([i,i+1])
"""
AB=copy(ab)
ab.sort(key=lambda x :x[1])
AB.sort()
ab=deque(ab)
AB=deque(AB)
num=0
while(ab):
    p=ab.popleft()
    AB.remove(p)
    num+=1
    e=p[1]
    Q=copy(AB)
    for I in AB:
        if I[0]<e:
            Q.remove(I)
            ab.remove(I)
        else:
            break
    AB=Q
print(num)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M=map(int,input().split())
ab=[]
for i in range(M):
    a,b=map(int,input().split())
    ab.append([a,b])

ab.sort(key=lambda x :x[1])
ab=deque(ab)
num=0
while(ab):
    p=ab.popleft()
    num+=1
    e=p[1]
    q=deque()
    for i in range(len(ab)):
        if ab[i][0]>=e:
            q.append(ab[i])
    ab=q
print(num)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
ab=[]
for i in range(M):
    a,b=map(int,input().split())
    ab.append([a,b])
ab.sort(key=lambda x :x[1])
num=0
while(ab):
    p=ab.pop(0)
    num+=1
    e=p[1]
    for i in reversed(range(len(ab))):
        if ab[i][0]<e:
            ab.pop(i)
print(num)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
lst = [tuple(map(int, input().split())) for _ in range(M)]
lst.sort(key=lambda x: x[1])
bridge = [False for _ in range(N - 1)]
for war in lst:
    if True not in bridge[war[0] - 1:war[1] - 1]:
        bridge[war[1] - 2] = True
print(bridge.count(True))

Submission status: Time Limit Exceeded

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

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

removed = []

for a,b in _input:
    flag = False
    for i in removed:
        if a <= i < b:
            flag = True
    if not flag:
        removed.append(b-1)

print(len(removed))

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
bridges = [1]*N
islandswar = [[] for _ in range(N+1)]
for i in range(M):
    a,b = map(int,input().split())
    islandswar[b].append(a)
count = 0

def check(a,b):
    for i in range(a,b):
        if bridges[i] == 0:
            return False
    return True
    

for i in range(2,N+1):
    for j in range(0,len(islandswar[i])):
        if check(islandswar[i][j],i):
            bridges[i-1] = 0
            count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ab = []
for i in range(m):
  ab.append(list(map(int, input().split())))
count = 0
while len(ab) > 0:
  c = float('inf')
  for i in range(len(ab)):
    if ab[i][1] < c:
      c = ab[i][1]
  count += 1
  tmp = []
  for i in range(len(ab)):
    if ab[i][0] >= c:
      tmp.append(ab[i])
  ab = tmp
print(count)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(m)]
lst = sorted(lst, key=lambda x:x[0], reverse=False)
ans = 0
#カバーできてないもののうち終了時間の最も早いものを取る
while len(lst)>0:
    ans+=1
    rest = []
    et = min(lst, key=lambda x:x[1])[1]
    flag = False
    for i in range(len(lst)):
        if lst[i][0]>=et:
            lst=lst[i:]
            flag=True
            break
    if not flag:
        break
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 = sorted(lst, key=lambda x:x[1], reverse=False)
ans = 0
#カバーできてないもののうち終了時間の最も早いものを取る
while len(lst)>0:
    ans+=1
    rest = []
    et = lst[0][1]
    for l in lst:
        if l[0]>=et:
            rest.append(l)
    lst = rest
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class Stub:
    @classmethod
    def input(self):
        Stub.current += 1
        return Stub.data.splitlines()[Stub.current]

    current = -1
    data = '''\
9 5
1 8
2 7
3 5
4 6
7 9
'''


def read_input():
    # return Stub.input()
    return input()


def parse_input():
    island, request = tuple(map(int, read_input().split()))
    requests = [
        tuple(map(lambda s: int(s) - 1, read_input().split()))
        for i in range(request)
    ]
    return Request(island, request, requests)


class Request:
    def __init__(self, island, request, requests):
        self.island = island
        self.request = request
        self.requests = requests

    def solve(self):
        bridge = 0
        self.requests.sort(key=(lambda r: r[1]))
        while len(self.requests) > 0:
            b = self.requests[0]
            bridge += 1
            self.requests = list(filter(lambda r: r[0] >= b[1], self.requests))
        return bridge


request = parse_input()
print(request.solve())

Submission status: Time Limit Exceeded

Solution code:
class Stub:
    @classmethod
    def input(self):
        Stub.current += 1
        return Stub.data.splitlines()[Stub.current]

    current = -1
    data = '''\
9 5
1 8
2 7
3 5
4 6
7 9
'''


def read_input():
    # return Stub.input()
    return input()


def parse_input():
    island, request = tuple(map(int, read_input().split()))
    requests = [
        tuple(map(lambda s: int(s) - 1, read_input().split()))
        for i in range(request)
    ]
    return Request(island, request, requests)


class Request:
    def __init__(self, island, request, requests):
        self.island = island
        self.request = request
        self.requests = requests

    def solve(self):
        bridge = 0
        while len(self.requests) > 0:
            b = min(self.requests, key=(lambda r: r[1]))
            bridge += 1
            self.requests = list(filter(lambda r: r[0] >= b[1], self.requests))
        return bridge


request = parse_input()
print(request.solve())

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M = map(int, input().split())
    ab = [[int(i) for i in input().split()] for _ in range(M)]
    ab = sorted(ab, key=lambda x: x[1])
    bd = ['0'] * (N - 1)
    for a, b in ab:
        if bd[a-1:b-1].count('1') == 0:
            bd[b - 2] = '1'
    print(bd.count('1'))


main()