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(" "))
#min=0
#max=1000000000
arr=[[0,100000000]]
for i in range(m):
    flag=1
    a,b=map(int, input().split(" "))
    for j in arr:
        flag=1
        if j[0]<=a and j[1]>=b:
            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])
#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:
from itertools import chain
N, M = [int(x) for x in input().split()]

ab = [(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:
    X = list(chain.from_iterable([list(range(x[0], x[1])) for x in ab]))
    m = mode(X)
    ab = [x for x in ab if m < x[0] or x[1] <= m]
    count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
request=[]
for _ in range(M):
    request.append(list(map(int,input().split())))
request.sort(key=lambda x: x[0])
    
memory=[]
memory.append(request[0][1])
head = request[0][0]
index = 0
ans = 0

def equalmin():
    if memory == []: return False
    else: return head == min(memory)

def equal():
    if index == M-1: return False
    else: return head == request[index+1][0]

while head <= N:
    if equalmin():
        ans +=1
        memory = []
    elif equal():
        index+=1
        memory.append(request[index][1])
    else: head +=1
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq

N, M =map(int, input().split())
p = []

for _ in range(M):
    A, B= map(int, input().split())
    n = B - A
    m = {i for i in range(A, B)}
    heapq.heappush(p, (n, m))

n = 0
sets = []
for _ in range(M):
    n, q = heapq.heappop(p)
    for m, s in sets:
        if len(s - q) == 0:
            break
    else:
        heapq.heappush(sets, (max(q), q))
    
count = 0
minnum = -1
for _ in range(len(sets)):
    n, q = heapq.heappop(sets)
    if minnum in q:
        continue
    minnum = n
    count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,m = [int(x) for x in input().split()]
conf=[]
for i in range(m):
  a,b = [int(x) for x in input().split()]
  conf.append([a,b])
f = np.zeros(n+1)
for a,b in conf:
  for i in range(a,b):
    f[i]+=1
cnt=0
while conf != []:
  p = np.argmax(f)
  for a,b in [[x,y] for x,y in conf if x<=p and p<y]:
    for i in range(a,b):
      f[i]-=1
  conf = [[x,y] for x,y in conf if x>p or p>=y]
  cnt +=1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import math, string, fractions, heapq, re, array, bisect, sys, random, time, copy
import itertools as it
import collections as cl
import functools as ft
import numpy as np

def LI(): return [int(x) for x in sys.stdin.readline().split()]
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 LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


n, m = LI()
ab = []
weight = np.zeros((1, n))
dic = {i: [] for i in range(n)}


def wei(dic):
    return [len(li) for li in dic.values()]


for i in range(m):
    a, b = LI()
    weight[0][a:b] += 1
    ab.append((a, b))
    for j in range(a, b):
        dic[j].append(i)

# print(weight)
count = 0
checked = []
while np.sum(weight) > 0:
    max_index = np.argmax(weight)
    # print('max_index: ', max_index)
    # print('--------------')
    for i, (a, b) in enumerate(ab):
        if (a <= max_index < b) and i not in checked:
            checked.append(i)
            weight[0][a:b] -= 1
            # print(weight)
    count += 1

print(count)

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

broken_bridge = [0 for i in range(n-1)]
comp_task = [0 for i in range(m)]

a = np.array(a) - 1
b = np.array(b) - 1 
cnt = 0
comp_task = np.zeros(m).astype(np.bool)
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*in_task == i+1)):
        cnt += 1
        comp_task += in_task
        a[comp_task] = -1
        b[comp_task] = -1
        in_task = np.zeros(m).astype(np.bool)

print(cnt)

Submission status: Time Limit Exceeded

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

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

    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 = map(int, input().split())
l = [list(map(int,input().split())) for _ in range(m)]
l.sort()

