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: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jul 21 21:41:43 2018
ABC103D
@author: maezawa
"""

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

w = []
cnt = 1

for i in range(m):
    ai, bi = list(map(int, input().split()))
    ci = set(list(range(ai,bi)))
    w.append(ci)
    
#print(*w)
bsbroken = []
bs0 = w[0]    
for bs in w:
    bsand = bs0 & bs
    if len(bsand) == 0:
        flag = 0
        for seq in bsbroken:
            if len(seq & bs) != 0:
                flag = 1
                break
        if flag == 0:
            cnt += 1
            bsbroken.append(bs0)
            bs0 = bs
    else:
        bs0 = bsand
        
print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = map(int, input().split())

a = np.zeros((M,2))

for i in range(M):
	a[i] = list(map(int, input().split()))

a = a[np.argsort(a[:,1])[::-1]]

prev = 0

a_max = 0
index = M
del_list = []
for i, tmp in enumerate(a):
	if tmp[1] == prev:
		if tmp[0] > a_max:
			del_list.append(index)
			index = i
			a_max = tmp[0]
		else:
			del_list.append(i)
	else:
		prev = tmp[1]
		if tmp[0] > a_max:
			del_list.append(index)
			index = i
			a_max = tmp[0]
		elif a_max >= tmp[1]:
			a_max = tmp[0]
		else:
			del_list.append(i)
del del_list[0]
a = np.delete(a, del_list, 0)

a = a[np.argsort(a[:,0])]

prev = 0
b_min = N+1
index = M
del_list = []
for i, tmp in enumerate(a):
	if tmp[0] == prev:
		if tmp[1] < b_min:
			del_list.append(index)
			index = i
			b_min = tmp[1]
		else:
			del_list.append(i)
	else:
		prev = tmp[0]
		if tmp[1] < b_min:
			del_list.append(index)
			index = i
			b_min = tmp[1]
		elif b_min <= tmp[0]:
			b_min = tmp[1]
		else:
			del_list.append(i)
del del_list[0]
a = np.delete(a, del_list, 0)

a = a[np.argsort(a[:,0])]

prev = 0
b_min = N+1
index = M
del_list = []
for i, tmp in enumerate(a):
	if tmp[0] == prev:
		if tmp[1] < b_min:
			del_list.append(index)
			index = i
			b_min = tmp[1]
		else:
			del_list.append(i)
	else:
		prev = tmp[0]
		if tmp[1] < b_min:
			del_list.append(index)
			index = i
			b_min = tmp[1]
		elif b_min <= tmp[0]:
			b_min = tmp[1]
		else:
			del_list.append(i)
del del_list[0]
a = np.delete(a, del_list, 0)



ans = 0
flg = True
for i in range(len(a[:,0])-1):
	if a[i,1] > a[i+1, 0]:
		ans += 1
		flg = False
	elif flg:
		ans += 1
		flg = True
	else:
		flg = True
if flg:
	ans += 1
print(ans)

Submission status: Wrong Answer

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

ab = []
for i in range(m):
    ab.append(list(map(int, input().split())))

out_ab = []
for a, b in ab:
    for i, old_ab in enumerate(out_ab):
        old_a = old_ab[0]
        old_b = old_ab[1]
        if old_a <= a and b <= old_b:  # どっちも中 or 片方同じ
            out_ab[i] = [a, b]
            break
        elif (a < old_a and b < old_b and old_a < b) or (old_a < a and old_b < b and a < old_b):  # 片方はみ出る
            out_ab[i] = [max(old_a, a), min(old_b, b)]
            break
        elif a < old_a and old_b < b:  # 両方はみ出る
            break
    else:
        out_ab.append([a, b])

print(len(out_ab))

Submission status: Wrong Answer

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

answer=1
left=requests[0][0]
right=requests[0][1]
for i in range(1,M):
    if requests[i][0] <= right and left <= requests[i][1]:
        left=max(left, requests[i][0])
        right=min(right, requests[i][1])
    else:
        answer+=1
        left=max(left, requests[i][0])
        right=min(right, requests[i][1])
print(answer)

Submission status: Wrong Answer

Solution code:
def intersect(r1, r2):
    if (r1[0] <= r2[0] and r2[0] < r1[1]) or \
            (r2[0] <= r1[0] and r1[0] < r2[1]):
        return True, (max(r1[0], r2[0]), min(r1[1], r2[1]))
    return False, None


N, M = [int(c) for c in raw_input().split()]
D = []
for _ in range(M):
    a, b = [int(c) for c in raw_input().split()]
    D.append(tuple([a, b]))

B = []
for d in D:
    if len(B) == 0:
        B.append(d)
        continue

    any_match = False
    for bi, b in enumerate(B):
        x, y = intersect(b, d)
        if x:
            B[bi] = y
            any_match = True
            break
    if not any_match:
        B.append(d)
print len(B)

Submission status: Wrong Answer

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

data = []
data2=[]
for i in range(M):
    data.append(list(map(int, input().split())))
    data2.append(list(range(10*data[i][0]+5,10*data[i][1]+1-5,5)))
ans=set(data2[0])
ct=1
for i in range(1,M):
    if len(ans.intersection(set(data2[i])))>0:
        ans = ans.intersection(set(data2[i]))
    else:
        ct+=1
        ans=set(data2[i])
print(ct)

Submission status: Wrong Answer

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

c = [(-1, -1) for i in range(M)]
for i in range(M):
    a, b = [int(i) for i in input().split()]
    c[i] = (a, b)

c.sort()
c.append((-2, M + 1))

count = 0
prev = -1
for i in range(M):
    if prev == c[i][0]:
        continue
    # print(c[i], c[i + 1])
    if c[i][1] <= c[i + 1][1]:
        count += 1
    prev = c[i][0]

print(count)

Submission status: Wrong Answer

Solution code:
a = list(map(int,input().split()))
b = [0]*a[0]

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

	b[m-1] += 1
	b[n-1] -= 1
ma = b[0]
for i in range(1,a[0]):
	b[i] += b[i-1]
	if b[i] >= ma:
		ma = b[i]
		k = i

print(a[1] - ma)

Submission status: Wrong Answer

Solution code:
from numpy import zeros, all
N, M = map(int, input().split())
d = []
x = zeros(N-1, dtype=int)
for i in range(M):
    ai, bi = map(int, input().split())
    x[ai-1:bi-1] += 1
    # d.append([(bi - ai), ai-1, bi-1])

status = 'stag'
count = 0
for i in range(len(x)-1):
    diff = x[i+1] - x[i]
    if diff == 0:
        s = 'stag'
    elif diff > 0:
        s = 'up'
    else:
        s = 'down'
    if s == 'stag':
        count += 1
    elif (status, s) == ('up', 'down') or (status, s) == ('down', 'up'):
        count += 1
    status = s
print(int(count + x[0] - 1))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(M)]
L = [0] * N
for a,b in ab:
    L[a-1] -= 1
    L[b-1] += 1

def ans(l,n):
    res = 0
    t = 0
    for i in range(1,N):
        if l[i] < 0:
            if l[i-1] >= 0:
                res += t
                t = 0

        elif l[i] == 0:
            if l[i-1] == 0:
                res += 1
            else:
                res += t
                t = 0
        else:
            t = max(t,L[i])
    return res + t
print(ans(L,N))

Submission status: Wrong Answer

Solution code:
import copy
import numpy as np
 
n, m = list(map(int, input().split(" ")))
a = np.zeros(m, dtype=np.int)
b = np.zeros(m, dtype=np.int)
for i in range(m):
    a[i], b[i] = list(map(int, input().split(" ")))
 
ans = 0
while(True):
    island = np.zeros(n, dtype=np.int)
    ans += 1
    for i, j in zip(a, b): island[i:j] += 1
    cut = island.argmax()
    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 = np.array(copy.deepcopy(na))
    b = np.array(copy.deepcopy(nb))
 
print(ans)

Submission status: Wrong Answer

Solution code:
import bisect

n,m = map(int,input().split())	
aaa = [list(map(int,input().split())) for i in range(m)]
ab = sorted(aaa)
#ab = sorted(aaa, key=lambda x: x[0])
#print(ab)
l = []
l.append(ab[0][0]-1)
l.append(ab[0][1]-1)

p = 1

if m != 1:
    

    for i in range(1,m):
        a = ab[i][0]-1
        b = ab[i][1]-1
        a1= bisect.bisect_left(l,a)
        b1= bisect.bisect_left(l,b)
        #print(a,b,a1,b1,l)
        if a1 == b1:
            if a1%2 == 0:
                l.insert(a1,b)
                l.insert(a1,a)
                p += 1
                
            else:
                l[a1-1] = a
                l[a1] = b
        
        elif  b1-1 ==a1:
            if a1%2 == 0:
                l[b1] = b
            elif a == l[a1]:
                l.insert(a1+1,b)
                l.insert(a1+1,a)
                p += 1
            else:
                l[a1] = a
        
print(p)

Submission status: Wrong Answer

Solution code:
N, M = list(map(int, input().split()))
intervals = []
for i in range(M):
    a, b = map(int, input().split())
    newInterval = None
    index = None
    for j in range(len(intervals)):
        s, e = intervals[j]
        if b <= s or e <= a:
            continue

        newInterval = (max(a, s), min(b, e))
        index = j
        break

    if newInterval is None:
        intervals.append((a, b))
    else:
        intervals[index] = newInterval

print(len(intervals))

Submission status: Wrong Answer

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

#一番目のお願いのとき
rangeArr = []
rangeArr.append(aArr[0])
ans = 1

for arIn in aArr[1:]:
    flag = 0
    for ranIn in rangeArr:
        if ranIn[0] < arIn[0] :
            if arIn[0] < ranIn[1]:
                ranIn[0] = arIn[0]
                flag = 1
        if ranIn[1] > arIn[1] :
            ranIn[1] = arIn[1]
            flag = 1
        #print("ranIn中身")
        #print(ranIn[0])
        #print(ranIn[1])
        if flag == 1 :
            break
    if flag == 0 :
        ans = ans + 1
        rangeArr.append(arIn)

print(ans)

Submission status: Wrong Answer

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

groups = [(ABs[0][0], ABs[0][1])]

gidx = 0
flag = True
for e in ABs[1:]:
    for gidx, g in enumerate(groups):
        if (g[1] < e[0]) or (e[1] < g[0]):
            groups.append((e[0], e[1]))
            break
        elif (g[0] <= e[0] or e[1] <= g[1]):
            groups[gidx] = (max(g[0], e[0]), min(g[1], e[1]))
            break

print(len(groups))

Submission status: Wrong Answer

Solution code:
a = list(map(int,input().split()))
b = [0]*a[0]

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

	b[m-1] += 1
	b[n-1] -= 1
ma = b[0]
for i in range(1,a[0]):
	b[i] += b[i-1]
	if b[i] >= ma:
		ma = b[i]
		k = i

print(a[0] - ma)

Submission status: Wrong Answer

Solution code:
N, M = list(map(int,input().strip().split(' ')))
AB = []
for i in range(M):
    AB.append( list(map(int,input().strip().split(' '))) ) 
import functools
import operator
prod = functools.partial(functools.reduce, operator.mul)
minpair = []
ans = 0
for p in AB:
    if not minpair:
        minpair.append(p)
        ans = 1
    else:
        chk = [0 for i in range(len(minpair))]
        for i in range(len(minpair)):
            if (minpair[i][1] <= p[0] and minpair[i][1] < p[1]) or (p[1] <= minpair[i][0] and p[0] <= minpair[i][0]):
                chk[i] = 1
                minpair.append(p)
            elif minpair[i][0] <= p[0] and p[1] <= minpair[i][1] and minpair[i][1] <= p[0]:
                minpair[i] = p
            else:
                if minpair[i][1] <= p[1]:
                    minpair[i][0] = p[0]
                else:
                    minpair[i][1] = p[1]
                
        ans = ans + prod(chk)
        
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, AB):
    DAB = [(b-a, abs(N/2 - (a + b)/2), a, b) for a, b in AB]
    DAB.sort(key=lambda x: x[1])
    DAB.sort(key=lambda x: x[0])
    cut = []

    for _, _, a, b in DAB:
        for c in cut:
            if a <= c < b:
                break
        else:
            cut.append((a+b)//2)
    return len(cut)


def main():
    N, M = read_int_n()
    AB = [read_int_n() for _ in range(M)]
    print(slv(N, M, AB))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def intersect(r1, r2):
    if (r1[0] <= r2[0] and r2[0] < r1[1]) or \
            (r2[0] <= r1[0] and r1[0] < r2[1]):
        return True, (min(r1[0], r2[0]), min(r1[1], r2[1]))
    return False, None


N, M = [int(c) for c in raw_input().split()]
D = []
for _ in range(M):
    a, b = [int(c) for c in raw_input().split()]
    D.append(tuple([a, b]))

B = []
for d in D:
    if len(B) == 0:
        B.append(d)
        continue

    any_match = False
    for bi, b in enumerate(B):
        x, y = intersect(b, d)
        if x:
            B[bi] = y
            any_match = True
            break
    if not any_match:
        B.append(d)
print len(B)

Submission status: Wrong Answer

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

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: Wrong Answer

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

groups = [(ABs[0][0], ABs[0][1])]

gidx = 0
flag = True
for e in ABs[1:]:
    for gidx, g in enumerate(groups):
        if (g[1] < e[0]) or (e[1] < g[0]):
            groups.append((e[0], e[1]))
            break
        elif (g[0] <= e[0] or e[1] <= g[1]):
            groups[gidx] = (max(g[0], e[0]), min(g[1], e[1]))

print(len(groups))

Submission status: Wrong Answer

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=request[0][1]
head = request[0][0]
index = 0
ans = 0

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

while head <= N:
    if head == memory:
        ans +=1
        memory = 0
    elif equal():
        index+=1
        memory=min(request[index][1],memory)
    else: head +=1
        
print(ans)

Submission status: Wrong Answer

Solution code:
NM = list(map(int, input().split()))
b = []
for i in range(NM[1]):
	ab = list(map(int, input().split()))
	flag = 1
	for i in range(len(b)):
		if (b[i][1] < ab[0] and b[i][0] < ab[0] ):
			b[i][0] = ab[0]
			flag = 0
			break
		if(b[i][0] > ab[1] and b[i][1] > ab[1]):
			b[i][1] = ab[1] 
			flag = 0
			break
		if (flag):
			b.append(ab)
			flag = 1

print(len(b))

Submission status: Wrong Answer

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

data = []
data2=[]
for i in range(M):
    data.append(list(map(int, input().split())))
    data2.append(list(range(10*data[i][0]+5,10*data[i][1]+1-5,5)))
print(data2)
ans=set(data2[0])
ct=1
for i in range(1,M):
    if len(ans.intersection(set(data2[i])))>0:
        ans = ans.intersection(set(data2[i]))
        print(ans)
    else:
        ct+=1
        ans=set(data2[i])
print(ct)
# AB = [x for x in zip(*data)]
# A=list(AB[0])
# B=list(AB[1])
#
# print(A)
# print(B)

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
stock = [[1,N]]
for i in range(M):
    a, b = map(int,input().split())
    for j in range(len(stock)):
        suba, subb = stock[j][0], stock[j][1]
        maxa = max(a,suba)
        minb = min(b,subb)
        if maxa < minb:
            stock[j][0] = maxa
            stock[j][1] = minb
            break
        if j == len(stock)-1:
            stock.append([a,b])
print(len(stock))

Submission status: Wrong Answer

Solution code:
import copy
import numpy as np
 
n, m = list(map(int, input().split(" ")))
a = np.zeros(m, dtype=np.int)
b = np.zeros(m, dtype=np.int)
for i in range(m):
    a[i], b[i] = list(map(int, input().split(" ")))
 
ans = 0
while(True):
    island = np.zeros(n, dtype=np.int)
    ans += 1
    for i, j in zip(a, b):
        for k in range(i, j, 1):
            island[i:j] += 1
    cut = island.argmax()
 
    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 = np.array(copy.deepcopy(na))
    b = np.array(copy.deepcopy(nb))
 
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
n,m = map(int, input().split())
ask = np.array([list(map(int, input().split())) for i in range(m)],dtype=int)


if n*(n-1)//2==m:
    print(n-1)
    sys.exit()

delete = set([i for i in range(1,n+1)])
for a in ask:
    b = set([i for i in range(a[0],a[1]+1)])
    tmp = delete & b
    if tmp==set():
        delete = delete | b
    else:
        delete = tmp
delete = np.sort(list(delete))
print(len(delete[np.where(delete[1:] - delete[:-1]!=1)]) + 1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict

n, m = map(int, input().split())
r_list = []

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

for i, r_range in enumerate(r_list):
  r_list[i] = list(range(r_range[0], r_range[1]))

def create_count_dict(r_list):
  count_dict = defaultdict(int)
  for r_range in r_list:
    for i in r_range:
      count_dict[i] += 1

  return count_dict

bridge_count = 0

while len(r_list) > 0:
  bridge_count += 1
  island_count_dict = create_count_dict(r_list)
  max_k = max(island_count_dict, key=island_count_dict.get)
  for r_range in r_list:
    if max_k in r_range:
      r_list.remove(r_range)

print(bridge_count)

Submission status: Wrong Answer

Solution code:
def cut(dem,c):
    res = []
    for d in dem:
        if c < d[0] or c >= d[1]:
            res.append(d)
    return res

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

demand = []

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

demand.sort()

res = 0

while len(demand) != 0:
    min_dem_len = n
    min_dem_ind = 0
    for i in range(len(demand)):
        if demand[i][1]-demand[i][0] < min_dem_len:
            min_dem_len = demand[i][1]-demand[i][0]
            min_dem_ind=i
            if min_dem_len == 1:
                break

    max_dem_del = 0
    max_dem_ind = min_dem_ind
    a = demand[min_dem_ind][0]
    for i in range(min_dem_len):
        dem_del = 0
        for j in range(len(demand)):
            if demand[j][0]<=a+i and a+i < demand[j][1]:
                dem_del+=1
            elif demand[j][0] > a+i:
                break
        if dem_del > max_dem_del:
            max_dem_del = dem_del
            max_dem_ind = a+i

    demand = cut(demand,max_dem_ind)
    res += 1
                
print(res)

Submission status: Wrong Answer

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


ans = 0
while True:
    if len(demand) == 0:
        break
    
    imosu = [0 for _ in range(n)]

    for d in demand:
        f,t = d
        imosu[f] += 1
        imosu[t] -= 1

    for i in range(1,n):
        imosu[i] += imosu[i-1]
        

    index = imosu.index(max(imosu))
    pop_list = []

    for i,d in enumerate(demand):
        if d[0] <= index and index <= d[1]-1:
            pop_list.append(i)

    
    pop_list.sort(reverse=True)
    for i in pop_list:
        demand.pop(i)
    ans += 1
    
    
print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
l = [list(map(int, input().split())) for i in range(m)]
cut_range = [l[0]]
flag = 0
for i in l[1:]:
    for j, elem in enumerate(cut_range):
        flag = 0
        if not(i[1] <= elem[0] or elem[1] <= i[0]):
            cut_range[j] = [max(i[0], elem[0]), min(i[1], elem[1])]
            flag += 1
    if flag == 0:
        cut_range.append(i)
print(len(cut_range))

Submission status: Wrong Answer

Solution code:
def solve(tasks):
    tasks = sorted(tasks, key=lambda x:x[1])
    end = 0
    start = 0
    ans = 0
    for task in tasks:
        if task[1]<start: continue
        end = task[0]
        ans += 1
        start = end
    return ans

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

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

ans = solve(tasks)
print(ans)

Submission status: Wrong Answer

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

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)-1,0-1,-1):
    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: Wrong Answer

Solution code:
import numpy as np
N, M = map(int, input().split())

a = np.zeros((M,2))

for i in range(M):
	a[i] = list(map(int, input().split()))

a = a[np.argsort(a[:,0])]

prev = 0
b_min = N+1
index = M
del_list = []
for i, tmp in enumerate(a):
	if tmp[0] == prev:
		if tmp[1] < b_min:
			del_list.append(index)
			index = i
			b_min = tmp[1]
		else:
			del_list.append(i)
	else:
		prev = tmp[0]
		if tmp[1] < b_min:
			del_list.append(index)
			index = i
			b_min = tmp[1]
		elif b_min <= tmp[0]:
			b_min = tmp[1]
		else:
			del_list.append(i)
del del_list[0]
a = np.delete(a, del_list, 0)

ans = 0
flg = True
for i in range(len(a[:,0])-1):
	if a[i,1] > a[i+1, 0]:
		ans += 1
		flg = False
	elif flg:
		ans += 1
		flg = True
	else:
		flg = True
if flg:
	ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
n, m = map(int, input().split())
# demands = [tuple(map(int, input().split())) for i in range(m)]
demands = [
    tuple(map(int,
              line.strip().split())) for line in sys.stdin.readlines()
]

compressed = []
while demands:
    a, b = demands.pop()
    for i, (ai, bi) in enumerate(compressed):
        if b <= ai or bi <= a:
            continue

        else:
            if a > ai:
                compressed[i][0] = a
            if b < bi:
                compressed[i][1] = b
            break

    else:
        compressed.append([a, b])

print(len(compressed))

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jul 21 21:41:43 2018
ABC103D
@author: maezawa
"""

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

