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:
N,M = map(int, input().split())
l_table = [False for _ in range(N)]
r_table = [False for _ in range(N)]
lr_table = {}
for _ in range(M):
    l_n, r_n = map(int, input().split())
    l_table[l_n-1] = True
    r_table[r_n-1] = True
    lr_table[(l_n-1,r_n-1)] = True

ret = 0
lefts = []
for i in range(N):
    if lefts and r_table[i] and any([(left,i) in lr_table and lr_table[(left,i)] for left in lefts]):
        # print(i,lefts)
        ret += 1
        lefts = []
    if l_table[i]:
        lefts.append(i)

print(ret)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int, input().split())
l_table = [False for _ in range(N)]
lr_table = {}
for _ in range(M):
    l_n, r_n = map(int, input().split())
    l_table[l_n-1] = True
    lr_table[(l_n-1,r_n-1)] = True

ret = 0
lefts = []
for i in range(N):
    if lefts and any([(left,i) in lr_table and lr_table[(left,i)] for left in lefts]):
        # print(i,lefts)
        ret += 1
        lefts = []
    if l_table[i]:
        lefts.append(i)

print(ret)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split(' '))
sections_a = []
sections_b = []

for _ in range(M):
    a,b = map(int,input().split(' '))
    sections_a.append(a)
    sections_b.append(b)

tmp_a = [sections_a[0]]
tmp_b = [sections_b[0]]
for i in range(1,len(sections_a)):
    for j in range(i):
        if sections_a[i] < tmp_a[j]:
            tmp_a.insert(j,sections_a[i])
            tmp_b.insert(j,sections_b[i])
            break
        if j == i -1:
            tmp_a.append(sections_a[i])
            tmp_b.append(sections_b[i])
min_end = 10000000000000000
sorted_list_a = tmp_a
sorted_list_b = tmp_b
cnt = 0
for i in range(len(sorted_list_a)):
    if min_end <= sorted_list_a[i]:
        cnt += 1
        min_end = 10000000000000000
    min_end = min(min_end,sorted_list_b[i])
cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

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

tmp_list = [sections[0]]
for i in range(1,len(sections)):
    for j in range(i):
        if sections[i] < tmp_list[j]:
            tmp_list.insert(j,sections[i])
            break
        if j == i -1:
            tmp_list.append(sections[i])
min_end = 10000000000000000
sorted_list = tmp_list
cnt = 0
for section in sorted_list:
    if min_end <= section[0]:
        cnt += 1
        min_end = min_end = 10000000000000000
    min_end = min(min_end,section[1])
cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
N, M = map(int, input().split())
ab = [list(map(int, line.split())) for line in sys.stdin if line != "\n" ]
count = 0
while ab:
  count = count + 1
  max_a = max([a for a, b in ab])
  ab = [[a, b] for a, b in ab if b <= max_a]
print(count)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for ab in range(M)]
count = 0
while ab:
  count = count + 1
  max_a = max([a for a, b in ab])
  ab = [[a, b] for a, b in ab if b <= max_a]
  if not ab:
    break
  count = count + 1
  min_b = min([b for a, b in ab])
  ab = [[a, b] for a, b in ab if min_b <= a]
print(count)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for ab in range(M)]
count = 0
while ab:
  count = count + 1
  max_a = max([a for a, b in ab])
  ab = [[a, b] if b <= max_a else [0, 0] for a, b in ab]
print(count)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for ab in range(M)]
count = 0
while ab:
  count = count + 1
  max_a = 0
  for a, b in ab:
    max_a = max_a if a <= max_a else a
  ab = [[a, b] for a, b in ab if b <= max_a]
print(count)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for ab in range(M)]
count = 0
while ab:
  count = count + 1
  max_a = 0
  for a, b in ab:
    max_a = max(max_a, a)
  ab = [[a, b] for a, b in ab if b <= max_a]
print(count)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for ab in range(M)]
count = 0
while ab:
  count = count + 1
  max_a = max([a for a, b in ab])
  ab = [tmp_ab for tmp_ab in ab if tmp_ab[1] <= max_a]