cut = [l[0]]
for i in range(1,m):
    for j in range(len(cut)):
        key = 0
        if cut[j][0] <= l[i][0]  and l[i][0] < cut[j][1] :
            cut[j][0] = l[i][0]
            key +=1
        if cut[j][0] < l[i][1] and l[i][1] <= cut[j][1]  :
            cut[j][1] = l[i][1]
            key +=1
        if key > 0:
            break
    
    if key == 0 :
        cut.append(l[i])


print(len(cut))

Submission status: Time Limit Exceeded

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

Rqst = sorted(Rqst)

i = 0
j = M
while i < j - 1:
    if Rqst[i + 1][0] == Rqst[i][0]:
        del Rqst[i + 1]
        j -= 1
    elif Rqst[i + 1][0] < Rqst[i][1]:
        if Rqst[i][1] <= Rqst[i + 1][1]:
            Rqst[i][0] = Rqst[i + 1][0]
            del Rqst[i + 1]
            j -= 1
        else:
            del Rqst[i]
            j -= 1
    else:
        i += 1

ans = len(Rqst)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M = map(int, raw_input().split())

    a = []
    for _ in range(M):
        ai, bi = map(int, raw_input().split())
        a.append((ai, bi))

    min_n = N
    for i in range(M):
        l = set()
        for m in a:
            j = m[0]
            while j < m[1]:
                if j in l:
                    break
                j += 1
            if j == m[1]:
                l.add(m[0])

        if len(l) < min_n:
            min_n = len(l)
        first = a.pop(0)
        a.append(first)

    print min_n

main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, M = map(int, input().split())
data = []
for i in range(M):
  a = list(map(int, input().split()))
  data.append(a)
ans = 0

hasi = [i+1 for i in range(N-1)]

while True:
  max = 0
  for i in hasi:
    cnt = 0
    for j in data:
      if j[0] <= i < j[1]:
        cnt += 1
    if cnt > max:
      max = cnt
      cut = i
  hasi.remove(cut)
  data = [i for i in data if (i[0] > cut or cut >= i[1])]
  ans += 1

  if data == []:
    print(ans)
    break

Submission status: Time Limit Exceeded

Solution code:
import copy
n, m = [int(x) for x in input().split()]
ms = []
bs = []
for i in range(m):
  tmp = [int(x) for x in input().split()]
  if abs(tmp[0] - tmp[1]) == 1:
    bs.append(max(tmp)-1)
  else:
    ms.append(tmp)

ms1 = copy.deepcopy(ms)
for mm in ms1:
  tmpl = [x for x in bs if min(mm) <= x < max(mm)]
  if len(tmpl) != 0:
    ms.remove(mm)

dd = [0 for x in range(n)]
for mm in ms:
  dd = [dd[j] + 1 if min(mm) <= j < max(mm) else dd[j] for j in range(n)]

while len(ms) > 0:
  i = dd.index(max(dd))
  bs.append(i)
  ms1 = copy.deepcopy(ms)
  for mm in ms1:
    tmpl = [x for x in bs if min(mm) <= x < max(mm)]
    if len(tmpl) != 0:
      dd = [dd[j] - 1 if min(mm) <= j < max(mm) else dd[j] for j in range(n)]
      ms.remove(mm)

print(len(bs))

Submission status: Time Limit Exceeded

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

B     = list(range(0, N-1))
R     = [None] * M

for m in range(0, M):
    a, b = map(int, input().split())
    R[m] = B[min(a, b)-1:max(a, b)-1]

result = 0

while R != []:
    R_sum = [0] * (N - 1)
    for r in R:
        R_sum[r[0]:r[-1]+1] = map(lambda x: x+1, R_sum[r[0]:r[-1]+1])
    max_idx = R_sum.index(max(R_sum))
    R = [x for x in map(lambda r: None if max_idx in r else r, R) if x is not None]
    result += 1

print(result)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
request=[]
for _ in range(M):
    request.append(list(map(int,input().split())))
request.sort(key=lambda x: x[0])
    
memory=[]
memory.append(request[0])
head = request[0][0]
index = 0
ans = 0

def find(n,li):
    for row in li:
        if row[1]==n:return True
    return False

def equal():
    if index == M-1: return False
    else: return head == request[index+1][0]

