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:
# Input
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,m = li()
ab = [(-1, -1)]
for _ in range(m):
    ai, bi = li_()
    ab.append((ai, bi))

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

ans = 0
cur = -1
for ai, bi in ab:
    if ai >= cur:
        ans += 1
        cur = bi

print(ans)

Submission status: Wrong Answer

Solution code:
# Input
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,m = li()
ab = [(-1, -1)]
for _ in range(m):
    ai, bi = li_()
    ab.append((ai, bi))

b = sorted(list(set([bi for _, bi in ab])))
ab.sort()
b.sort()

ans = 0
j = 0
bj = b[j]
for ai, _ in ab:
    if ai >= bj:
        j += 1
        bj = b[j]
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
# Input
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,m = li()
a = [-1]
b = [-1]
for _ in range(m):
    ai, bi = li_()
    a.append(ai)
    b.append(bi)

a.sort()
b.sort()

ans = 0
j = 0
bj = b[j]
for ai in a:
    if ai >= bj:
        while bj == b[j]:
            j += 1
        bj = b[j]
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
# Input
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x) - 1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,m = li()
a = [-1]
b = [-1]
for _ in range(m):
    ai, bi = li_()
    a.append(ai)
    b.append(bi)

a.sort()
b.sort()

ans = 0
j = 0
bj = b[j]
for ai in a:
    if ai >= bj:
        j += 1
        bj = b[j]
        ans += 1

print(ans)

Submission status: Wrong Answer

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

ans = 0
t = 0
for i in range(m):
  if t < l[i][1]:
    ans += 1
    t = l[i][0]
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
war_list = []
divide_list = []
for i in range(M):
    war_list.append(list(map(int,input().split())))
war_list.sort(key = lambda x : x[1])

divide_list = [war_list[0][1]]
for i in range(1,M):
    if  war_list[i][0] < divide_list[-1]:
        pass
    else:
        divide_list.append(divide_list[-1])
    
print(len(divide_list))

Submission status: Wrong Answer

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

abp = []

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

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

dbridge = []

def check(a,b,dbridge):
	for i in range(a,b):
		if i in dbridge:
			return False
	return True

print(abp)

for a,b in abp:
	if check(a,b,dbridge):
		dbridge.append(b-1)
	else:
		pass

print(len(dbridge))

Submission status: Wrong Answer

Solution code:

n, m = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(m)]
print(ab)
ab.sort(key=lambda x:x[1])
print(ab)

ans = 0
endplace = 0
for ai, bi in ab:
    if endplace <= ai:
        endplace = bi
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
w = [list(map(int, input().split())) for _ in range(M)]
w.sort(key=lambda x: x[1])
f = 0
ans = 0
for i in range(M):
    if w[i][0] < f < w[i][1]:
        continue
    f = w[i][1]
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np
N, M = map(int, input().split(" "))
ab = np.array([[i for i in input().split(" ")] for _ in range(M)])

ab_sort = ab[np.argsort(ab[:,1])]
ans = 1
[na, nb] = ab_sort[0]
for a, b in ab_sort[1:]:
    if a >= nb:
        ans += 1
        na = a
        nb = b
print(ans)

Submission status: Wrong Answer

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

A=sorted(A,key=lambda x:x[0])

count = 0
flag=False
for i in range(2*M):
    if A[i][1]==0:
        flag=True
    else:
        if flag:
            count+=1
            flag=False

if flag:
    count+=1

print(count)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
W = [0 for i in range(N)]
X = [0 for i in range(N)]
for i in range(M):
    l,r = map(int, input().split())
    W[l] += 1
    X[r-1] += 1

score = 0
for i in range(N):
    if W[i] >= 1 and X[i] >= 1:
        score += 1

if score == 0:
    score = 1

print(score)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
W = [0 for i in range(N)]
X = [0 for i in range(N)]
for i in range(M):
    l,r = map(int, input().split())
    W[l] += 1
    X[r-1] += 1

print(W,X)
score = 0
for i in range(N):
    if W[i] >= 1 and X[i] >= 1:
        score += 1

if score == 0:
    score = 1    

print(score)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
W = [0 for i in range(N)]
X = [0 for i in range(N)]
for i in range(M):
    l,r = map(int, input().split())
    W[l] += 1
    X[r-1] += 1

score = 0
for i in range(N):
    if W[i] >= 1 and X[i] >= 1:
        score += 1

print(score)

