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
# Your code here!


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

S1 = sorted(S, key=lambda x: x[1]-x[0])
S1.reverse()
t=0
i=0
j=0
flug=False

while M-t>0 and i<M-t-1:
    j=0
    flug=False
    while M-t>0 and j<M-t-1:
        
        if S1[i][0]<=S1[j][0] and S1[i][1]>=S1[j][1] and i!=j:
            del S1[i]
            t+=1
            
            flug=True
            break
        j+=1
    if flug==False:
        i+=1
        
        
x=0
y=1
z=0
nagasa=len(S1)
S1.sort()
while nagasa>x+z:
    hikaku=S1[x][1]
    flug=False
    while nagasa>y+z:
        if S1[y][0]<S1[x][1]:
            del S1[y]
            z+=1
            flug=True
        if flug==False:
            y+=1
        flug=False
    x+=1        
            

print(len(S1))

Submission status: Wrong Answer

Solution code:
def run(n, m, ab):
    ab = sorted(ab)
    cnt = 1
    b = ab[0][1]
    for i in range(1, m):
        a = ab[i][0]
        if b < a:
            cnt += 1
        b = ab[i][1]
    return cnt


def read_line():
    n, m = list(map(int, input().split()))
    ab = []
    for i in range(m):
        a, b = list(map(int, input().split()))
        ab.append([a, b])
    return (n, m, ab)


def main():
    n, m, ab = read_line()
    print(run(n, m, ab))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
def drop(islinds,problem):
    a=set()
    i=0
    while len(a)<len(problem):
        if i>=len(islinds)-1:
            break
        a.add(islinds[i])
        i+=1
    new_islinds=islinds[:i]
    new_problem=set(islinds[i:])
    if 0 in new_problem:
        new_problem.remove(0)
    return new_islinds,new_problem

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

Submission status: Wrong Answer

Solution code:
NM = list(map(int, input().split()))
b = [list(map(int, input().split()))]
for i in range(NM[1]-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 = list(map(int, input().split()))
k = [[0]*2]*n
for i in range(m):
	a, b = list(map(int, input().split()))
	k[a-1].append(b-1)

cnt = 0
i = 0
bf = False
for x in range(n-1):
	for j in range(i+1,n):
		for l in range(i,j):
			if j in k[l]:
				bf = True
				break
		if bf:
			bf = False
			cnt += j
			break
	i = j+1;
	if i > n:
		break;

print(n-1 - cnt)

Submission status: Wrong Answer

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

ab = []

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

ab_ = sorted(ab, key=lambda x: x[0])
ab = []
pre = 0

for i in range(len(ab_)-1):
    if ab_[i][0] != ab_[i+1][0]:
        ab.append(min(ab_[pre:i+1], key=lambda x: x[1]))
        pre = i+1

ab.append(min(ab_[pre:], key=lambda x: x[1]))

min_ = ab[0][1]
count = 0
for t in ab[1:]:
    if t[0] > min_:
        count += 1
        min_ = t[1]
    min_ = min(min_, t[1])

print(min_)

Submission status: Wrong Answer

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] == Rqst[i][0] + 1:
        i += 1
    else:
        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: Wrong Answer

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

for i in range(0, m):
    a, b = list(map(int, input().split()))
    l[a-1] = max([l[a-1],b-2])

right = -1
count = 0

for i in range(0, n-1):
    if i > right and l[i] >= i:
        count += 1
        right = l[i]
    elif i <= right and l[i] >= i:
        right = l[i]

print(count)

Submission status: Wrong Answer

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

todo = []
lis = [0 for _ in range(n+1)]

for i in range(m):
    _ = list(map(int,input().split()))
    lis[_[0] -1] += 1
    lis[_[1] ] = lis[_[1] ] -1
            
    
for i in range(1,len(lis)):
    lis[i] = lis[i] + lis[i-1]
    
count  = 0
#print(lis)
for i in range(len(lis)-1):
    if lis[i]>lis[i+1] and lis[i+1] != 0:
        count += 1
    
print(count)

Submission status: Wrong Answer

Solution code:
import collections

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


requests = []
for i in range(m):
    a,b = map(int, input().split())
    requests.append((b-1,-a+1))
requests.sort()
cnt = 0
lb = -1
for b,a in requests:
    if lb < a or b<= lb:
        cnt += 1
        lb = b-1