while head <= N:
    if find(head,memory):
        ans +=1
        memory = []
    elif equal():
        index+=1
        memory.append(request[index])
    else: head +=1
        
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 = 0
    while True:
        l.sort()
        value = l[-1][0]+1
        l.sort(key=lambda v:v[1])
        l2 = [v2 for (_,v2) in l]
        index = bisect.bisect_left(l2,value)
        l = l[:index]

        count += 1
        if len(l)<1:
            break
    return count



result = do(l)
print(result)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

s= input().rstrip().split(' ')

n = int(s[0])
m = int(s[1])

a = [0] *m
b = [0] *m
mat = [0]*m

for i in range(m):
    s = input().rstrip().split(' ')
    a[i] = int(s[0])
    b[i] = int(s[1])
    mat[i] = [0]*(a[i]-1) + [1]*(b[i]-a[i])+[0]*(n-b[i])

mat = np.array(mat)
    
count = 0
# print(np.sum(mat))
while(np.sum(mat)>0):

    MAX = np.max(np.sum(mat, 0))
    destroy = np.argmax(np.sum(mat, 0))
    count += 1

#     for i in range(m):
#         if mat[i][destroy]==0:
#             mat[i] = [0]*(n-1)

    mat = mat[mat[:,destroy]==0]
        
print(count)

Submission status: Time Limit Exceeded

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

Rqst = sorted(Rqst)

i = 0
j = M
while i < j - 1:
    if Rqst[i][0] == Rqst[i + 1][0]:
        del Rqst[i + 1]
        j -= 1
    else:
        i += 1

M = len(Rqst)
i = 0
j = M

while i < j - 1:
    if Rqst[i + 1][0] < Rqst[i][1]:
        if Rqst[i][1] <= Rqst[i + 1][1]:
            Rqst[i][0] = Rqst[i + 1][0]
            del Rqst[i + 1]
            j -= 1
        else:
            del Rqst[i]
            j -= 1
    else:
        i += 1

ans = len(Rqst)

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

broken_bridge = [0 for i in range(n-1)]
comp_task = [0 for i in range(m)]

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

for i in range(n-1):
    if(np.any(a*np.logical_not(comp_task) == i )):
        in_task = (in_task+(a*np.logical_not(comp_task)==i)).astype(np.bool)
    if(np.any(b*np.logical_not(comp_task)*in_task == i+1)):
        cnt += 1
        comp_task = (comp_task + in_task).astype(np.bool)
        in_task = np.zeros(m)

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import copy
n, m = [int(x) for x in input().split()]
ms = []
bs = []
for i in range(m):
  tmp = [int(x) for x in input().split()]
  if abs(tmp[0] - tmp[1]) == 1:
    bs.append(max(tmp)-1)
  else:
    ms.append(tmp)

ms1 = copy.deepcopy(ms)
for mm in ms1:
  tmpl = [x for x in bs if min(mm) <= x < max(mm)]
  if len(tmpl) != 0:
    ms.remove(mm)

dd = 1
while len(ms) > 0:
  dd = [0 for x in range(n)]
  for mm in ms:
    for i in range(min(mm),max(mm)):
      dd[i] += 1
  i = dd.index(max(dd))
  bs.append(i)
  ms1 = copy.deepcopy(ms)
  for mm in ms1:
    tmpl = [x for x in bs if min(mm) <= x < max(mm)]
    if len(tmpl) != 0:
      ms.remove(mm)

print(len(bs))

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 i in range(m):
        if a[i][0] >= x:
            p = min(p, a[i][1])
    if p <= n:
        ans +=1
    if p == 10000000:
        break
    x = p

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
E=[(1,N)]
for _ in[0]*M:
    a,b=map(int,input().split())
    E+=[(a,b)]
    F=[]
    for s,t in E:
        if s<=a and b<=t:
            F+=[(a,b)]
        else:
            F+=[(s,t)]
    E=F