Submission status: Wrong Answer

Solution code:
#方針　もっとも近い敵でない島の集まりを調べると区間スケジュール問題となる。
#一列に並んでいるので飛んだ島とは繋げない
#橋の取り壊しの最小値というが、分割としてはもっとも番号の若いものまでしか無理である。
#最近接の敵である島の数字をもつ配列を考える。
N,M = (int(_) for _ in input().split())
mostNeightborOpponent = [N+1 for _ in range(N)]
#print(mostNeightborOpponent)
for i in range(M):
    a,b = (int(_) for _ in input().split())
    if mostNeightborOpponent[a-1] > b:
        mostNeightborOpponent[a-1] = b
#print(mostNeightborOpponent)
#island:・・・島|島・・・の右の島のindex
island = 1
bridgeWillBreak = 0

while island < N:
    minOpIsland = mostNeightborOpponent[island-1]
    for i in range(island-1,N):
        if minOpIsland > mostNeightborOpponent[i]:
            minOpIsland=mostNeightborOpponent[i]
    #print(minOpIsland)
    island = minOpIsland
    if island >= N:
        break
    bridgeWillBreak += 1

print(bridgeWillBreak)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
islands = [0 for i in range(N+1)]
count = 0
s = []
for i in range(M):
	s.append(list(map(int, input().split())))

s.sort(key=lambda a:a[1]-a[0])

for f in s:
	isCover = False
	for i in range(f[0], f[1]):
		if islands[i]:
			isCover = True
	if not isCover:
		for i in range(f[0], f[1]):
			islands[i] = 1 if f[1]-f[0] > 1 else 2

t = ''.join([str(i) for i in islands])
t = [j for j in t.split('1') if len(j) > 0]
print(islands.count(2)+len(t)-1)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
import itertools
import collections
import functools
import math
from queue import Queue
INF = float("inf")


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    cut = []

    # BIT構成
    bit = Bit(N)
    for m in range(M):          # M
        bit.add(a[m], 1)
        bit.add(b[m]+1, -1)

    counter = 0
    for k in range(5):
        # while True:                                   # logM?
        # 最大値を求める
        m, n = -INF, -1
        for i in range(N):
            kari = bit.sum(i+1)
            if m < kari:
                m = kari
                n = i+1

        # 切断する
        cut.append((n, n+1))
        for i in range(M):          # MlogM
            if a[i] <= n and n+1 <= b[i]:
                bit.add(a[i], -1)
                bit.add(b[i]+1, 1)
                a[i] = 0
                b[i] = 0
                counter += 1
        if counter == M:
            break

    print(len(cut))


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [int()] * (M)  # type: "List[int]"
    b = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, M, a, b)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
groop = []
def search(a,b):
    for i in groop:
        if b > i[0] and a < i[1]:
            if b < i[1]:
                i[1] = b
            if a > i[0]:
                i[0] = a
            return True
    return False
for i in range(m):
    a,b = map(int,input().split())
    if not search(a,b):
        groop.append([a,b])
print(len(groop))

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
groop = []
def search(a,b):
    for i in groop:
        if b > i[0] and a < i[1]:
            if b < i[1]:
                i[1] = b
            if a > i[0]:
                i[0] = a
            return True
    return False
for i in range(m):
    a,b = map(int,input().split())
    if not search(a,b):
        groop.append([a,b])
print(len(groop))

Submission status: Wrong Answer

Solution code:
N,M = list(map(int,input().split()))
ab = ([list(map(int,input().split())) for _ in range(M)])
a = sorted(list(set([row[0] for row in ab])),reverse=True)
b = sorted(list(set([row[1] for row in ab])))
i,j = 0,0
cnt = 0
while 1:
    if a[i]<b[j]:
        break
    if cnt%2:
        #jを更新
        if a[i+1] < b[j]:
            while b[j]<=a[i]:
                j+=1
        else:
            j += 1
    else:
        #iを更新
        if a[i] < b[j+1]:
            while b[j]<=a[i]:
                i+=1
        else:
            i += 1
    cnt += 1
print(cnt+1)

Submission status: Wrong Answer

Solution code:
N,M = list(map(int,input().split()))
ab = ([list(map(int,input().split())) for _ in range(M)])
a = sorted(list(set([row[0] for row in ab])),reverse=True)
b = sorted(list(set([row[1] for row in ab])))
i,j = 0,0
while 1:
    if a[i]<b[j]:
        break
    i,j = (i+(i==j),j+(i!=j))