w = []
cnt = 1

for i in range(m):
    ai, bi = list(map(int, input().split()))
    ci = set(list(range(ai,bi)))
    w.append(ci)
    
#print(*w)
    
bs0 = w[0]    
for bs in w:
    bsand = bs0 & bs
    if len(bsand) == 0:
        cnt += 1
        bs0 = bs
    else:
        bs0 = bsand
        
print(cnt)

Submission status: Wrong Answer

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

op = [[a[0], b[0]]]
for i in range(1, m):
    for j in range(len(op)):
        is_add = False
        if a[i] >= op[j][1] or b[i] <= op[j][0]:
            is_add = True
            continue

        if a[i] >= op[j][0] and b[i] <= op[j][1]:
            is_add = False
            op[j][0] = a[i]
            op[j][1] = b[i]
            break
        elif a[i] > op[j][0] and b[i] > op[j][1]:
            is_add = False
            op[j][0] = a[i]
        elif a[i] < op[j][0] and b[i] < op[j][1]:
            is_add = False
            op[j][1] = b[i]

    if is_add:
        op.append([a[i], b[i]])


print(len(op))

Submission status: Wrong Answer

Solution code:
def intersect(r1, r2):
    if (r1[0] < r2[0] and r2[0] < r1[1]) or \
            (r2[0] < r1[0] and r1[0] < r2[1]):
        return True, (min(r1[0], r2[0]), min(r1[1], r2[1]))
    return False, None