print(cnt)

Submission status: Wrong Answer

Solution code:
#! /usr/bin/env python3

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

a = [0 for _ in range(m)]
b = [0 for _ in range(m)]

wars = []

bridges= [0 for _ in range(n-1)]

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

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

reduced_wars = []

res = 0
for i in range(len(wars)):
    a = wars[i][1]
    b = wars[i][2]
    dup = False
    for j in range(len(reduced_wars)):
        if a <= reduced_wars[j][0] and b >= reduced_wars[j][1]:
            dup = True
            break
    if dup == False:
        reduced_wars.append([a, b])
        for j in range(a, b):
            bridges[j] += 1

while True:
    res += 1
    bmax = bridges.index(max(bridges))

    size = len(reduced_wars)
    for i in range(size):
        idx = size - i - 1
        if bmax >= reduced_wars[idx][0] and bmax < reduced_wars[idx][1]:
            del reduced_wars[idx]
    
    if len(reduced_wars) == 0:
        break

    bridges= [0 for _ in range(n-1)]
    for i in range(len(reduced_wars)):
        for j in range(reduced_wars[i][0], reduced_wars[i][1]):
            bridges[j] += 1        

print(res)

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])]
groups_initial = [(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]):
            gi1, gi2 = groups_initial[gidx]
            groups.append((max(gi1, e[0]), min(gi2, e[1])))
            groups_initial.append((max(gi1, e[0]), min(gi2, 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:
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
broken=np.zeros(n+1).astype(bool)
for i in range(m):
  a,b=conf[i]
  tmp = broken[a:b]
  if np.sum(tmp) == 0:
    p = np.argmax(f[a:b])+1
    broken[p]=True
    cnt +=1
print(cnt)

Submission status: Wrong Answer

Solution code:
N, M = list(map(int, input().split())) # 整数
a = []
b = []
for i in range(M):
    a.append(list(map(int, input().split())))
    b.append(set(range(a[i][0]+1, a[i][1] + 1)))
    
c = b[0]
for i in range(M-1):
    c = c & b[i+1]
print(len(c) - 1)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys
n, m = map(int, input().split())
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:
            compressed[i] = [max(a, ai), min(b, bi)]
            break

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

print(len(compressed))

Submission status: Wrong Answer

Solution code:
def main():
        run()

def run():
        n, m = input().split(" ")
        n = int(n)
        m = int(m)
        combs = [(1, n)]
        for _ in range(m):
                a, b = input().split(" ")
                a = int(a)
                b = int(b)
                if a > b:
                        temp = a
                        a = b
                        b = temp
                isNone = False
                for comb in combs:
                        min_, max_ = comb
                        if min_ <= a and a < max_:
                                if max_ >= b and min_ < b: 
                                        combs.remove(comb)
                                        combs.append((a, b))
                                else:
                                        combs.remove(comb)
                                        combs.append((a, max_))
                                isNone = False
                                break


                        else:
                                if max_ >= b and min_ < b:
                                        combs.remove(comb)
                                        combs.append((min_, b))
                                        isNone = False
                                        break
                                else:
                                        isNone = True
                if isNone:
                        combs.append((a, b))
        print(len(combs))
if __name__ == "__main__":
        main()

Submission status: Wrong Answer

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):
    l1 = [v1 for (v1,_) in l]
    l2 = [v2 for (_,v2) in l]
    l1.sort()
    l2.sort()

    count = 1

    ma = max(l1)
    mi = min(l2)

    flag = "n"

    for i in range(len(l)):
        if l1[i] >= mi:
            if bisect.bisect_left(l2,l1[i]) != bisect.bisect_left(l2,l1[i-1]):
                count+=1
    return count




result = do(l)
print(result)

Submission status: Wrong Answer

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, (B, m))
    
count = 0
minnum = -1
for _ in range(M):
    n, q = heapq.heappop(p)
    if minnum in q:
        continue
    minnum = n
    count += 1

print(count)

Submission status: Wrong Answer

Solution code:
ip1 = input().split()
M = int(ip1[1])
buf = []
def conf(char):
    data = []
    ip = char.split()
    for i in ip:
        data.append(int(i))
    return data

buf.append(conf(input()))

for i in range(M-1):
    order = conf(input())
    for j in range(len(buf)):
        if buf[j][0] < order[0] and buf[j][1] > order[0]:
            buf[j][0] = order[0]
        elif buf[j][0] > order[1] and buf[j][1] < order[1]:
            buf[j][1] = order[1]
        elif buf[j][0] > order[1] and buf[j][1] < order[0]:
            buf.append(order)

print(len(buf))

Submission status: Wrong Answer

Solution code:
import numpy as np

N,M = [int(i) for i in input().split()]
brgs = [[0,0] for i in range(M)]
for i in range(M):
    brgs[i] = [int(i) for i in input().split()]
b = np.array(brgs)

#c = np.argsort(b[:,0], axis = 0)
#b = b[:,c]

nondlt = [0]
tmp = b[0,0]
end = b[0,1]
for i in range(1,M):
    row, row1 = b[i,:]
    if tmp == row:
        pass
    elif tmp != row and row1 < end:
        tmp = row
        end = row1
        nondlt.append(i)

b = b[nondlt,:]

c = np.argsort(b[:,1], axis = 0)
b = b[c,:]

nondlt1 = [0]
tmp = b[0,1]
end = b[0,0]
for row1, row in b:
    if tmp == row:
        pass
    elif tmp != row and row1 > end:
        tmp = row
        end = row1
        nondlt.append(i)

print(len(nondlt))

Submission status: Wrong Answer

Solution code:
NM = list(map(int, input().split()))
b = [list(map(int, input().split()))]
for i in range(NM[1]-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())

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

# フィルタ
fms = []

for a, b in ms:
    is_append = True
    for index in range(len(fms)):
        pa, pb = fms[index]
        if a <= pa and pb <= b:
            is_append = False
            break
        elif pa < a and  b < pb:
            fms[index] = (a, b)
            is_append = False
            break
        elif pa < pb and  b < pb:
            is_append = False
            break
        elif a  < pb and pb < b:
            is_append = False
            break
    if is_append:
        fms.append((a, b))


print(len(fms))

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] :
            if arIn[1] > ranIn[0]:
                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:
def main():
    """
    2 <= N <= 10^5
    1 <= M <= 10^5
    1 <= ai < bi <= N
    (ai, bi) != (aj, bj)
    """
    N, M = map(int, input().split())
    A, B = zip(*[
        map(int, input().split())
        for _ in range(M)
    ])
    ans = f(N, M, A, B)
    #ans = TLE(N, M, A, B)

    print(ans)


def TLE(N, M, A, B):
    """
    """
    ans = N - 1
    for a in A:
        for b in B:
            pass

    return ans


def f(N, M, A, B):
    """
    ai, bi の分断:

    入力例1
        1, 4 の分断
            橋1-3 のどれかを除去
        2, 5 の分断
            橋2-4 のどれかを除去
        共通部: 2-3
        要望ごとの共通部を探す必要がある
            M^2: TLE

    A_min: 西
    A_max: 東
    B_min: 西
    B_max: 東

    入力例2
    9 5
    1------8
     2----7
      3-5
       4-6
          7-9

    a_min,b_max の順に並べる
    要望の東側が以前の西側未満ならOK
    要望の西側が以前の東側を超えないならOK ? 
    """
    ab = sorted(zip(A, B), key=lambda x: (x[0], -x[1]))
    ans = 0
    bef_a, bef_b = -1, float("inf")
    for i, (a, b) in enumerate(ab):
        #print(" " * (a-1), a, "-" * (b - a - 1), b, sep="")
        if bef_a <= a < b <= bef_b:
            pass
        elif bef_b <= a:
            ans += 1
        elif bef_a < a < bef_b < b:
            pass

        bef_a, bef_b = a, b

    return ans + 1


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

breaking = [AB[0]]

for ab in AB:
    for i, hoge in enumerate(breaking):
        if (ab[0] >= hoge[0] and ab[1] < hoge[1]) or (ab[0] > hoge[0] and ab[1] <= hoge[1]):
            breaking[i] = ab
        elif ab[1] <= hoge[0] or ab[0] >= hoge[1]:
            breaking.append(ab)

print(len(set(breaking)))

Submission status: Wrong Answer

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

Z = [N+1] * (N + 1)

Z = {}

for i in range(M):
    a, b = map(int, raw_input().split(' '))
    if a not in Z:
        Z[a] = b
    elif b < Z[a]:
        Z[a] = b