cnt=0
while E:
    cnt+=1
    M, Mi = 0, 0
    A = [0]*N
    l = len(E)
    B = [set(range(l))for _ in[0]*N]
    for k,(s,t) in enumerate(E):
        for i in range(s,t):
            A[i]+=1
            B[i]-={k}
            if M<A[i]:
                M, Mi = A[i], i
    E=[E[i]for i in B[Mi]]
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def sarch(listd, num, i):
    if listd[i - 2] == num:
        return 1
    return 0

N, M = map(int, input().split())
data = []
brige = []
for i in range(M):
    A, B = map(int, input().split())
    data.append(B)
    listdata = [0 for j in range(1, A)]
    for j in range(A, B):
        listdata.append(j)
    listdata.extend([0 for j in range(B, N)])
    brige.append(listdata)


ans = []


keylist = [0 for i in range(M)]

for i in range(1, N + 1):
    for j in range(M):
        if keylist[j] != 1 and sarch(brige[j], i, data[j]) == 1:
            ans.append(i)
            for k in range(M):
                if brige[k][i - 1] == i:
                    keylist[k] = 1
            keylist[j] = 1


print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
E={(1,N)}
for _ in[0]*M:
    a,b=map(int,input().split())
    E|={(a,b)}
    F=set()
    for s,t in E:
        if s<=a and b<=t:
            F.add((a,b))
        else:
            F.add((s,t))
    E=F
cnt=0
E=list(E)
while E:
    cnt+=1
    M, Mi = 0, 0
    A = [0]*N
    l = len(E)
    B = [set(range(l))for _ in[0]*N]
    for k,(s,t) in enumerate(E):
        for i in range(s,t):
            A[i]+=1
            B[i]-={k}
            if M<A[i]:
                M, Mi = A[i], i
    E=[E[i]for i in B[Mi]]
print(cnt)

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 = [(int(i), int(j)) for i, j in [input().split() for i in range(M)]]
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:
headData = [int(n) for n in input().split()]
islandNum = headData[0]
requestNum = headData[1]
requestList = []
count = 0
for n in range(requestNum):
    request = [int(elem) for elem in input().split()]
    requestList.append(request)


while (len(requestList) != 0):
    # 優先度チェック
    bridgePriority = islandNum * [0]
    for request in requestList:
        for j in range(request[0], request[1]):
            bridgePriority[j] += 1
    bridge = -1

    # 優先度が最も高い橋を特定
    for index in range(len(bridgePriority)):
        if (bridgePriority[index] == max(bridgePriority)):
            bridge = index
            break

    # 橋を削除した場合、叶っていないリクエストリストを作成
    newRequestList = []
    for request in requestList:
        if (bridge < request[0] or request[1] <= bridge):
            newRequestList.append(request)
    requestList = newRequestList
    count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
import copy
n,m = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(m)]
bridge = [0 for _ in range(n)]
bridge_m = [[] for _ in range(n)]
for i in range(m):
    for j in range(ab[i][0],ab[i][1]):
        bridge[j] +=1
        bridge_m[j].append(i)
cnt =0
max_ = max(bridge)
while(max_!=0):
    argmax = bridge.index(max_)
    delete = copy.deepcopy(bridge_m[argmax])
    for i in delete:
        for j in range(ab[i][0],ab[i][1]):
            bridge[j] -=1
            bridge_m[j].remove(i)
    cnt +=1
    max_ =max(bridge)
print(cnt)

Submission status: Time Limit Exceeded

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

ans = 0
while 1:
    if len(a) == 0:
        break
    maxVal = max(a)
    maxIdx = a.index(maxVal)

    for j in reversed(range(len(a))):
        if a[j] <= maxVal <= b[j] - 1:
            a.pop(j)
            b.pop(j)

    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import copy

n, m = list(map(int, input().split(" ")))
a = m*[0]
b = m*[0]
for i in range(m):
    a[i], b[i] = list(map(int, input().split(" ")))