N, M = [int(c) for c in raw_input().split()]
D = []
for _ in range(M):
    a, b = [int(c) for c in raw_input().split()]
    D.append(tuple([a, b]))

B = []
for d in D:
    if len(B) == 0:
        B.append(d)
        continue

    any_match = False
    for bi, b in enumerate(B):
        x, y = intersect(b, d)
        if x:
            B[bi] = y
            any_match = True
            break
    if not any_match:
        B.append(d)
print len(B)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
s = set(range(1,N))
ans = 1
m = []
for i in range(M):
    a, b = map(int, input().split())
    m.append((a,b))
i = 0
while i < M:
    a, b = m[i]
    s = s & set(range(a,b))
    if len(s) == 0:
        ans += 1
        s = set(range(1,N))
        i -= 1
    i += 1
print(ans)

Submission status: Wrong Answer

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

ans=1
for i in range(m):
    c,d=map(int,input().split())
    if(i==0):
        ta=c
        tb=d
        continue
    
    if(ta>=d):
        ans+=1
        ta=c
    else:
        tb=min(tb,d)
    if(tb<=c):
        ans+=1
        tb=d
    else:
        ta=max(ta,c)
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
ayou = []
byou = []
for i in range(m):
    kazu = list(map(int,input().split()))
    a = min(kazu)
    kazu.remove(min(kazu))
    b = max(kazu)
    ayou.append(a)
    byou.append(b)