print(count)

Submission status: Time Limit Exceeded

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

ans=0
while AB:
  a=AB[-1][0]
  AB=list(filter(lambda x:x[1]<=a,AB))
  ans+=1
  
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a_and_b_list = [list(map(int, input().split())) for _ in range(m)]
bridge_broken = [False for _ in range(n-1)]
a_and_b_list.sort(key=lambda x: x[1])
for a_and_b in a_and_b_list:
    if True not in bridge_broken[a_and_b[0]-1:a_and_b[1]-1]:
        bridge_broken[a_and_b[1]-2] = True
print(bridge_broken.count(True))

Submission status: Time Limit Exceeded

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

bridge=[0]*(N-1)
l=[]
for _ in range(M):
  l.append(list(map(int,input().split())))

for sl in l:
  for i in range(sl[0]-1,sl[1]-1):
    bridge[i]+=1
ans=0
# bridge=[4,6,6,4]
while max(bridge)>=1:
  m=bridge.index(max(bridge)) #m=1
  l1=copy.deepcopy(l)
  for sl in l1:
    if(m>=sl[0]-1 and m<sl[1]-1):
      for j in range(sl[0]-1,sl[1]-1):
        bridge[j]-=1
      l.remove(sl)
  ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

banned_list = []
for i in range(M):
    banned_list.append(tuple(map(int,input().split())))
banned_list = sorted(banned_list,key=lambda x:x[1])
#status = [1 for _ in range(N-1)]
status = set()
counter = 0
for i in range(M):
    a = banned_list[i][0]
    b = banned_list[i][1]
    if len([one for one in status if (one >= a-1 and one < b-1)]) == 0:
        status  |= {b-2}
        counter += 1
print(counter)

Submission status: Time Limit Exceeded

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

banned_list = []
for i in range(M):
    banned_list.append(tuple(map(int,input().split())))

banned_list = sorted(banned_list,key=lambda x:x[1])
status = [1 for _ in range(N-1)]
counter = 0
for i in range(M):
    a = banned_list[i][0]
    b = banned_list[i][1]
    if not 0 in status[a-1:b-1]:
        counter += 1
        status[b-2] = 0
print(counter)

Submission status: Time Limit Exceeded

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

banned_list = []*M
for i in range(M):
    banned_list.append(tuple(map(int,input().split())))

banned_list = sorted(banned_list,key=lambda x:x[1])
status = [1 for _ in range(N-1)]
counter = 0
for i in range(M):
    a = banned_list[i][0]
    b = banned_list[i][1]
    if sum(status[a-1:b-1]) ==  b-a:
        counter += 1
        status[b-2] = 0
print(counter)

Submission status: Time Limit Exceeded

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

banned_list = []*M
for i in range(M):
    banned_list.append(tuple(map(int,input().split())))

banned_list = sorted(banned_list,key=lambda x:x[1])
status = [True for _ in range(N-1)]
counter = 0
for i in range(M):
    a = banned_list[i][0]
    b = banned_list[i][1]
    if sum(status[a-1:b-1]) ==  b-a:
        counter += 1
        status[b-2] = False
print(counter)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ab = [[int(i) for i in input().split()] for i in range(m)]
count = 0
for i in range(m):
    ab[i].sort()
while len(ab) > 0:
    ab = sorted(ab, key = lambda x: x[1])
    end = ab[0]
    list.sort(ab, reverse=True)
    remove = ab.index(end)
    if remove >= 1:
        while ab[remove - 1][0] < end[1]:
            remove -= 1
            if remove == 0:
                break
    del ab[(remove):]
    count += 1
print(int(count))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ab = [[int(i) for i in input().split()] for i in range(m)]
count = 0
for i in range(m):
    ab[i].sort()
while len(ab) > 0:
    ab = sorted(ab, key = lambda x: x[1])
    end = ab[0]
    list.sort(ab, reverse=True)
    remove = ab.index(end)
    if remove >= 1:
        while ab[remove - 1][0] < end[1]:
            remove -= 1
            if remove == 0:
                break
    del ab[(remove):]
    count += 1