ans = 0
while(True):
    island = n*[0]
    ans += 1
    for i, j in zip(a, b):
        for k in range(i, j, 1):
            island[k] += 1
    cut = island.index(max(island))

    na = []
    nb = []
    for i, j in zip(a, b):
        if(cut < i or j <= cut):
            na.append(i)
            nb.append(j)

    if(len(na) == 0): break

    a = copy.deepcopy(na)
    b = copy.deepcopy(nb)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

s= input().rstrip().split(' ')
n = int(s[0])
m = int(s[1])

a = [0] *m
b = [0] *m

for i in range(m):
    s = input().rstrip().split(' ')
    a[i] = int(s[0])
    b[i] = int(s[1])
    
mat = [0]*m
for i in range(m):
    mat[i] = [0]*(a[i]-1) + [1]*(b[i]-a[i])+[0]*(n-b[i])

count = 0
while(np.sum(np.sum(mat))>0):

    destroy = np.argmax(np.sum(mat, 0))
    count += 1

    for i in range(m):
        if mat[i][destroy]==1:
            mat[i] = [0]*(n-1)
        
print(count)

Submission status: Time Limit Exceeded

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

for i in range(m):
    A,B=map(int,input().split())
    lis.append([A,B])
    ng[A].add(B)
    
lis.sort()
now=[]
danger=set()
cu=0
for i in range(1,n):
    now.append(i)
    danger=danger|ng[i]
    if(i+1 in danger):
        cu+=1
        danger=set()
            
print(cu)

Submission status: Time Limit Exceeded

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

a = []
for i in range(m):
    a.append(list(map(int,input().split())))
a.sort()
ans = 0
while len(a) >0:
    ans += 1
    b = [0 for i in range(n-1)]
    for i in a:
        for j in range(i[0]-1,i[1]-1):
            b[j] += 1
    c = b.index(max(b))
    d = a[:]
    for i in d:
        if i[0] <= c+1 and i[1] >= c+2:
            a.remove(i)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
def sarch(listd, num):
    if listd[len(listd) - 1] == num:
        for i in listd:
            for j in ans:
                if i == j:
                    return 0
        return 1
    return 0

N, M = map(int, input().split())
data = []
brige = []
for i in range(M):
    A, B = map(int, input().split())
    data.append([A, B])
    listdata = []
    for j in range(A, B):
        listdata.append(j)
    brige.append(listdata)


ans = []

keylist = [0 for i in range(M)]

for i in range(1, N + 1):
    for j in range(M):
        if keylist[j] != 1 and sarch(brige[j], i) == 1:
            ans.append(i)
            keylist[j] = 1
    

print(len(ans))

Submission status: Time Limit Exceeded

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

for i in range(m):
    A,B=map(int,input().split())
    lis.append([A,B])
    ng[A].append(B)
    
lis.sort()
now=[]
cu=0
for i in range(1,n):
    now.append(i)
    for j in now:
        if(i+1 in ng[j]):
            cu+=1
            now=[]
            break
            
print(cu)

Submission status: Time Limit Exceeded

Solution code:
def sarch(listd, num):
    if listd[len(listd) - 1] == num:
        return 1
    return 0

N, M = map(int, input().split())
data = []
brige = []
for i in range(M):
    A, B = map(int, input().split())
    data.append([A, B])
    listdata = []
    for j in range(A, B):
        listdata.append(j)
    brige.append(listdata)


ans = []

keylist = [0 for i in range(M)]

for i in range(1, N + 1):
    for j in range(M):
        if keylist[j] != 1 and sarch(brige[j], i) == 1:
            ans.append(i)
            keylist[j] = 1
            for k in range(M):
                for l in brige[k]:
                    if l == i:
                        keylist[k] = 1
                        break
    