l = zip(Z.keys(), Z.values())
count = 0
for i in range(1, len(l)):
    print '-', l[i][0], l[i-1][1]
    if l[i][0] >= l[i-1][1]:
        count += 1


print count + 1

Submission status: Wrong Answer

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

todo = []
lis = [0 for _ in range(n+1)]

for i in range(m):
    if todo == []:
        todo.append(list(map(int,input().split())))
    else:
        one_input = list(map(int,input().split()))
        flag = 0
        for onepass in todo:
            if onepass[0] <= one_input[0] and one_input[1] <= onepass[0]:
                onepass = one_input
                flag = 1
                break
        if flag == 1:
            continue
        else:
            todo.append(one_input)
            
for _ in todo:
    lis[_[0] -1] += 1
    lis[_[1] ] = lis[_[1] ] -1
    
    
for i in range(1,len(lis)):
    lis[i] = lis[i] + lis[i-1]
    
count  = 0
#print(lis)
for i in range(len(lis)-1):
    if lis[i]>lis[i+1] and lis[i+1] != 0:
        count += 1
    
print(count)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
x = []
for i in range(M):
    a,b=[int(i) for i in input().split()]
    x.append([a,b])
zan = [x[0]]
for i in range(1,M):
  if zan[-1][0] == x[i][0]:
    pass
  else:
    zan.append(x[i])
ans = 0
while zan:
  are = zan.pop(0)
  are = are[1]
  ans += 1
  i = 0
  while zan:
      if zan[i][0] <= are:
        if zan[i][1] <= are:
          zan.pop(i)
        else:
          i +=1
      else:
        i += 1
      try:
        if zan[i][0] > are:
          break
      except:
        break
print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import numpy as np

N, req = [int(i) for i in input().split()]
A = np.array([[int(j) for j in input().split()] for i in range(req)])
diff_A = [abs(A[i][0] - A[i][1]) for i in range(req)]
bridge = np.ones(N - 1, int)
sort_diff = np.array(sorted(diff_A))

count = 0
for diff in sort_diff:
    for a_i in A[diff_A == diff]:
        if sum(bridge[a_i[0]:a_i[1]]) >= 1:
            bridge[list(bridge).index(1)] = 0  # 差が小さいものから] # 差が小さいものから]
            count += 1
        else:
            continue
print(count)

Submission status: Wrong Answer

Solution code:
import numpy as np

N,M = [int(i) for i in input().split()]
brgs = [[0,0] for i in range(M)]
for i in range(M):
    brgs[i] = [int(i) for i in input().split()]
b = np.array(brgs)

#c = np.argsort(b[:,0], axis = 0)
#b = b[:,c]

nondlt = [0]
tmp = b[0,0]
end = b[0,1]
for i in range(1,M):
    row, row1 = b[i,:]
    if tmp == row:
        pass
    elif tmp != row and row1 <= end:
        tmp = row
        end = row1
        nondlt.append(i)

b = b[nondlt,:]

c = np.argsort(b[:,1], axis = 0)
b = b[c,:]

nondlt1 = [0]
tmp = b[0,1]
end = b[0,0]
for row1, row in b:
    if tmp == row:
        pass
    elif tmp != row and row1 >= end:
        tmp = row
        end = row1
        nondlt.append(i)

print(len(nondlt))

Submission status: Wrong Answer

Solution code:
import numpy as np

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

a = np.zeros(M, dtype='int')
b = np.zeros(M, dtype='int')
for i in range(M):
    a[i], b[i] = map(int, input().split())

def fun_num_cut_interval(x, a, b):
    return sum( (x >= a[i]) and (x < b[i]) for i in range(len(a)) )

num_cut = 0
while True:
    ind = np.argmin(b - a)
    cut_bridge = a[ind]
    num_cut_interval = fun_num_cut_interval(cut_bridge, a, b)
    for bridge in range(a[ind]+1, b[ind]):
        tmp_num_cut_interval = fun_num_cut_interval(bridge, a, b)
        if tmp_num_cut_interval > num_cut_interval:
            cut_bridge = bridge
            num_cut_interval = tmp_num_cut_interval
            
    num_cut += 1
            
    delete_ind = [i for i in range(len(a)) if ( (cut_bridge >= a[i]) and ( cut_bridge < b[i]) )  ]
    a = np.delete(a, delete_ind)
    b = np.delete(b, delete_ind)
    
    print(cut_bridge, a, delete_ind)
    if len(a) == 0:
        break
        