if n % 2 == 1:
    hanbun = (n-1) / 2
    ans = 1
    for i in range(m):
        if ayou[i] > hanbun or byou[i] < hanbun:
            ans += 1
        else:
            pass
else:
    hanbun = n / 2
    ans = 1
    for i in range(m):
        if ayou[i] >= hanbun or byou[i] <= hanbun:
            ans += 1
        else:
            pass

if ans >= n or n <= m:
    print(n - 1)
else:
    print(ans)

Submission status: Wrong Answer

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


ans = 0
while True:
    if len(demand) == 0:
        break
    
    imosu = [0 for _ in range(n)]

    for d in demand:
        f,t = d
        imosu[f] += 1
        imosu[t] -= 1

    for i in range(1,n):
        imosu[i] += imosu[i-1]
        

    index = imosu.index(max(imosu))
    pop_list = []

    for i,d in enumerate(demand):
        if d[0] <= index and index <= d[1]-1:
            pop_list.append(i)

    
    pop_list.sort(reverse=True)
    for i in pop_list:
        demand.pop(i)

    
    if ans > 4:
        break
    ans += 1
    
    
print(ans)

Submission status: Wrong Answer

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

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

		if hasi == []:
			hasi.append(ls)

		else:
			count = 0
			fl = 1

			for x in hasi:
				if x[1] <= ls[0] or ls[1] <= x[0]:
					count += 1
					continue

				else:
					hasi[count] = [max(x[0], ls[0]), min(x[1], ls[1])]
					fl = 0
					break

			if fl:
				hasi.append(ls)


	print(len(hasi))