print(int(count))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ab = [[int(i) for i in input().split()] for i in range(m)]
count = 0
while len(ab) != 0:
    ab = sorted(ab, key = lambda x: x[1])
    end = ab[0][1]
    ab.sort()
    while ab[0][0] < end:
        ab.pop(0)
        if len(ab) == 0:
            break
    count += 1
print(int(count))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(m)]

AB.sort(key=lambda x:x[1])
bridge=[True]*(n-1)
for a,b in AB:
  if bridge[a-1:b-1].count(False)==0:
    bridge[b-2]=False
print(bridge.count(False))

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(m)]

AB.sort(key=lambda x:x[1])
bridge=[True]*(n-1)
for a,b in AB:
  if False not in bridge[a-1:b-1]:
    bridge[b-2]=False
print(bridge.count(False))

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
bit = int(bin(2**(n-1)-1),2)
ab = []
for _ in range(m):
  ab.append(list(map(int,input().split())))
ab.sort(key = lambda x:(x[0],x[1]))

ans = 0
for a_b in ab: 
  a_b_bit = int(bin(2**(a_b[1]-1)-2**(a_b[0]-1)),2)
  if bit & a_b_bit !=0:
    bit = bit & a_b_bit
  else:
    ans += 1
    bit = a_b_bit

print(ans+1)

Submission status: Time Limit Exceeded

Solution code:
def log(s):
    # print("| " + str(s), file=sys.stderr)
    pass


def output(x):
    print(x, flush=True)


def input_ints():
    return map(int, input().split())


def main():
    num_nodes, num_regions = tuple(input_ints())
    regions = [tuple(input_ints()) for _ in range(num_regions)]

    nodes = set()
    for r in regions:
        nodes.add(r[0])
        nodes.add(r[1])

    regions.sort(key=lambda x: (x[1] - x[0], x[0]))

    i = 0
    while i < len(regions):
        regions[0:i+1] + [r for r in regions[i+1:] if not (regions[i][0] <= r[0] and r[1] <= regions[i][1])]
        i += 1

    def solve(rs, steps):
        min_steps = 99999999999

        for i in [i for i in range(rs[0][0], rs[0][1]) if i in nodes]:
            rs2 = [r for r in rs if not r[0] <= i < r[1]]
            if rs2:
                min_steps = min(solve(rs2, steps + 1), min_steps)
            else:
                return steps

        return min_steps

    print(solve(regions, 1))


main()

Submission status: Time Limit Exceeded

Solution code:
def log(s):
    # print("| " + str(s), file=sys.stderr)
    pass


def output(x):
    print(x, flush=True)


def input_ints():
    return map(int, input().split())


def main():
    num_nodes, num_regions = tuple(input_ints())
    regions = [tuple(input_ints()) for _ in range(num_regions)]

    nodes = set()
    for r in regions:
        nodes.add(r[0])
        nodes.add(r[1])

    regions.sort(key=lambda x: (x[1] - x[0], x[0]))

    def solve(rs, steps):
        min_steps = 99999999999

        for i in [i for i in range(rs[0][0], rs[0][1]) if i in nodes]:
            rs2 = [r for r in rs if not r[0] <= i < r[1]]
            if rs2:
                min_steps = min(solve(rs2, steps + 1), min_steps)
            else:
                return steps

        return min_steps

    print(solve(regions, 1))


main()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
ab_s = [list(map(int, input().split())) for _ in range(M)]
bridges = [0] * N
ab_s = sorted(ab_s, key=lambda x: x[1])
for ab in ab_s:
  if sum(bridges[ab[0]:ab[1]]) == 0:
    bridges[ab[1]-1] = 1
print(sum(bridges))

Submission status: Time Limit Exceeded

Solution code:
import heapq

