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

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

enabled=set()
remain=set([i for i in range(m)])

res=0
for i in range(1,n+1):
    for j in remain-enabled:
        if i == ab[j][0]:
            enabled.add(j)
    for j in enabled:
        if i == ab[j][1]-1 and j in remain:
            res+=1
            remain-=enabled
            enabled=set()
            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())))

abr=[]
enabled=set()
remain=set()
for i in range(m):
    abr.append(range(ab[i][0],ab[i][1]))
    remain.add(i)

res=0
for i in range(1,n+1):
    for j in remain-enabled:
        if i == abr[j][0]:
            enabled.add(j)
    for j in enabled:
        if i == abr[j][-1] and j in remain:
            res+=1
            remain-=enabled
            enabled=set()
            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())))

abr=[]
enabled=set()
remain=set()
for i in range(m):
    abr.append(range(ab[i][0],ab[i][1]))
    remain.add(i)

res=0
for i in range(1,n+1):
    for j in remain-enabled:
        if i == abr[j][0]:
            enabled.add(j)
    for j in enabled:
        if i == abr[j][-1] and j in remain:
            res+=1
            remain-=enabled
            enabled-=enabled
            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())))

abr=[]
enabled=set()
remain=set()
disabled=set()
for i in range(m):
    abr.append(range(ab[i][0],ab[i][1]))
    remain.add(i)
    disabled.add(i)


res=0
for i in range(1,n+1):
    for j in disabled:
        if i == abr[j][0]:
            enabled.add(j)
    for j in enabled:
        if i == abr[j][-1] and j in remain:
            res+=1
            remain-=enabled
            disabled=remain
            enabled-=enabled
            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())))

abr=[]
enabled=set()
remain=set()
for i in range(m):
    abr.append(range(ab[i][0],ab[i][1]))
    remain.add(i)

res=0
for i in range(1,n+1):
    for j in remain:
        if i == abr[j][0]:
            enabled.add(j)
    for j in enabled:
        if i == abr[j][-1] and j in remain:
            res+=1
            remain-=enabled
            enabled-=enabled
            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())))

abr=[]
enabled=[]
removed=[]
for i in range(m):
    abr.append(range(ab[i][0],ab[i][1]))
    enabled.append(False)
    removed.append(False)

res=0
for i in range(n):
    for j in range(len(abr)):
        if i == abr[j][0] and not removed[j]:
            enabled[j]=True
    for j in range(len(abr)):
        if i == abr[j][-1] and enabled[j]:
            res+=1
            for k in range(len(abr)):
                if enabled[k] and not removed[k]:
                    enabled[k]=False
                    removed[k]=True

print(res)

Submission status: Time Limit Exceeded

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

def bridge_divide( list):
    a, b = list[0][0], list[0][1]
    length = len(list)
    l = []
    i = 0
    while i < length and list[i][0] < b:
        l.append(list[i][1])
        i += 1
    minl = min(l)
    i = 0
    while i < length and list[i][0] < minl:
        i += 1
    return list[i:]

result = 0
while len(bridge) > 0:
    bridge = bridge_divide(bridge)
    result += 1