print(i+j+1)

Submission status: Wrong Answer

Solution code:
N,M = list(map(int,input().split()))
ab = ([list(map(int,input().split())) for _ in range(M)])
a = list(set([row[0] for row in ab]))[::-1]
b = list(set([row[1] for row in ab]))
i,j = 0,0
while 1:
    if a[i]<b[j]:
        break
    i,j = (i+(i==j),j+(i!=j))
print(i+j+1)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

N,M = (int(i) for i in input().split())
dic = {}
cnt = 0
pos = 0
for i in range(M):
  a,b = map(int,input().split())
  if a not in dic or dic[a] > b:
    dic[a] = b

for j in sorted(dic.keys()):
  if j >= pos:
    cnt += 1
    pos = dic[j]
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
imput = sys.stdin.readline

N,M = (int(i) for i in input().split())
f1 = 0
t1 = 0
cnt = 0
for i in range(M):
  f2,t2 = map(int,input().split())
  if t1 <= f2:
    cnt += 1
    t1 = t2
  else:
    t1 = min(t1,t2) 
print(cnt)

Submission status: Wrong Answer

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

a = sorted(a)
b = sorted(b)

def search(s,a,b):
    bi = b[0]
    a = [i for i in a if i >= bi]
    if len(a) != 0:
        ai = a[0]
        b = [i for i in b if i > ai]
        return a,b,ai
    else:
        return a,b,0


cnt = 0
n = 1
while n != 0:
    a,b,n = search(n,a,b)
    #print(n)
    cnt+=1
print(cnt)

Submission status: Wrong Answer

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


def search(s):
    for ni in range(s+1,N+1):
        for bi in b:
            if ni == bi:
                for nj in range(bi,N+1):
                    for ai in a:
                        if nj == ai:
                            return ai
                return 0


cnt = 0
n = 1
while n != 0:
    n = search(n)
    #print(n)
    cnt+=1
print(cnt)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
B=[]
for i in range(1,M):
  a,b=map(int,input().split())
  B.append([a,b])
B.sort(key=lambda x:x[1])
ans=0
c=-1
for item in B:
  if item[1]!=c:
    c=item[1]
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
sys.setrecursionlimit(1000000)

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

A.sort(reverse=False)

cnt = 0
bridge = 0

for i in range(M-1):
    #print(i,A[i][0])
    if i == M -2 and A[i+1][0] > bridge:
        cnt += 1
    elif A[i][0] > bridge and A[i][1] < A[i+1][1]:
        cnt += 1
        bridge = A[i][1] - 1
        
print(cnt)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007
sys.setrecursionlimit(1000000)

#A
def A():
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    def bfs(s,g,n,v,ent):
        bfs_map = [-1 for i in range(n)]
        bfs_map[s] = 0
        q = deque()
        q.append(s)
        fin = False
        while q:
            x = q.popleft()
            for y in v[x]:
                if c[x][y] > 0 and bfs_map[y] < 0:
                    bfs_map[y] = bfs_map[x]+1
                    if y == g:
                        fin = True
                        break
                    q.append(y)
            if fin:
                break

        if bfs_map[g] == -1:
            return [None,0]
        path = [None for i in range(bfs_map[g]+1)]
        m = float("inf")
        path[bfs_map[g]] = g
        y = g
        for i in range(bfs_map[g])[::-1]:
            for x in ent[y]:
                if c[x][y] > 0 and bfs_map[x] == bfs_map[y]-1:
                    path[i] = x
                    if c[x][y] < m:
                        m = c[x][y]
                    y = x
                    break
        return [path,m]

    def ford_fulkerson(s,g,c,n,v,ent):
        while 1:
            p,m = bfs(s,g,n,v,ent)
            if not m:break
            for i in range(len(p)-1):
                c[p[i]][p[i+1]] -= m
                c[p[i+1]][p[i]] += m
        return sum(c[g])

    n,m = LI()
    c = [[1 if j == i+1 else 0 for j in range(n+2)] for i in range(n+2)]
    c[0] = [0 for i in range(n+2)]
    c[-1] = [0 for i in range(n+2)]
    c[-2] = [0 for i in range(n+2)]
    ent = [[i-1] for i in range(n+2)]
    v = [[i+1] for i in range(n+2)]
    ent[0] = []
    ent[1] = []
    ent[-1] = []
    v[0] = []
    v[-1] = []
    v[n] = []
    for i in range(m):
        a,b = LI()
        c[0][a] = 1
        c[b][n+1] = 1
        v[0].append(a)
        v[b].append(n+1)
        ent[a].append(0)
        ent[n+1].append(b)
    print(ford_fulkerson(0,n+1,c,n+2,v,ent))
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
AB = sorted([[int(i) for i in input().split()] for i in range(M)], key = lambda x: x[1])