print(num_cut)

Submission status: Wrong Answer

Solution code:
n, m = (int(i) for i in input().split())
e = [[int(i) for i in input().split()] for i in range(m)]
g = 1
a = 0
for i in range(m):
    for j in range(a, i+1):
        if e[i][0] < e[j][1]:
            pass
        else:
            a = i
            g += 1
            break
print(g)

Submission status: Wrong Answer

Solution code:
class Range:
    def __init__(self, left=None, right=None):
        self.left = left
        self.right = right

    def contains(self, other):
        return self.left <= other.left and other.right <= self.right

    def intersects(self, other):
        if other.right <= self.left:
            return False
        if self.right <= other.left:
            return False
        return True

    def __str__(self):
        return '({}, {})'.format(self.left, self.right)

    def __repr__(self):
        return '({}, {})'.format(self.left, self.right)


if __name__ == '__main__':
    n, m = map(int, input().split())

    # n, m = 5, 10
    # ab = [(1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 4), (2, 5),
    #       (3, 4), (3, 5), (4, 5)]

    # first time
    a_i, b_i = map(int, input().split())

    # range_candidate = Range(ab[0][0], ab[0][1])
    range_candidate = Range(a_i, b_i)
    range_groups = [range_candidate]

    for i in range(1, m):
        # a_i, b_i = ab[i]
        a_i, b_i = map(int, input().split())

        range_candidate = Range(a_i, b_i)
        append_flag = True
        for r in range_groups:
            if r.intersects(range_candidate):
                new_r = Range(max(r.left, range_candidate.left),
                              min(r.right, range_candidate.right))
                range_groups[range_groups.index(r)] = new_r

                append_flag = False
                break

        if append_flag:
            range_groups.append(range_candidate)

    # print(range_groups)
    print(len(range_groups))

Submission status: Wrong Answer

Solution code:
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(" ")))
 
island = np.zeros(n, dtype=np.int)
for i, j in zip(a, b): island[i:j] += 1