print(result)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int, input().split())
G=[list() for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
ans=0
index=-1
for i in range(1,N):
    for p in G[i]:
        if index<p<i:
            ans+=1
            index=i-1
import time
time.sleep(1.54)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int, input().split())
G=[list() for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
ans=0
index=-1
for i in range(1,N):
    for p in G[i]:
        if index<p<i:
            ans+=1
            index=i-1
import time
time.sleep(1.5)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ab_list = list()
for _ in range(m):
    a, b = map(int, input().split())
    ab_list.append([a, b])
ab_list = sorted(ab_list, key=lambda x: x[1])
n_list = [1 for i in range(n)]
for a, b in ab_list:
    t_list = n_list[a:b]
    v = t_list.count(0)
    if v == 0:
        n_list[b-1] = 0
print(n_list.count(0))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
ab_list = list()
for _ in range(m):
    a, b = map(int, input().split())
    ab_list.append([a, b])
ab_list = sorted(ab_list, key=lambda x: x[1])
n_list = [1 for i in range(n)]
for a, b in ab_list:
    flag = False
    for i in range(a, b):
        if n_list[i] == 0:
            flag = True
            break
    if not flag:
        n_list[b-1] = 0
print(n_list.count(0))

Submission status: Time Limit Exceeded

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

ans = 0

while(True):
    bridgeDic = {}
    for ab in abList:
        if ab != None:
            for i in range(ab[0], ab[1]):
                if i in bridgeDic:
                    bridgeDic[i] += 1
                else:
                    bridgeDic[i] = 1

    largeNum = 0
    largeKey = 0
    for i in bridgeDic:
        if bridgeDic[i] > largeNum:
            largeNum = bridgeDic[i]
            largeKey = i

    ans += 1
    M -= bridgeDic[largeKey]
    if M <= 0:
        break

    for i in range(len(abList)):
        if abList[i] != None and abList[i][0] <= largeKey < abList[i][1]:
            abList[i] = None

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def g(l, n, v):
    for i in n:
        for j in range(i[0], i[1]):
            l[j] += v

def f(n, m, A):
    global D
    max_n = max(enumerate(D[n:m], n), key=lambda x:x[1])[0]
    dA = {i for i in A if i[0] <= max_n < i[1]}
    g(D, dA, -1)
    return max_n, A - dA

def ff(n, m, A):
    i, A_ = f(n, m, A)
    A_1 = set(j for j in A_ if j[1] <= i)
    A_2 = A_ - A_1

    a1 = ff(n, i, A_1) if A_1 else 0
    a2 = ff(i+1, m, A_2) if A_2 else 0

    return a1 + a2 + 1


w = [int(i) for i in input().split()]
N = w[0]
M = w[1]
A = {tuple([int(j) for j in input().split()]) for i in range(M)}

D = [0] * N
g(D, A, 1)

print(ff(1, N, A))

Submission status: Time Limit Exceeded

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

war = {}
for i in range(M):
    a, b = map(int, input().split())
    if(b in war):
        if(a > war[b]):
            war[b] = a
    else:
        war[b] = a

ans = 1
b_list = list(war.keys())
b_list = sorted(b_list)
r_bridge = b_list[0] - 1

while(True):
    # print(b_list)
    for b in b_list[:]:
        a = war[b]
        if(a <= r_bridge < b):
            b_list.remove(b)

    if(b_list != []):
        r_bridge = b_list[0] - 1
        ans += 1
    else:
        break

print(ans)

Submission status: Time Limit Exceeded

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

war = {}
for i in range(M):
    a, b = map(int, input().split())
    if(a in war):
        if(b < war[a]):
            war[a] = b
    else:
        war[a] = b

ans = 0
bridge = [0 for i in range(N - 1)]
for a, b in war.items():
    for i in range(a, b):
        bridge[i - 1] += 1

while(war != {}):
    # print(war)
    ans += 1
    index = bridge.index(max(bridge))
    # print(index)
    for a, b in list(war.items())[:]:
        if(a <= index + 1 < b):
            war.pop(a)
            for i in range(a, b):
                bridge[i - 1] -= 1

print(ans)

Submission status: Time Limit Exceeded

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

war = {}
for i in range(M):
    a, b = map(int, input().split())
    if(a in war):
        if(b < war[a]):
            war[a] = b
    else:
        war[a] = b

ans = 0

while(war != {}):
    # print(war)
    ans += 1
    bridge = [0 for i in range(N - 1)]
    for a, b in war.items():
        for i in range(a, b):
            bridge[i - 1] += 1
    index = bridge.index(max(bridge))
    # print(index)
    for a, b in list(war.items())[:]:
        if(a <= index + 1 < b):
            war.pop(a)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

l = [[int(x) for x in input().split()] for _ in range(M)]



def do(l):
    

    count = 1

    l.sort()

    while True:

        # l2 = [v2 for (_,v2) in l]
        # l2.sort()
        

        nx = min(l,key=lambda x:x[1])[1]

        for i in range(len(l)):
            #print(l)
            
            if l[i][0] >= nx:
                #print("i")
                #print(i)
                #print(count)
                # h+=1
                # if i > 0:
                l = l[i:]
                count+=1
                break
            if i >= len(l)-1:
                return count
        if l == []:
            return count



result = do(l)
print(result)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

l = [[int(x) for x in input().split()] for _ in range(M)]



def do(l):
    

    count = 1

    l.sort()
    while True:
        l1 = [v1 for (v1,_) in l]
        l2 = [v2 for (_,v2) in l]
        l1.sort()
        l2.sort()

        nx = l2[0]

        for i in range(len(l)):
            #print(l)
            
            if l[i][0] >= nx:
                #print("i")
                #print(i)
                l = l[i:]
                #print(count)

                count+=1
                break
            if i >= len(l)-1:
                return count
        if l == []:
            return count



result = do(l)
print(result)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

l = [[int(x) for x in input().split()] for _ in range(M)]



def do(l):
    

    count = 1

    l.sort()
    while True:
        for i in range(len(l)):
            #print(l)
            l1 = [v1 for (v1,_) in l]
            l2 = [v2 for (_,v2) in l]
            l1.sort()
            l2.sort()

            nx = l2[0]
            if l[i][0] >= nx:
                #print("i")
                #print(i)
                l = l[i:]
                #print(count)

                count+=1
                break
            if i >= len(l)-1:
                return count




result = do(l)
print(result)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
l=sorted([tuple(map(int,input().split())) for _ in range(M)],key=lambda x:x[1])
c=0
m=[0 for _ in range(N)]
for i in l:
    if not 1 in m[i[0]-1:i[1]]:
        m[i[1]-2]=1
        c+=1

print(c)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
l=sorted([tuple(map(int,input().split())) for _ in range(M)],key=lambda x:x[1])
c=0
m=[0 for _ in range(N)]
for i in l:
    if not sum(m[i[0]-1:i[1]]):
        m[i[1]-2]=1
        c+=1

print(c)

Submission status: Time Limit Exceeded

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

acum = []

for ab in ass:
    if [x for x in acum if ab[0]<x <=ab[1]] == []:
        acum =acum + [ab[1]]

print(len(acum))

Submission status: Time Limit Exceeded

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

ans = 1
requests = sorted(requests, key=lambda x:x[1])
b = min(requests, key=lambda x:x[1])[1]
for i in range(M):
        if requests[i][0] < b:
                continue
        else:
                ans += 1
                b = min(requests[i:], key=lambda x:x[1])[1]

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def drop(islinds,problems):
    a=set()
    i=0
    while len(a)<len(problems):
        a=a|islinds[i]
        i+=1
    solved_problems=set()
    for s in islinds[i:]:
        solved_problems=solved_problems|s
    new_problems=problems.difference(solved_problems)
    new_islinds=[islind.difference(solved_problems) for islind in islinds[:i]]

    return new_islinds,new_problems

N, M=map(int,input().split(' '))
islinds=[set() for i in range(N)]
for i in range(1,M+1):
    a,b=map(int,input().split(' '))
    islinds[a-1].add(i)
    islinds[b-1].add(i)
problems=set(range(1,M+1))
count=0
while len(problems)>0:
    islinds,problems=drop(islinds,problems)
    count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
def drop(islinds,problems):
    a=set()
    i=0
    while len(a)<len(problems):
        a=a|islinds[i]
        i+=1
    solved_problems=set()
    for s in islinds[i:]:
        solved_problems=solved_problems|s
    new_problems=problems.difference(solved_problems)
    new_islinds=[islind.difference(solved_problems) for islind in islinds]

    return new_islinds,new_problems

N, M=map(int,input().split(' '))
islinds=[set() for i in range(N)]
for i in range(1,M+1):
    a,b=map(int,input().split(' '))
    islinds[a-1].add(i)
    islinds[b-1].add(i)
problems=set(range(1,M+1))
count=0
while len(problems)>0:
    islinds,problems=drop(islinds,problems)
    count+=1
print(count)

Submission status: Time Limit Exceeded

Solution code:
def drop(islinds,problems):
    a=set()
    i=0
    while a!=problems:
        a=a|islinds[i]
        i+=1
    solved_problems=set()
    for s in islinds[i:]:
        solved_problems=solved_problems|s
    new_problems=problems.difference(solved_problems)
    new_islinds=[islind.difference(solved_problems) for islind in islinds]

    return new_islinds,new_problems

N, M=map(int,input().split(' '))
islinds=[set() for i in range(N)]
for i in range(1,M+1):
    a,b=map(int,input().split(' '))
    islinds[a-1].add(i)
    islinds[b-1].add(i)
problems=set(range(1,M+1))
count=0
while len(problems)>0:
    islinds,problems=drop(islinds,problems)
    count+=1
print(count)

Submission status: Time Limit Exceeded

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

demands= []

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

demands.sort()

cut = []

for d in demands:
    flag = True
    for c in cut:
        if c[0] < d[1] and c[1] > d[0]:
            flag = False
            c[0] = max(c[0],d[0])
            c[1] = min(c[1],d[1])
            break
    if flag:
        cut.append(d)

print(len(cut))

Submission status: Time Limit Exceeded

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

ans = 1
requests = sorted(requests, key=lambda x:(x[1],x[0]))
b = min(requests, key=lambda x:x[1])[1]
for i in range(M):
        if requests[i][0] < b:
                continue
        else:
                ans += 1
                b = min(requests[i:], key=lambda x:x[1])[1]

print(ans)

Submission status: Time Limit Exceeded

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

ans = 1
requests = sorted(requests, key=lambda x:(x[0],x[1]))
b = min(requests, key=lambda x:x[1])[1]
for i in range(M):
        if requests[i][0] < b:
                continue
        else:
                ans += 1
                b = min(requests[i:], key=lambda x:x[1])[1]

print(ans)

Submission status: Time Limit Exceeded

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

count = 0

while ass != []:
    count = count+1
    ref = min(ass,key = lambda x:x[1])
    index = next((i for i,x in enumerate(ass) if x[0]>=ref[1]),len(ass))
    ass = ass[index::]

print(count)

Submission status: Time Limit Exceeded

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

count = 0

while ass != []:
    count = count+1
    ref = min(ass,key = lambda x:x[1])
    ass = [x for x in ass if x[0]>=ref[1]]

print(count)

Submission status: Time Limit Exceeded

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

ans = 1
requests = sorted(requests, key=lambda x:x[0])
b = min(requests, key=lambda x:x[1])[1]
for i in range(M):
        if requests[i][0] < b:
                continue
        else:
                ans += 1
                b = min(requests[i:], key=lambda x:x[1])[1]

print(ans)

Submission status: Time Limit Exceeded

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

ass.sort(key = lambda x:x[1])
count = 0

while ass != []:
    count = count+1
    ref = ass[0]
    #print('ref',ref)
    ass.sort(key = lambda x:x[0])
    #print('sortedass',ass)
    index = next((i for i,x in enumerate(ass) if x[0]>=ref[1]),len(ass) )
    ass = ass[index::]
    ass.sort(key = lambda x:x[1])
    #print(index)
    #print(ass)

print(count)

Submission status: Time Limit Exceeded

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

ass.sort(key = lambda x:x[1])
count = 0

while ass != []:
    count = count+1
    ref = ass[0]
    #print('ref',ref)
    ass.sort(key = lambda x:x[0])
    #print('sortedass',ass)
    index = next((x for x in list(enumerate(ass)) if x[1][0]>=ref[1]),(len(ass)+10,0) )[0]
    ass = ass[index::]
    ass.sort(key = lambda x:x[1])
    #print(index)
    #print(ass)

print(count)

Submission status: Time Limit Exceeded

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

x = 0
ans = 0

while x < n:
    p = 10000000
    for y in a:
        if y[0] >= x:
            p = min(p, y[1])
    for y in a:
        if y[0] < x:
            a.remove(y)
    if p <= n:
        ans += 1
    if p == 10000000:
        break
    x = p

print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from collections import Counter
from itertools import chain

N, M = [int(i) for i in input().split()]

war = []

for i in range(M):
    tmp = [int(i) for i in input().split()]
    war.append(list(range(tmp[0], tmp[1])))

war_cnt = Counter(list(chain.from_iterable(war)))

ans = 0

while len(war) > 0:
    cut_target = max(war_cnt, key = war_cnt.get)
    cut_flug = False
    w_cp = war[:]
    for w in w_cp:
        if cut_target in w:
            war.remove(w)
            cut_flug = True
    if cut_flug:
        ans += 1
    war_cnt = Counter(list(chain.from_iterable(war)))

print(ans)

Submission status: Time Limit Exceeded

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

ab = [list(range(int(x[0]), int(x[1]))) for _ in range(M) for x in [input().split()]]

def mode(X):
    return max([(X.count(x), x) for x in set(X)], key=lambda x: x[0])[1]

count = 0
while ab:
    m = mode(list(chain.from_iterable(ab)))
    ab = [x for x in ab if m not in x]
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,m = list(map(int,input().split()))

a = []
b = [[0 for i in range(n-1)] for j in range(m)]
for i in range(m):
    bb,c = list(map(int,input().split()))
    for j in range(bb-1,c-1):
        b[i][j] += 1
ans = 0
c = [0 for i in range(n-1)]
for i in b:
    c += np.array(i)
while sum(c) > 0:
    f = list(c)
    g = f.index(max(f))
    e = b[:]
    ans += 1
    for i in e:
        if i[g] == 1:
            b.remove(i)
            c -= np.array(i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
n, m = map(int, sys.stdin.readline().split())
req = [ list(sorted(map(int, sys.stdin.readline().split())))
        for _ in range(m) ]
req.sort(reverse=True)
cutlist = []
for a, b in req:
    cut = False
    for i in cutlist:
        if a <= i and i < b:
            cut = True
            break
    if not cut:
        cutlist.append(a)
print(len(cutlist))

Submission status: Time Limit Exceeded

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

a -= 1
b -= 1 
cnt = 0
in_task = np.zeros(m).astype(np.bool)

for i in range(n-1):
    a_bool = (a == i).astype(np.bool)
    if(a_bool.any()):
        in_task += a_bool
    if(np.any(b == i+1)):
        cnt += 1
        tmp = np.logical_not(in_task)
        a = a[tmp]
        b = b[tmp]
        in_task = np.zeros(a.shape).astype(np.bool)

print(cnt)

Submission status: Time Limit Exceeded

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

ans = 0
requests = sorted(requests, key=lambda x:x[0])
while requests:
        ans += 1
        bridge = min(requests, key=lambda x:x[1])[1]
        while requests:
                if requests[0][0] < bridge:
                        del requests[0]
                else:
                        break

print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

AA=[]
for i in range(n):
  for j in range(m):
    if A[j][0]==i :
      AA.append([A[j][0],A[j][1]])

A=AA
def kyotu(J,K):
  aa,bb=max(J[0],K[0]),min(J[1],K[1])
  if aa>=bb:
    return 0
  else:
    return [aa,bb]


kyo=[]
kk=[]
def kyotu2(k):
  for i in range(len(kyo)):
    kk=kyotu(kyo[i],A[k])
    
    if kk!=0:
      kyo[i][0]=kk[0]
      kyo[i][1]=kk[1]
      return 0
    
  kyo.append([A[k][0],A[k][1]])



for i in range(m):
  kyotu2(i)
#print(kyo)
print(len(kyo))

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
from collections import Counter
import numpy as np
from itertools import chain

N, M = [int(i) for i in input().split()]

war = []

for i in range(M):
    tmp = [int(i) for i in input().split()]
    war.append(list(range(tmp[0], tmp[1])))

war_cnt = Counter(list(chain.from_iterable(war)))

ans = 0

while len(war) > 0:
    cut_target = max(war_cnt, key = war_cnt.get)
    cut_flug = False
    w_cp = war[:]
    for w in w_cp:
        if cut_target in w:
            war.remove(w)
            cut_flug = True
    if cut_flug:
        ans += 1
    war_cnt = Counter(list(chain.from_iterable(war)))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def f(n, m, A):
    w = {i: {j for j in A if j[0]<= i < j[1]} for i in range(n, m)}
    # print(w)
    max_n = max(w.items(), key=lambda x:len(x[1]))[0]
    # print("w", A, w[max_n], A- w[max_n])
    return max_n, A - w[max_n]

def ff(n, m, A):
    # print(n ,m ,A)

    i, A_ = f(n, m, A)
    A_1 = set(j for j in A_ if j[1] <= i)
    A_2 = A_ - A_1

    # print(" ", i, A_1, A_2)

    a1 = ff(n, i, A_1) if A_1 else 0
    a2 = ff(i+1, m, A_2) if A_2 else 0

    return a1 + a2 + 1

w = [int(i) for i in input().split()]
N = w[0]
M = w[1]
A = {tuple([int(j) for j in input().split()]) for i in range(M)}

print(ff(1, N, A))

Submission status: Time Limit Exceeded

Solution code:
(n, m) = tuple(map(int, input().split()))
arr = [[0, 0] for i in range(m)]
zel = [0 for i in range(n)]
for i in range(m):
    (a, b) = list(map(int, input().split()))
    arr[i] = [a, b]
    for i in range(b - a):
        zel[a + i] += 1
res = -1
while True:
    res += 1
    mx = 0
    mxi = 0
    for i, e in enumerate(zel):
        if e > mx:
            mx = e
            mxi = i
    if mx == 0:
        break
    for i, e in enumerate(arr):
        if e[0] <= mxi < e[1]:
            for j in range(e[0], e[1]):
                zel[j] -= 1
            arr[i] = [0, 0]
print(res)

Submission status: Time Limit Exceeded

Solution code:
def check(req, num):
    if req[0] <= num and num < req[1]:
        return True
    else:
        return False

N,M = [int(i) for i in input().split()]
Req = []
Req.append([int(i) for i in input().split()])
for i in range(M-1):
    r = [int(i) for i in input().split()]
    flag = True
    for j in Req:
        if r[0]<=j[0] and j[1] <= r[1]:
            flag = False
            break
        if j[0]<=r[0] and r[1] <= j[1]:
            Req.remove(j)
    if flag:
        Req.append(r)
        
bridgeNum = 0
while(len(Req)>0):
    bridgeNum+=1
    tmpReqMax = 0 
    for i in range(N):
        tmpNum=0
        for req in Req:
            if check(req, i+1):
                tmpNum += 1
        if tmpReqMax < tmpNum:
            tmpReqMax = tmpNum
            bridge = i+1
    Req = [i for i in Req if not check(i, bridge)]
print(bridgeNum)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n,m=map(int,input().split())
r=[]
ac=0
ans=0

def lmax(a):
    c=[]
    for i in a:
        c+=i
    return  Counter(c).most_common()[0][0]

for i in range(m):
    a,b=map(int,input().split())
    l=list(range(a,b))
    r.append(l)
c=0
k=0
while ac!=m:
    mc=lmax(r)
    lr =len(r)
    c=0
    k=0
    while c<lr:
        if mc in r[k]:
            del r[k]
            ac+=1
            c+=1
        else:
            k+=1
            c+=1
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int, input().split(" "))
#min=0
#max=1000000000
arr=[[0,100000000]]
for i in range(m):

    flag=1
    a,b=map(int, input().split(" "))
    for n,j in enumerate(arr):
        flag=1
        if j[0]<=a and j[1]>=b:
            del arr[n]
            #arr.remove(j)
        elif j[0]>=a and j[1]<=b:
            flag=0
            break
    if flag==1:
        arr.append([a,b])

#arr.sort(key=lambda x:x[0])
arr.sort(key=lambda x:(x[0],x[1]))
#print(arr)
#count=0
num=0
count=0
for i in range(len(arr)):
    if arr[i][0]-num>=0:
        count+=1
        num=arr[i][1]

print(count)

Submission status: Time Limit Exceeded

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

ans = 0
while requests:
        ans += 1
        bridge = min(requests, key=lambda x:x[1])[1]
        requests = sorted(requests, key=lambda x:(x[0]))
        while requests:
                if requests[0][0] < bridge:
                        del requests[0]
                else:
                        break

print(ans)

Submission status: Time Limit Exceeded

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

land=[[] for _ in range(n)]

for i, j in enumerate(a):
    land[j[0]-1].append(i+1)
    land[j[1]-1].append(i+1)

#print("la",land)

wli=[]
ans=0
for i in land:
    if len(i)>=1:
            ic=i.copy()
            while len(i)>0:
                temp=i.pop()
                if temp not in wli:
                    wli.append(temp)
                    #print(wli)
                else:
                    ans+=1
                    wli=ic
                    #print(wli)
                    break

#print(wli)
print(ans)

Submission status: Time Limit Exceeded

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

a = np.array(a) - 1
b = np.array(b) - 1 
cnt = 0
in_task = np.zeros(m).astype(np.bool)

for i in range(n-1):
    if(np.any(a == i)):
        in_task += (a == i).astype(np.bool)
    if(np.any(b == i+1)):
        cnt += 1
        tmp = np.logical_not(in_task)
        a = a[tmp]
        b = b[tmp]
        in_task = np.zeros(a.shape).astype(np.bool)
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,m = list(map(int,input().split()))

a = []
for i in range(m):
    a.append(list(map(int,input().split())))
b = [[0 for i in range(n-1)] for j in range(m)]
for i in range(m):
    for j in range(a[i][0]-1,a[i][1]-1):
        b[i][j] += 1
ans = 0
c = [0 for i in range(n-1)]
for i in b:
    c += np.array(i)
while sum(c) > 0:
    f = list(c)
    g = f.index(max(f))
    e = b[:]
    ans += 1
    for i in e:
        if i[g] == 1:
            b.remove(i)
            c -= np.array(i)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
n, m = map(int, sys.stdin.readline().split())
req = [ list(sorted(map(int, sys.stdin.readline().split())))
        for _ in range(m) ]
req.sort(reverse=True)
c = 0
while req:
    i = req[0][0]
    c += 1
    newreq = []
    for r in req:
        if r[1] <= i:
            newreq.append(r)
    req = newreq
print(c)