n, m = map(int, input().split())
ls = [list(map(int, input().split())) for _ in range(m)]
heapq.heapify(ls)
res = 0
r = min([r for _, r in ls])
while True:
    res += 1
    while ls:
        ll, rr = heapq.heappop(ls)
        if ll >= r:
            heapq.heappush(ls, [ll, rr])
            break
    if len(ls) > 0:
        r = min([r for _, r in ls])
    else:
        break
print(res)

Submission status: Time Limit Exceeded

Solution code:
import heapq

n, m = map(int, input().split())
ls = [list(map(int, input().split())) for _ in range(m)]
ls2 = [[r, l] for l, r in ls]
heapq.heapify(ls)
heapq.heapify(ls2)
res = 0
while ls2:
    r, l = heapq.heappop(ls2)
    res += 1
    while ls:
        ll, rr = heapq.heappop(ls)
        if ll >= r:
            heapq.heappush(ls, [ll, rr])
            break
    ls2 = []
    for l, r in ls:
        heapq.heappush(ls2, [r, l])
print(res)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    N,M = map(int, input().split())
    bridges = [False]*(N-1)
    closest_enemy = [-1]*N
    for _ in range(M):
        a,b = map(int, input().split())
        closest_enemy[b-1] = max(a-1,closest_enemy[b-1])
    for i in range(1,N):
        if closest_enemy[i] < 0: continue

        if True in bridges[closest_enemy[i]:i]:
            continue
        else:
            bridges[i-1] = True
    print(bridges.count(True))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    N,M = map(int, input().split())
    bridges = [False]*(N-1)
    battles = [[] for _ in range(N)]
    for _ in range(M):
        a,b = map(int, input().split())
        battles[b-1].append(a-1)
    for i in range(1,N):
        battle = battles[i]
        if len(battle) == 0: continue

        closest_idx = max(battle)
        if True in bridges[closest_idx:i]:
            continue
        else:
            bridges[i-1] = True
    print(bridges.count(True))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    N,M = map(int, input().split())
    bridges = [False]*(N-1)
    battles = [[] for _ in range(N)]
    for _ in range(M):
        a,b = map(int, input().split())
        battles[b-1].append(a-1)
    for i in range(1,N):
        battle = battles[i]
        if len(battle) == 0: continue

        closest_idx = max(battle)
        for bridge_idx in range(closest_idx, i):
            if bridges[bridge_idx]: break
        else:
            bridges[i-1] = True
    print(bridges.count(True))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

bb = b
e = [0]*(n-1)
h = []
for _ in range(n):
    h.append([])
count = 0
visited = []

for i, name in enumerate(bb):
    #if len(name) == 1:
    #    count += 1
    #    visited.append(i)
    #else:
        for j in name:
            e[j-1] += 1
            h[j-1].append(i)

while e != [0]*(n-1):
    g = e.index(max(e))
    for i in h[g]:
        if i in visited:
            continue
        else:
            this_bb = bb[i]
            visited.append(i)
            for j in bb[i]:
                e[j-1] -= 1
    count += 1

print(count)

Submission status: Time Limit Exceeded

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

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
l=[[0,0] for _ in range(m)]
for i in range(m):
    l[i][1],l[i][0]=map(int,input().split())

l=sorted(l)

ans=1
for _ in range(n-1):
    for i in l[1:]:
        if i[1]<l[0][0]:
            l.remove(i)
    l.remove(l[0])
    if len(l)!=0:
        ans+=1
    else:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
l=[[0,0] for _ in range(m)]
for i in range(m):
    l[i][1],l[i][0]=map(int,input().split())

l=sorted(l)

ans=1
for _ in range(n-1):
    ll=[]
    for i in l:
        if i[1]>=l[0][0]:
            ll.append(i)
    l=ll
    if len(l)!=0:
        ans+=1
    else:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
l=[[0,0] for _ in range(m)]
for i in range(m):
    l[i][1],l[i][0]=map(int,input().split())

l=sorted(l)
ans=1
for _ in range(n-1):
    ll=[]
    for i in l:
        if i[1]>=l[0][0]:
            ll.append(i)
    l=ll
    if len(l)!=0:
        ans+=1
    else:
        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