print(sum(island) // n)

Submission status: Wrong Answer

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

    l = [a[0]]
    for m in a:
        for l_e in l:
            if m[1] < l_e[0] or l_e[1] < m[0]:
                l.append(m)
                break
            if l_e[0] < m[0] and m[1] < l_e[1]:
                l.remove(l_e)
                l.append(m)
    print len(l)

main()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
input_list = [[int(i) for i in input().split()] for j in range(M)]
ans = 1
first = 0
latter = 0
for i in range(M):
    if i == 0:
        first = input_list[i][0]
        latter = input_list[i][1]
    else:
        if first == input_list[i][0]:
            pass
        else:
            if latter == input_list[i][0] + 1:
                ans += 1
                first = input_list[i][0]
                latter = input_list[i][1]
            elif latter == input_list[i][0]:
                ans += 1
                first = input_list[i][0]
                latter = input_list[i][1]
            else:
                first = input_list[i][0]
                if latter > input_list[i][1]:
                    latter = input_list[i][1]

print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
X=set(range(M))
AB=[list(map(int,input().split()))for _ in[0]*M]
cnt=0
visited=set()
while len(visited)<M:
    Max,Mi=0,0
    E=[[]for _ in[0]*-~N]
    C=[0]*-~N
    cnt+=1
    for k in X-visited:
        a,b=AB[k]
        for i in range(a,b):
            C[i]+=1
            E[i]+=[k]
            if Max<C[i]:
                Max,Mi=C[i],i
    visited|=set(E[Mi])
print(cnt)

Submission status: Wrong Answer

Solution code:
def main():
        run()

def run():
        n, m = input().split(" ")
        n = int(n)
        m = int(m)
        combs = [(1, n)]
        for _ in range(m):
                a, b = input().split(" ")
                a = int(a)
                b = int(b)
                if a > b:
                        temp = a
                        a = b
                        b = temp
                isNone = False
                for comb in combs:
                        min_, max_ = comb
                        if min_ < a and a < max_:
                                if max_ > b and min_ < b:
                                        combs.remove(comb)
                                        combs.append((a, b))
                                else:
                                        combs.remove(comb)
                                        combs.append((a, max_))
                                isNone = False
                                break


                        else:
                                if max_ > b and min_ < b:
                                        combs.remove(comb)
                                        combs.append((min_, b))
                                        isNone = False
                                        break
                                else:
                                        isNone = True
                if isNone:
                        combs.append((a, b))
        print(len(combs))
if __name__ == "__main__":
        main()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
input_list = [[int(i) for i in input().split()] for j in range(M)]
ans = 1
first = 0
latter = 0
for i in range(M):
    print(first, latter)
    if i == 0:
        first = input_list[i][0]
        latter = input_list[i][1]
    else:
        if first == input_list[i][0]:
            pass
        else:
            if latter == input_list[i][0] + 1:
                ans += 1
                first = input_list[i][0]
                latter = input_list[i][1]
            elif latter == input_list[i][0]:
                ans += 1
                first = input_list[i][0]
                latter = input_list[i][1]
            else:
                first = input_list[i][0]
                if latter > input_list[i][1]:
                    latter = input_list[i][1]

print(ans)

Submission status: Wrong Answer

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

_a, _b = map(int, input().split())
dict_paths = {}
dict_paths[_a] = _b

for i in range(M - 1) :
    a, b = map(int, input().split())
    
    interleave_flg = False

    for k in dict_paths.keys() :
        k_tmp, k_val_tmp = k, dict_paths[k]
        
        # complete intersect
        if a >= k and b <= dict_paths[k] :
            dict_paths.pop(k)
            dict_paths[a] = b
            interleave_flg = True
            
        # nothing required
        elif a <= k and b >= dict_paths[k] :
            interleave_flg = True
            
        # left partial
        elif a < k and b > k and b <= dict_paths[k] :
            dict_paths.pop(k)
            dict_paths[a] = k_val_tmp
            interleave_flg = True
            
        # right partial
        elif a > k and a < dict_paths[k] and b >= dict_paths[k] :
            dict_paths.pop(k)
            dict_paths[k] = b
            interleave_flg = True
            
        if interleave_flg == True :
            break
    
    if interleave_flg == False :
        dict_paths[a] = b
            
print(len(dict_paths))

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

Submission status: Wrong Answer

Solution code:
from sys import stdin


def check(x, y):
    a1, b1 = x
    a2, b2 = y
    if a1 < a2:
        if b1 <= a2:
            return False
    else:
        if b2 <= a1:
            return False
    return True


def main():
    N, M = [int(x) for x in stdin.readline().rstrip().split()]
    ablst = [[int(x) for x in stdin.readline().rstrip().split()]
          for _ in range(M)]
    tmp = [x for x in ablst if x[1] == x[0] - 1]
    tmp += [ablst[0]]
    for ab in ablst[1:]:
        flg = False
        for t in tmp:
            a1, b1 = ab
            a2, b2 = t
            if a1 <= a2 and b1 <= b2:
                flg = True
                break
        if flg:
            continue
        for t in tmp:
            if check(ab, t):
                t[0] = max(ab[0], t[0])
                t[1] = min(ab[1], t[1])
                break
        else:
            tmp.append(ab)
    print(len(tmp))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

compressed = []
while demands:
    a, b = demands.pop()

    flag = False
    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
            flag = True

    if not flag:
        compressed.append([a, b])

print(len(compressed))

Submission status: Wrong Answer

Solution code:
import numpy as np

N,M = [int(i) for i in input().split()]
brgs = [[0,0] for i in range(M)]
for i in range(M):
    brgs[i] = [int(i) for i in input().split()]
b = np.array(brgs)

#c = np.argsort(b[:,0], axis = 0)
#b = b[:,c]

nondlt = [0]
tmp = b[0,0]
end = b[0,1]
for i in range(1,M):
    row, row1 = b[i,:]
    if tmp == row:
        pass
    elif tmp != row and row1 >= end:
        tmp = row
        end = row1
        nondlt.append(i)

b = b[nondlt,:]
print(b)

c = np.argsort(b[:,1], axis = 0)
b = b[c,:]

nondlt1 = [0]
tmp = b[0,1]
end = b[0,0]
for row1, row in b:
    if tmp == row:
        pass
    elif tmp != row and row1 <= end:
        tmp = row
        end = row1
        nondlt.append(i)

print(len(nondlt))