cnt = 1
posi = AB[0][1]
for i in range(1, M):
    if AB[i][0] > posi:
        cnt += 1
        posi = AB[i][1]

print(cnt)

Submission status: Wrong Answer

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

q = sorted(q, key=lambda k: k[0])
q.append((10**5+1, 10**5+1))

t_min = 10**5 + 1
l = 0
r = 1
c = 0
for i in range(1, m + 1):
    
    if q[i][1] < t_min:
        t_min = q[i][1]
        #print("t_min", t_min)
    if q[i][0] != q[i + 1][0]:
        if r <= q[i][0]:
            c += 1
            r = t_min
            t_min = 10**5 + 1
            #print("pp", i)
        else:
            if t_min < r:
                r = t_min
        l = q[i][0]
        #print("lr:", i, l, r)

print(c)

Submission status: Wrong Answer

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

q = sorted(q, key=lambda k: k[0])
q.append((10**5+1, 10**5+1))

t_min = 10**5 + 1
l = 1
r = t_min
c = 1
for i in range(1, m + 1):
    if q[i][1] < t_min:
        t_min = q[i][1]
    if q[i][0] != q[i + 1][0]:
        if r <= q[i][0]:
            c += 1
            r = q[i][1]
            #print("pp")
        else:
            if t_min < r:
                r = t_min
        l = q[i][0]
        #print(l, r)

print(c)

Submission status: Wrong Answer

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

q = sorted(q, key=lambda k: k[0])
q.append((10**5+1, 10**5+1))

t_min = 10**5 + 1
l = 1
r = t_min
c = 1
for i in range(1, m + 1):
    if q[i][1] < t_min:
        t_min = q[i][1]
    if q[i][0] != q[i + 1][0]:
        if r <= i:
            c += 1
            r = q[i][1]
        else:
            if t_min < r:
                r = t_min
        l = q[i][0]

print(c)

Submission status: Wrong Answer

Solution code:
#D問題
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
AB=sorted(AB, key=lambda x: x[1])
bridges=[]
for i in range(M):
    if len(bridges) == 0:
        bridges.append(AB[i][1])
    elif max(bridges)>=AB[i][0]:
        pass
    else:
        bridges.append(AB[i][1]-1)
print(len(bridges))

Submission status: Wrong Answer

Solution code:
#D問題
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]
AB=sorted(AB, key=lambda x: x[1])
bridges=[]
for i in range(M):
    if len(bridges) == 0:
        bridges.append(AB[i][1])
    elif max(bridges)>=AB[i][0]:
        pass
    else:
        bridges.append(AB[i][1])
print(len(bridges))

Submission status: Wrong Answer

Solution code:
#D問題
N,M=map(int,input().split())
kyomu=[]
for i in range(M):
    a,b=map(int,input().split())
    kyomulen=len(kyomu)
    j=0
    flag=0
    for j in range(kyomulen):
        if a>=kyomu[j][0] and b<=kyomu[j][1]:
            del kyomu[j]
            kyomu.append([a,b])
            flag=1
            break
    if flag == 0:
        kyomu.append([a,b])
print(len(kyomu))

Submission status: Wrong Answer

Solution code:
from copy import copy
from collections import deque

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

"""
N=10**5
M=10**5
"""
ab=[]
for i in range(1,N):
    ab.append([i,i+1])

AB=copy(ab)
ab.sort(key=lambda x :x[1])
AB.sort()
ab=deque(ab)
AB=deque(AB)
num=0
while(ab):
    p=ab.popleft()
    AB.remove(p)
    num+=1
    e=p[1]
    Q=copy(AB)
    for I in AB:
        if I[0]<e:
            Q.remove(I)
            ab.remove(I)
        else:
            break
    AB=Q
print(num)

Submission status: Wrong Answer

Solution code:
from collections import deque
N,M=map(int,input().split())
ab=[]
for i in range(M):
    a,b=map(int,input().split())
    ab.append([a,b])