print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
v = [[] for i in range(n+1)]
path = [0 for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    v[b].append(a)
for i in range(n+1):
    if v[i] == []:
        continue
    m = max(v[i])
    found = 0
    for e in path[m:i]:
        if e == 1:
            found = 1
            break
    if found == 0:
        path[i - 1] = 1
s = 0
for p in path:
    s += p
print(s)

Submission status: Time Limit Exceeded

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

Query = []
for _ in range(M):
    Query.append(list(map(int, input().split())))


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

count = 0
while len(Query) > 0:
    Query = list(filter(lambda x: x[0] >= Query[0][1], Query))
    count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N,M = map(int,input().split())

D = defaultdict(lambda: N+1)
for i in range(M):
    a,b = map(int,input().split())
    if b<D[a]:D[a]=b
        
side_b = []
ans = 0
for i in range(1,N+1):
    if i in side_b:
        side_b = []
        ans += 1
    side_b.append(D[i])
    #print(i,side_b)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map( int, input().split())
Q = []
for i in range(M):
    a,b = map(int,input().split())
    Q.append([a,b])
Q = sorted(Q)
ans = 1
while len(Q) != 0:
    stan = Q[0][1]
    k = 1
    while len(Q) != 0:
        if Q[0][0] < stan:
            stan = min(stan,Q.pop(0)[1])
        else:
            ans += 1
            break
print(ans)

Submission status: Accepted

Solution code:
# Segment tree (+)
from operator import add
from sys import stdin


class SegmentTree:
    def __init__(self, size, op, e):
        self._op = op
        self._e = e
        self._size = size
        t = 1
        while t < size:
            t *= 2
        self._offset = t - 1
        self._data = [e] * (t * 2 - 1)

    def __getitem__(self, key):
        return self._data[self._offset + key]

    def __setitem__(self, key, value):
        op = self._op
        data = self._data
        i = self._offset + key
        data[i] = value
        while i >= 1:
            i = (i - 1) // 2
            data[i] = op(data[i * 2 + 1], data[i * 2 + 2])

    def build(self, iterable):
        op = self._op
        data = self._data
        data[self._offset:self._offset + self._size] = iterable
        for i in range(self._offset - 1, -1, -1):
            data[i] = op(data[i * 2 + 1], data[i * 2 + 2])

    def query(self, start, stop):
        def iter_segments(data, l, r):
            while l < r:
                if l & 1 == 0:
                    yield data[l]
                if r & 1 == 0:
                    yield data[r - 1]
                l = l // 2
                r = (r - 1) // 2
        op = self._op
        it = iter_segments(self._data, start + self._offset,
                           stop + self._offset)
        result = self._e
        for v in it:
            result = op(result, v)
        return result

readline = stdin.readline

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

ab.sort(key=lambda x: x[1])
st = SegmentTree(N - 1, add, 0)

result = 0
for a, b in ab:
    a, b = a - 1, b - 1
    if st.query(a, b) != 0:
        continue
    result += 1
    st[b - 1] = 1
print(result)

Submission status: Accepted

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

l=[list(map(int,input().split())) for i in range(m)]
from operator import itemgetter as it
l.sort(key=it(1))
head=0
ans=0
for a,b in l:
    if not(a<head<=b):ans+=1;head=b
print(ans)

Submission status: Accepted

Solution code:

icase=0
if icase==0:
    n,m=map(int,input().split())
    ab=[[0]*2 for i in range(m)]
    for i in range(m):
        ai,bi=map(int,input().split())
        ab[i]=[ai-1,bi-1]
    ab.sort(reverse=True)
elif icase==1:
    n,m=5,2
    ab=[[1, 4], [0, 3]]
elif icase==2:
    n,m=9,5
    ab=[[6, 8], [3, 5], [2, 4], [1, 6], [0, 7]]
elif icase==3:
    n,m=5,10
    ab=[[3, 4], [2, 4], [2, 3], [1, 4], [1, 3], [1, 2], [0, 4], [0, 3], [0, 2], [0, 1]]

istat=0
icnt=0
while True:
    lower=ab[istat][0]
#    print(istat,lower)
    ii=istat
    while lower<ab[ii][1]:
        ii+=1
        if ii>=m:
            break
    istat=ii
    icnt+=1
    if ii>=m:
        break
    
print(icnt)

Submission status: Accepted

Solution code:
def IslandsWar():
    n, m = map(int, input().split())
    a = [list(map(int,input().split())) for _ in range(m)]
    a.sort(key=lambda x: x[1])
    removes = [a[0][1]]

    for i, j in a[1:]:
        check = False
        for k in removes:
            if i < k:
                check = True
                break
        if not check:
            removes.append(j)
    print(len(removes))
            
if __name__ == "__main__":
    IslandsWar()

Submission status: Accepted

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

a_b_l = sorted(a_b_l, key=lambda x: x[1])
ans = 0
prev_removed_bridge = 0
for a, b in a_b_l:
    if a <= prev_removed_bridge:
        continue
    prev_removed_bridge = b - 1
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    N, M = list(map(int, input().split()))
    requests = []
    for i in range(M):
        a_i, b_i = list(map(int, input().split()))
        requests.append((a_i, b_i))

    return N, M, requests


def main(N: int, M: int, requests: list) -> None:
    """
    メイン処理.

    Args:\n
        N (int): 島の数(2 <= N <= 10^5)
        M (int): 要望の数(1 <= M <= 10^5)
        requests (list): 要望(1 <= a_i < b_i <= N)
    """
    # 求解処理
    requests = sorted(requests, key=lambda x: x[1])
    bridge = 0
    ans = 0
    for i in range(M):
        a_i, b_i = requests[i]
        if a_i > bridge:
            bridge = b_i - 1
            ans += 1

    # 結果出力
    print(ans)


if __name__ == "__main__":
    # 標準入力を取得
    N, M, requests = get_input()

    # メイン処理
    main(N, M, requests)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 標準入力を取得
N, M = list(map(int, input().split()))
requests = []
for i in range(M):
    a_i, b_i = list(map(int, input().split()))
    requests.append((a_i, b_i))

# 求解処理
requests = sorted(requests, key=lambda x: x[1])
bridge = 0
ans = 0
for i in range(M):
    a_i, b_i = requests[i]
    if a_i > bridge:
        bridge = b_i - 1
        ans += 1

# 結果出力
print(ans)

Submission status: Accepted

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

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

ans = 1
current = req[0][1]
for i in range(1, len(req)):
    if req[i][0] < current:
        continue
    current = req[i][1]
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 標準入力を取得
N, M = list(map(int, input().split()))
requests = []
for i in range(M):
    a_i, b_i = list(map(int, input().split()))
    requests.append((a_i, b_i))

# 求解処理
requests = sorted(requests, key=lambda x: x[1])
bridges = [requests[0][1] - 1]
for i in range(M):
    a_i, b_i = requests[i]
    if (bridges[-1] < a_i) or (b_i <= bridges[-1]):
        bridges.append(b_i - 1)
ans = len(bridges)

# 結果出力
print(ans)

Submission status: Accepted

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

intervals = []
for conflict in conflicts:
    intervals.append([conflict[0], conflict[1]-1])

intervals = sorted(intervals, key=lambda x: x[1])#interval[1]の大きい順にソート

count = 0
end = -float("inf")
for interval in intervals:
    if interval[0] > end:
        count += 1
        end = interval[1]

print(count)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
INF = 10**18

def li():
    return [int(x) for x in input().split()]


N, M = li()
# 区間は半開区間 [a, b)
Intervals = [li() for _ in range(M)]

Intervals.sort(key=lambda l: l[1])

last_end = - INF
required_cnt = 0
for interval in Intervals:
    start, end = interval[0], interval[1]
    # 重なってなければ一点必要
    # 半開区間なのでlast_endとstartが等しくても重なってない
    if last_end <= start:
        last_end = end
        required_cnt += 1

print(required_cnt)

Submission status: Accepted

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

left=a[0][0]
right=a[0][1]

ans=1

for i in range(1,m):
  x=a[i][0]
  y=a[i][1]
  
  if left<=x<right:
    left=x
    right=min(right,y)
    
  else:
    ans+=1
    left=x
    right=y
    
print(ans)