if __name__ == '__main__':
	run()

Submission status: Wrong Answer

Solution code:
N, M = list(map(int, input().split()))
intervals = []
for i in range(M):
    a, b = map(int, input().split())
    newInterval = None
    index = None
    for j in range(len(intervals)):
        s, e = intervals[j]
        if b <= s or e <= a:
            continue

        newInterval = (max(a, s), min(b, e))
        if newInterval == intervals[j]:
            newInterval = None
            continue 

        index = j
        break

    if newInterval is None:
        intervals.append((a, b))
    else:
        intervals[j] = newInterval

print(len(intervals))

Submission status: Wrong Answer

Solution code:
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(" ")))


island = n*[0]
for i, j in zip(a, b):
    for k in range(i, j, 1):
        island[k] += 1

ans = 0
tmp = 0
flag = True
for i in island:
    if(flag == True):
        if(i != tmp and i != tmp+1):
            ans += 1
            if(i != tmp): flag = False
    else:
        if(i != tmp-1):
            ans += 1
            if(i != tmp): flag = True
    tmp = i
if(tmp >= 2): ans += 1
            
print(ans)

Submission status: Wrong Answer

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):
    print(count)
    # 優先度チェック
    bridgePriority = islandNum * [0]
    for request in requestList:
        for j in range(request[0], request[1]):
            bridgePriority[j] += 1
    deleteBridgeList = []

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

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

Submission status: Wrong Answer

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

groups = [(ABs[0][0], ABs[0][1])]

gidx = 0
flag = True
for e in ABs[1:]:
    for gidx, g in enumerate(groups):
        if (g[1] < e[0]) or (e[1] < g[0]):
            groups.append((e[0], e[1]))
            break
        elif (g[0] <= e[0] or e[1] <= g[1]):
            groups[gidx] = (max(g[0], e[0]), min(g[1], e[1]))
            break

print(len(groups))