ab.sort(key=lambda x :x[1])
ab=deque(ab)
num=0
while(ab):
    p=ab.popleft()
    num+=1
    e=p[1]
    q=deque()
    for i in range(len(ab)):
        if ab[i][0]<e:
            q.append(ab[i])
    ab=q
print(num)

Submission status: Wrong Answer

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

ends = [[[], []] for _ in range(n+1)]
for i, (a, b) in enumerate(ab, start = 1):
    ends[a][0].append(i)
    ends[b][1].append(i)
# for e in ends: print(e)

ans = 0
orders = set([])
for start, end in ends:
    if len(end) > 0:
        rm_bridge = False
        for e in end:
            if e in orders:
                orders.remove(e)
                rm_bridge = True
        orders = set([])
        ans += int(rm_bridge)
    if len(start) > 0:
        for s in start:
            orders.add(s)
    # print(orders)
print(ans)

Submission status: Wrong Answer

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

counts = [[0, 0] for _ in range(n+1)]
for a, b in ab:
    counts[a][0] += 1
    counts[b][1] += 1
# print(counts)
    
n_close = 0
ans = 0
for ca, cb in counts:
    if cb > 0:
        if n_close > 0:
            ans += 1
            n_close = 0
        else:
            pass
    if ca > 0:
        n_close += 1
print(ans)

Submission status: Wrong Answer

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

ab = sorted(ab)
counts = [[0, 0] for _ in range(n+1)]
for a, b in ab:
    counts[a][0] += 1
    counts[b][1] += 1
# print(counts)
    
n_close = 0
ans = 0
for ca, cb in counts:
    if cb > 0:
        if n_close > 0:
            ans += 1
            n_close = 0
        else:
            pass
    if ca > 0:
        n_close += 1
print(ans)

Submission status: Wrong Answer

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

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

removed = []

for a,b in _input:
    flag = False
    for i in removed:
        if a <= i < 5:
            flag = True
    if not flag:
        removed.append(b-1)

print(len(removed))

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
ab=[[0,0] for i in range(M)]
for i in range(M):
    ab[i][0],ab[i][1]=map(int,input().split())
r=0
ans=0
for i in range(M):
    a=ab[i][0]
    b=ab[i][1]
    if a>=r:
        ans+=1
        r=b
    else:
        if b<r:
            r=b
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = [int(i) for i in input().split()]
e = [[int(j) for j in input().split()] for i in range(m)]
sorted(e,key= lambda x : x[1])
s=[]
for i in e:
  if s!=[] and i[0]<=s[-1]:
    pass
  else:
    s.append(i[1]-1)
    
print(len(s))

Submission status: Wrong Answer

Solution code:
n,m = [int(i) for i in input().split()]
e = [[int(j) for j in input().split()] for i in range(m)]
s =[]
for cmd in e:
  if s==[]:
    s.append(cmd)
  else:
    found = False
    for tmp in s:
      if cmd[0]>=tmp[0] and cmd[0]<tmp[1]:
        tmp[0]=cmd[0]
        found = True
      if cmd[1]>tmp[0] and cmd[1]<=tmp[1]:
        tmp[1]=cmd[1]
        found = True
    if found == False:
      s.append(cmd)

print(len(s))

Submission status: Wrong Answer

Solution code:
#ABC 103D回答
N,M=map(int,input().split())
A=[]
for i in range(M):
    a,b=map(int,input().split())
    A.append([a,b])
B=sorted(A,key=lambda x:x[1])
#print(B)
if M==0:
    print(0)
else:
    c=B[0][1]
    B.pop(0)
    count=1
    while B!=[]:
        if B[0][0]>c:
            count=count+1
            c=B[0][1]
        B.pop(0)
        #print(B)
        #print(count)
    print(count)

Submission status: Wrong Answer

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

cnt = 1
b = SG[0][1]
for s, g in SG[1:]:
    if s >= b:
        b = s + 1
        cnt += 1
        
print(cnt)

Submission status: Wrong Answer

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

cnt = 0
b = 0
for s, g in SG:
    if s >= b:
        b = s + 1
        cnt += 1
        
print(cnt)

Submission status: Wrong Answer

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

cnt = 0
b = 0
for s, g in SG[1:]:
    if s > b:
        b = s
        cnt += 1
        
print(cnt)

Submission status: Wrong Answer