count = 0
while len(reqs) > 0:
    copied_req = copy.deepcopy(reqs)
    _, idx = map(min, zip(*copied_req))
    for req in reqs:
        if req[0] < idx:
            copied_req.remove(req)
    count += 1
    reqs = copied_req
print(count)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
wars = {}
for i in range(m):
  a, b = map(int, input().split())
  if a in wars.keys():
    wars[a].append(b)
  else:
    wars[a] = [b]

cuts = 0
antis = []

for i in range(1, n):
  if i in wars.keys():
    antis.append(min(wars[i]))
  if i + 1 in antis:
    cuts += 1
    antis.clear()
    
print(cuts)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
wars = {}
for i in range(m):
  a, b = map(int, input().split())
  if a in wars.keys():
    wars[a].append(b)
  else:
    wars[a] = [b]

cuts = 0
antis = []

for i in range(1, n):
  if i in wars.keys():
    for anti in wars[i]:
      antis.append(anti)
  if i + 1 in antis:
    cuts += 1
    antis.clear()
    
print(cuts)

Submission status: Time Limit Exceeded

Solution code:
import copy

N, M = map(int, input().split())
ab_list = [list(map(int, input().split())) for i in range(M)]
ab_list.sort()
cnt = 0
while True:
    point = {}

    for ab in ab_list:
        for i in range(ab[0], ab[1]):
            if i in point.keys():
                point[i] += 1
            else:
                point[i] = 1

    max_k = max(point, key=point.get)
    flag = False
    new_ab_list = copy.deepcopy(ab_list)
    for ab in ab_list:
        if ab[0] > max_k:
            break
        if ab[0] <= max_k < ab[1]:
            new_ab_list.remove(ab)
            if not flag:
                cnt += 1
                flag = True
    ab_list = new_ab_list
    if len(ab_list) == 0:
        break

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import copy

N, M = map(int, input().split())
ab_list = [list(map(int, input().split())) for i in range(M)]
ab_list.sort()
cnt = 0
while True:
    point = {}
    for i in range(N):
        point[i] = 0

    for i in range(N):
        for ab in ab_list:
            if ab[0] <= i < ab[1]:
                point[i] += 1

    max_k = max(point, key=point.get)
    flag = False
    new_ab_list = copy.deepcopy(ab_list)
    for ab in ab_list:
        if ab[0] > max_k:
            break
        if ab[0] <= max_k < ab[1]:
            new_ab_list.remove(ab)
            if not flag:
                cnt += 1
                flag = True
    ab_list = new_ab_list
    if len(ab_list) == 0:
        break

print(cnt)

Submission status: Time Limit Exceeded

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

cnt = 0
while True:
    point = {}
    for i in range(N):
        point[i] = 0

    # point更新
    for i in range(N):
        for ab in ab_list:
            if ab[0] <= i < ab[1]:
                point[i] += 1

    max_k = max(point, key=point.get)

    flag = False
    for i in reversed(range(len(ab_list))):
        if ab_list[i][0] <= max_k < ab_list[i][1]:
            ab_list.pop(i)
            if not flag:
                cnt += 1
                flag = True
    if len(ab_list) == 0:
        break

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from copy import copy
from operator import itemgetter
n, m = map(int, input().split())
abab = [list(map(int, input().split())) for _ in range(m)]
abab.sort(key=itemgetter(1))

class UnionFind(list) :
    def __init__(self, n) :
        super().__init__(range(n))

    def find(self, i) :
        if self[i] == i : return i
        self[i] = self.find(self[i])
        return self[i]

    def union(self, x, y) :
        x = self.find(x)
        y = self.find(y)
        self.new = copy(self)
        self.new[y] = x
        return self.new

    def sameroot(self, x, y) :
        return self.find(x) == self.find(y)

uf = UnionFind(n)
r = 0
for i in range(n-1) :
    u = uf.union(i, i+1)
    c = 0
    for a, b in abab :
        if b-2 > i : uf=u ; r+=1 ; abab=abab[c:] ; break
        if u.sameroot(a-1, b-1) : abab=abab[c:] ; break
        c += 1
    else : abab = [] ; r+=1
print(n-1-r)

Submission status: Time Limit Exceeded

Solution code:
from copy import copy
from operator import itemgetter
n, m = map(int, input().split())
abab = [list(map(int, input().split())) for _ in range(m)]
abab.sort(key=itemgetter(1))

class UnionFind(list) :
    def __init__(self, n) :
        super().__init__(range(n))

    def find(self, i) :
        if self[i] == i : return i
        self[i] = self.find(self[i])
        return self[i]

    def union(self, x, y) :
        x = self.find(x)
        y = self.find(y)
        self.new = copy(self)
        self.new[y] = x
        return self.new

    def sameroot(self, x, y) :
        return self.find(x) == self.find(y)

uf = UnionFind(n)
r = 0
for i in range(n-1) :
    u = uf.union(i, i+1)
    c = 0
    for a, b in abab :
        if b-2 > i : uf=u ; r+=1 ; abab=abab[c:] ; break
        if u.sameroot(a-1, b-1) : break
        c += 1
    else : abab = [] ; r+=1
print(n-1-r)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a, b = [0] * m, [0] * m
for i in range(m):
    a[i], b[i] = map(int, input().split())
bridge = []
for i in range(m):
    bridge.append(list(range(a[i], b[i])))
cnt = 0

while True:
    cnt_passed = [0 for _ in range(n - 1)]
    for bri in bridge:
        for j in bri:
            cnt_passed[j - 1] += 1
    removed = cnt_passed.index(max(cnt_passed)) + 1
    bridge = list(filter(lambda bri: removed not in bri, bridge))
    cnt += 1
    if len(bridge) == 0:
        print(cnt)
        exit(0)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
a, b = [0] * m, [0] * m
for i in range(m):
    a[i], b[i] = map(int, input().split())
bridge = []
for i in range(m):
    bridge.append(list(range(a[i], b[i])))
cnt = 0

while True:
    cnt_passed = [0] * (n - 1)
    for bri in bridge:
        for j in bri:
            cnt_passed[j - 1] += 1
    removed = cnt_passed.index(max(cnt_passed)) + 1
    for bri in bridge[:]:
        if removed in bri:
            bridge.remove(bri)
    cnt += 1
    if len(bridge) == 0:
        print(cnt)
        exit(0)

Submission status: Time Limit Exceeded

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

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

removed_bridge = []
for ab in AB_sorted:
    for bridge in removed_bridge:
        if ab[0] < bridge < ab[1]:
            break
    else:
        removed_bridge.append(ab[1] - 0.5)

print(len(removed_bridge))

Submission status: Time Limit Exceeded

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

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

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

num = 0
loc = 0
for i in range(M):
	if loc < areas[i][1]:
		num += 1
		loc = areas[i][0]

print(num)

Submission status: Time Limit Exceeded

Solution code:

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

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

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

num = 0
loc = 0
for i in range(M):
	if loc < areas[i][1]:
		num += 1
		loc = areas[i][0]

print(num)

Submission status: Time Limit Exceeded

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

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

while len(ab)!=0:
  if ab[0][1]-split[-1]>0 and ab[0][0]-split[-1]<=0:
    ab.pop(0)
  else:
    split.append(ab[0][1]-1)
  
  #print(ab)
print(len(split)-1)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

cnt = 0
while len(AB) > 0:
    bridges = [0] * (N - 1)
    for a, b in AB:
        for i in range(a - 1, b - 1):
            bridges[i] += 1
    collapse = bridges.index(max(bridges))
    cnt += 1
    AB = list(filter(lambda ab: ab[0] > collapse + 1 or collapse + 1 >= ab[1], AB))
print(cnt)

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())
bridges = set()
ms2 = sorted((tuple(map(int, input().split())) for i in range(m)), 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))