Solution code:
#ABC103D
n,m=map(int,input().split())
from collections import defaultdict
data=set()
start=defaultdict(int)
end=defaultdict(int)
for i in range(m):
    s,e=map(int,input().split())
    data|={(s,e),}
    start[s]+=1
    end[e]+=1
ans=0
nokori=m
while nokori>0:
    now=0
    an=0
    bre=0
    for i in range(1,n):
        now=now+start[i]-end[i]
        if now>an:
            an=now
            bre=i
    ans+=1
    nokori-=an
    kesu=set()
    for x in data:
        if x[0]<=bre and x[1]>bre:
            start[x[0]]-=1
            end[x[1]]-=1
            kesu|={x,}
    data-=kesu
print(ans)

Submission status: Wrong Answer

Solution code:
#O(n)で実装
n,m = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(m)]
rest = sorted(lst, key=lambda x:x[0], reverse=False)
ans = 1
et = rest[0][1] #end_time
for i in range(len(rest)):
    if rest[i][0]>=et:
        et=rest[i][1]
        ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(m)]
ans = 0
#カバーできてないもののうち終了時間の最も早いものを取る
while len(lst)>0:
    ans+=1
    if len(lst)==1:
        break
    et = min(lst, key=lambda x:x[1])[1]
    left,right=0,len(lst)-1
    while left <= right:
        mid = (left+right)//2 #切り捨て
        if lst[mid][0]>=et:
            right-=1
        else:
            left+=1
    lst = lst[left:]
print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
N,M =map(int,input().split(" "))

num =[]
for i in range(M):
    l,m =map(int,input().split(" "))
    x =[m,l]
    num.append(x)
num.sort()
#print(num)
t = num[0][0]
ans =1
for i in range(1,M):
    k =num[i][1]
    if t<k:
        t = k
        ans +=1
print(ans)

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

cut = sorted(cut, key=lambda x: x[0])

ans = 1
ind = 0

print(cut)

s = cut[ind][0]
e = cut[ind][1]
while ind < M:
    n_s, n_e = cut[ind]
    if n_s < e:
        e = min(e, n_e)
    else:
        s = n_s
        e = n_e
        ans += 1
    ind += 1


print(ans)

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

cut = sorted(cut, key=lambda x: x[0])

ans = 1
ind = 0

# print(cut)
start, end = cut.pop(0)
ind += 1
while ind < M:
    n_s, n_e = cut.pop(0)
    ind += 1
    if end > n_s:
        continue
    else:
        start = n_s
        end = n_e
        ans += 1


print(ans)

Submission status: Wrong Answer

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

bridge_counts = [0 for i in range(N - 1)]
for r in requests:
    for i in range(r[0] - 1, r[1] - 1):
        bridge_counts[i] += 1
        
bridges = list(range(N - 1))
bridges.sort(key=lambda x:-bridge_counts[x])

count = 0

for b in bridges:
    removed = False
    for r in requests.copy():
        if r[0] - 1 <= b < r[1] - 1:
            requests.remove(r)
            removed = True
    if removed:
        count += 1
    if len(requests) == 0:
        break
        
print(count)

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    ab = [[int(i) for i in input().split()] for _ in range(M)]
    ab = sorted(ab, key=lambda x: x[1] - x[0])
    d = [ab.pop(0)]
    ans = 1
    for a, b in ab:
        for aa, bb in d:
            if aa >= b or a >= bb:
                ans += 1
    print(ans)


main()

Submission status: Wrong Answer

Solution code:
def main():
    N, M = map(int, input().split())
    ab = [[int(i) for i in input().split()] for _ in range(M)]
    ab = sorted(ab, key=lambda x: x[1] - x[0])
    d = [ab.pop(0)]
    ans = 1
    for a, b in ab:
        for aa, bb in d:
            if aa > b or a > bb:
                ans += 1
    print(ans)


main()

Submission status: Wrong Answer

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

ab = []
ab_tmp = []
for _ in range(M):
  ab_tmp.append(tuple(map(int, input().strip().split())))
for _ab in sorted(ab_tmp, key=lambda x: x[0]):
  a, b = _ab
  ab.append((a, 'L'))
  ab.append((b, 'R'))

prevlr = None
c = 0
for abi, lr in sorted(ab, key=lambda x: x[0]):
  if lr == 'L':
    prevlr = 'L'
  elif lr == 'R':
    if prevlr == 'L':
      c += 1
    prevlr = 'R'
print(c)