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 -*-
# 標準入力を取得
N, M = list(map(int, input().split()))
a, b = [], []
for i in range(M):
    a_i, b_i = list(map(int, input().split()))
    a.append(a_i)
    b.append(b_i)

# 求解処理
ans = 0
bridges = []
for i in range(M):
    bit = ((1 << b[i]) - 1) - ((1 << a[i]) - 1)
    is_included = False
    j = 0
    while j < ans:
        if bridges[j] & bit > 0:
            bridges[j] = bridges[j] & bit
            is_included = True
            break
        j += 1

    if not is_included:
        bridges.append(bit)
        ans += 1

# 結果出力
print(ans)

Submission status: Wrong Answer

Solution code:
# 初期入力
import sys
input = sys.stdin.readline  #文字列では使わない

N,M = map(int, input().split())
ans =0
x =set(range(1,N))
used =[]
for _ in range(M):
    a,b = map(int, input().split()) #争いのある部分
    # 争いのある部分の積集合⇒壊すべきところ
    ab_set =set(range(a,b))
    if x & ab_set:
        x =x & ab_set

    #共通部分がなかったら壊すべきところが増える
    else:
        for u in used:
            if u & ab_set:
                x = u & ab_set
                continue
        used.append(x)
        ans +=1
        x =ab_set
print(ans +1)

Submission status: Wrong Answer

Solution code:
# 初期入力
import sys
input = sys.stdin.readline  #文字列では使わない

N,M = map(int, input().split())
ans =0
x =set(range(1,N))
for _ in range(M):
    a,b = map(int, input().split()) #争いのある部分
    # 争いのある部分の積集合⇒壊すべきところ
    x =x & set(range(a,b))

    #共通部分がなかったら壊すべきところが増える
    if len(x) ==0:
        ans +=1
        x =set(range(a,b))
print(ans +1)

Submission status: Wrong Answer

Solution code:
n,m= map(int,input().split())
ym=[0]*(n-1)
z=set()
for i in range(m):
    a,b= map(int,input().split())
    z.add((a,b))
    ym[a-1]+=1
    if b<n:ym[b-1]-=1
for j in range(1,n-1):ym[j]+=ym[j-1]
brbroke=0
while len(z)>0:
    ymmax=max(ym)
    if ymmax==1:
        brbroke+=len(z)
        z=set()
    else:
        brbroke+=1
        maxi=ym.index(ymmax)
        newset=set()
        sym=[0]*(n-1)
        zcount=0
        for sz in z:
            if sz[0]<=maxi+1<sz[1]:
                newset.add(sz)
                sym[sz[0]-1]+=1
                if sz[1]<n:sym[sz[1]-1]-=1
                zcount+=1
                if zcount==ymmax:break
        for i in range(1,n-1):sym[i]+=sym[i-1]
        z-=newset
        for i in range(n-1):ym[i]-=sym[i]
print(brbroke)

Submission status: Wrong Answer

Solution code:
# 問題：https://atcoder.jp/contests/abc103/tasks/abc103_d

n, m = map(int, input().strip().split())
a_list = []
b_list = []
for _ in range(m):
    tmp_a, tmp_b = map(int, input().strip().split())
    a_list.append(tmp_a)
    b_list.append(tmp_b)

l_list = []
r_list = []
for a, b in zip(a_list, b_list):
    should_add_a_b = True
    for l, r, i in zip(l_list, r_list, range(len(l_list))):
        if b <= l or r <= a:
            continue
        if l < a:
            l_list[i] = a
        if b < r:
            r_list[i] = b
        should_add_a_b = False
        break
    if should_add_a_b:
        l_list.append(a)
        r_list.append(b)
print(len(l_list))

Submission status: Wrong Answer

Solution code:
# 問題：https://atcoder.jp/contests/abc103/tasks/abc103_d

n, m = map(int, input().strip().split())
a_list = []
b_list = []
for _ in range(m):
    tmp_a, tmp_b = map(int, input().strip().split())
    a_list.append(tmp_a)
    b_list.append(tmp_b)

l_list = []
r_list = []
for a, b in zip(a_list, b_list):
    should_add_a_b = True
    for l, r, i in zip(l_list, r_list, range(len(l_list))):
        if b <= l or r <= a:
            continue
        if l < a:
            l_list[i] = a
        if b < r:
            r_list[i] = b
        should_add_a_b = False
        break
    if should_add_a_b:
        l_list.append(a)
        r_list.append(b)
print(l_list)
print(r_list)
print(len(l_list))

Submission status: Wrong Answer

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

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

ans = 0
while data:
    counts = [0] * (N + 1)
    for a, b in data:
        counts[a] += 1
        counts[b] -= 1
    for i in range(1, len(counts)):
        counts[i] = counts[i - 1] + counts[i]
    counts = counts[1:-1]

    mi, mv = None, 0
    for i, v in enumerate(counts):
        if mv < v:
            mi, mv = i, v
    newdata = []
    for a, b in data:
        if a <= mi + 1 < b:
            continue
        newdata.append((a, b))
    data = newdata
    ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,m=LI()
  l=[LI() for _ in range(m)]
  l=sorted(l,key=lambda x:x[1])

  ans=1
  kiru=l[0][1]
  for x,y in l[1:]:
    if x<kiru<y:
      continue
    ans+=1
    kiru=y

  return ans

# main()
print(main())

Submission status: Wrong Answer

Solution code:

n, m = map(int, input().split())
l = [list(map(int, input().split())) for i in range(m)]

l = sorted(l, key = lambda x:(x[1], x[0]))
cnt = m

for i in range(1, m):
    if l[i-1][1] > l[i][0]:
        l[i][1] = l[i-1][0]
        cnt -= 1

print(cnt)

Submission status: Wrong Answer

Solution code:
import sys

input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    C = [{"L": 0, "R": 0} for _ in range(N)]
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        C[a]["L"] += 1
        C[b]["R"] += 1

    ans = 0
    L_exist = False
    for c in C:
        if L_exist and c["R"] > 0:
            ans += 1
            L_exist = False
        if c["L"] > 0:
            L_exist = True

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

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

# 区間の終端でソート
ab = sorted([tuple(map(int, input().split())) for i in range(m)], key=itemgetter(1))
# 前回除いた橋
removed = -1
ans = 0
print(ab)

for a, b in ab:
    # a が removed より大きい = まだ取り除いてない
    #print(a)
    if a > removed:
        removed = b - 1
        ans += 1
        print("OK")

print(ans)

Submission status: Wrong Answer

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

N,M=list(map(int,input().split()))
#- 1要望 a→c,b→c分断要望に対して、a<bならb→cだけ考慮すればいい -#
want_list = [0]*(N+1)
for _ in range(M):
    a,b = map(int,input().split())
    want_list[b]=max(0,a)


#-分断した時の橋とindexと要望を見比べて、要望を満たしていないならカウントする-#
cnt = 0
cutNo = 0
for idx,val in enumerate(want_list):
    if val >cutNo:
        cutNo = idx-1
        cnt += 1
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

N,M=list(map(int,input().split()))
#- 1要望 a→b,a→c分断要望に対して、b<cならa→bだけ考慮すればいい -#
#want = [float('inf')]*(N+1)
#for i in range(M):
#    a,b = map(int,input().split())
#    want[a] = min(want[a],b)
#
#want_list = []
#for idx,val in enumerate(want):
#    if val!=float('inf'):
#        want_list.append([idx,val])

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


#-取り除く橋要望をいもして最大の要望があつまっているところから順次取り除く-#
ex_bridge = []
while want_list:
    imo = [0]*(N+1)
    for wl in want_list:
        imo[wl[0]]+=1
        imo[wl[1]]-=1
    imo = list(itertools.accumulate(imo))
    tmp = imo.index(max(imo))
    ex_bridge.append(tmp)
    after_wl = []
    for a,b in want_list:
        if a<=tmp and b>tmp:
            continue
        else:
            after_wl.append([a,b])
    want_list = after_wl
print(len(ex_bridge))

Submission status: Wrong Answer

Solution code:
import sys,math,collections,itertools
input = sys.stdin.readline

N,M=list(map(int,input().split()))
#- 1要望 a→b,a→c分断要望に対して、b<cならa→bだけ考慮すればいい -#
want = [float('inf')]*(N+1)
for i in range(M):
    a,b = map(int,input().split())
    want[a] = min(want[a],b)

want_list = []
for idx,val in enumerate(want):
    if val!=float('inf'):
        want_list.append([idx,val])

#-取り除く橋要望をいもして最大の要望があつまっているところから順次取り除く-#
ex_bridge = []
while want_list:
    imo = [0]*(N+1)
    for wl in want_list:
        imo[wl[0]]+=1
        imo[wl[1]]-=1
    imo = list(itertools.accumulate(imo))
    tmp = imo.index(max(imo))
    ex_bridge.append(tmp)
    after_wl = []
    for a,b in want_list:
        if a<=tmp and b>tmp:
            continue
        else:
            after_wl.append([a,b])
    want_list = after_wl
print(len(ex_bridge))

Submission status: Wrong Answer

Solution code:
N, *A = map(int, open(0).read().split())
*A, = zip(*[iter(A)]*2)
A.sort()
cnt = 0
R = 0
for a, b in A:
    if R <= a:
        cnt += 1
        R = b
    elif b < R:
        R = b
print(cnt)

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappush

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *AB = map(int, read().split())

    Q = [0] * M
    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
        Q[i] = (a - 1, b - 2)

    Q.sort()

    hq = []
    ans = 0
    for x, y in Q:
        if not hq:
            heappush(hq, y)
        elif x < hq[0]:
            heappush(hq, y)
        elif x == hq[0]:
            ans += 1
            hq = []
        else:
            hq = [x]
            ans += 1

    if hq:
        ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from heapq import heappush

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, M, *AB = map(int, read().split())

    Q = [0] * M
    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
        Q[i] = (a - 1, b - 2)

    Q.sort()

    hq = []
    ans = 0
    for x, y in Q:
        if hq and x == hq[0]:
            ans += 1
            hq = []
        else:
            heappush(hq, y)

    if hq:
        ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

# for i in range():

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

# print(ab)
ans = 0
div = -1, -1
for i in range(len(ab)):
    a, b = ab[i]
    # print(a, b)

    if a == div[0]:
        continue
    elif a >= div[1]:
        div = a, b
        ans += 1
    else:
        div = a, min(b, div[1])
    # print(div, ans)

print(ans)

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
N, M = map(int, input().split(' '))

a_b_pairs = [list(map(int, input().split(' '))) for _ in range(M)]
a_b_pairs.sort(key=lambda x: x[1])
right = a_b_pairs[0][1]

ans = 1
for a, b in a_b_pairs[1:]:
    if a < right < b:
        pass
    else:
        right = b
        ans += 1


print(ans)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
L=list()
for i in range(M):
  a,b=map(int,input().split())
  A=list([b,a])
  L.append(A)
L=sorted(L)
R=[L[0][1]]
for j in range(M):
  if R[-1] not in range(L[j][1],L[j][0]):
    R.append(L[j][0]-1)
print(len(R))

Submission status: Wrong Answer

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

c = 1
s = 1
e = 10**9
for i in range(M):
    a = T[i][0]
    b = T[i][1]
    if a >= e and b > e:
        c += 1
        s = a
        e = b
    elif a > s and b < e:
        s = a
        e = b
    elif a > s:
        s = a
    elif b < e:
        e = b
    else:
        pass
print(c)

Submission status: Wrong Answer

Solution code:
from collections import*
n = len(s:=input())
print((n - k) // (2*k) * 2 + 1 if (k := sum(v%2 for v in Counter(s).values())) else n)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

class UnionFind():
    def __init__(self, n):
        self.parents = list(range(n))
        self.size = [1] * n

    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.size[x] < self.size[y]:
                x,y = y,x
            self.parents[y] = x
            self.size[x] += self.size[y]

def main():
    N, M = map(int, input().split())
    uf = UnionFind(N)
    for _ in range(M):
        a, b = map(lambda x: int(x)-1, input().split())
        uf.union(uf.find(a),uf.find(b))
    # print(max(Counter(uf.parents).values()) - 1)
    # print(uf.parents)
    ans = 0
    S = set()
    for u in uf.parents:
        if u in S:
            ans += 1
            S.clear()
            S.add(u)
        else:
            S.add(u)
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys
from collections import deque, Counter
from heapq import heappop, heappush
from bisect import bisect_right
from itertools import accumulate

sys.setrecursionlimit(10**6)
INF = 10**12
m = 10**9 + 7

class UnionFind():
    def __init__(self, n):
        self.parents = list(range(n))
        self.size = [1] * n

    def find(self, x):
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.size[x] < self.size[y]:
                x,y = y,x
            self.parents[y] = x
            self.size[x] += self.size[y]

def main():
    N, M = map(int, input().split())
    uf = UnionFind(N)
    for _ in range(M):
        a, b = map(lambda x: int(x)-1, input().split())
        uf.union(uf.find(a),uf.find(b))
    print(max(Counter(uf.parents).values()) - 1)

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n,m = map(int, raw_input().split())
s = [map(int, raw_input().split()) for _ in range(m)]
c = 0
s.sort()
cur = s[0]
for u,v in s[1:]:
	if cur == []:
		cur = [u,v]
	if cur[1] <= u-1:
		cur = [u,v]
		c += 1 
	else:
		cur[0] = max(u, cur[0])
	 	cur[1] = min(v, cur[1])
		if cur[1] - cur[0] <= 1: 
			c +=1
			cur = []
print c + (1 if cur else 0)

Submission status: Wrong Answer

Solution code:
n,m = map(int, raw_input().split())
s = [map(int, raw_input().split()) for _ in range(m)]


c = 0
s.sort()
cur = s[0]
for u,v in s[1:]:
	if cur == []:
		cur = [u,v]
	if cur[1] <= u:
		cur = [u,v]
		c += 1 
	else:
		cur[0] = max(u, cur[0])
	 	cur[1] = min(v, cur[1])
		if cur[1] - cur[0] <= 1: 
			c +=1
			cur = []
print c + (1 if cur else 0)

Submission status: Wrong Answer

Solution code:
n,m = map(int, raw_input().split())
s = [map(int, raw_input().split()) for _ in range(m)]

c = 0
s.sort()
cur = s[0]
for u,v in s[1:]:
	if cur == []:
		cur = [u,v]
	if cur[1] <= u:
		cur = [u,v]
		c += 1 
	else:
		cur[0] = max(u, cur[0])
	 	cur[1] = min(v, cur[1])
		if cur[1] - cur[0] == 0: c+=1
		cur = []
print c + (1 if cur else 0)

Submission status: Wrong Answer

Solution code:
n,m = map(int, raw_input().split())
s = [map(int, raw_input().split()) for _ in range(m)]

c = 0
s.sort()
cur = s[0]

#--->
# ->
for u,v in s[1:]:
	if cur == []:
		cur = [u,v]
	if cur[1] <= u:
		cur = [u,v]
		c += 1 
	else:
		cur[0] = max(u, cur[0])
	 	cur[1] = min(v, cur[1])
	if cur[1] - cur[0] <= 1:
		c+=1
		cur = []
print c + (1 if cur else 0)

Submission status: Wrong Answer

Solution code:
n,m = map(int, raw_input().split())
s = [map(int, raw_input().split()) for _ in range(m)]
cur = s[0]
c = 0
s.sort()


#--->
# ->
for u,v in s[1:]:
	if cur == []:
		cur = [u,v]
	if cur[1] <= u:
		cur = [u,v]
		c += 1 
	else:
		cur[0] = max(u, cur[0])
	 	cur[1] = min(v, cur[1])
	if cur[1] - cur[0] <= 1:
		c+=1
		cur = []
print c + (1 if cur else 0)

Submission status: Wrong Answer

Solution code:
n,m = map(int, raw_input().split())
s = [map(int, raw_input().split()) for _ in range(m)]
cur = s[0]
c = 0
s.sort()


#--->
# ->
for u,v in s[1:]:
	if cur == []:
		cur = [u,v]
	if cur[1] <= u:
		cur = [u,v]
		c += 1 
	else:
		cur[0] = max(u, cur[0])
	 	cur[1] = min(v, cur[1])
	if cur[1] - cur[0] <= 1:
		c+=1
		cur = []
print c + 1

Submission status: Wrong Answer

Solution code:
n,m = map(int, raw_input().split())
s = [map(int, raw_input().split()) for _ in range(m)]
cur = s[0]
c = 0
s.sort()
#--->
# ->
for u,v in s[1:]:
	if cur == []:
		cur = [u,v]
	if cur[1] <= u:
		cur = [u,v]
		c += 1 
	else:
		cur[0] = max(u, cur[0])
	 	cur[1] = min(v, cur[1])
	 	if cur[0] == cur[1]:
	 		c +=1
	 		break
print c+1

Submission status: Wrong Answer

Solution code:
n,m = map(int, raw_input().split())
s = [map(int, raw_input().split()) for _ in range(m)]
cur = s[0]
c = 0
s.sort()
#--->
# ->
for u,v in s[1:]:
	if cur == []:
		cur = [u,v]
	if cur[1] <= u:
		cur = [u,v]
		c += 1 
	elif cur[0] == u:
		pass
	else:
		cur[0] = max(u, cur[0])
	 	cur[1] = min(v, cur[1])
	 	if cur[0] == cur[1]:
	 		c +=1
	 		break
print c+1

Submission status: Wrong Answer

Solution code:
n,m = map(int, raw_input().split())
s = [map(int, raw_input().split()) for _ in range(m)]
cur = s[0]
c = 0
s.sort()

for u,v in s[1:]:
	if cur[1] <= u:
		cur = [u,v]
		c += 1 
	elif cur[0] == u:
		pass
	else:
		cur[0] = max(u, cur[0])
	 	cur[1] = min(v, cur[1])
print c+1

Submission status: Wrong Answer

Solution code:
(n,m),*ab = [list(map(int, s.split())) for s in open(0)]

ab = [(a-1,b-1) for a,b in ab]

aa = [0]*n
bb = [0]*n

for a,b in ab:
    aa[a] = 1
    bb[b] = 1

ended = False

ans = 1

for i,j in zip(aa,bb):
    if j:
        ended = True
    if i and ended:
        ans += 1
        ended = False

print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
g = [[n] for i in range(n)]
for i in range(m):
  a,b = map(int, input().split())
  g[a-1].append(b-1)
k = 0
ans=0
while k <=n-1:
  ans+=1
  e = n
  for i in g[k:]:
    e = min(e,min(i))
  if e == n-1 or e==n:
    break
  k = e
print(ans)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
g = [[n] for i in range(n)]
for i in range(m):
  n,m = map(int, input().split())
  g[n-1].append(m-1)
k = 0
ans=0
while k <=n-1:
  ans+=1
  e = n
  for i in g[k:]:
    e = min(e,min(i))
  if e == n:
    break
  k = e
print(ans)

Submission status: Wrong Answer

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

ab_lst = []

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


cut_distance = []

for a,b in ab_lst:
	have_add = True
	for cut in cut_distance:
		is_break = False
		if(a > cut[0] and a < cut[1]):
			cut[0] = a
			have_add = False
			is_break = True
		if(b < cut[1] and b > cut[0]):
			cut[1] = b
			have_add = False
			is_break = True
		if(is_break):
			break
	if(have_add):
		cut_distance.append([a,b])
	
print(len(cut_distance))

Submission status: Wrong Answer

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


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

#import numpy as np

def main():
	n,m=MI()
	li=[LI() for _ in range(m)]

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

	now=0
	ans=0

	for a,b in li:
		if now<=a:
			now=b
			ans+=1
	print(ans)

























if __name__ == "__main__":
	main()

Submission status: Wrong Answer

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

#S = [[0 for j in range(3)] for i in range(2)]　2行3列の場合
S = [[0 for j in range(2)] for i in range(M)]

for i in range(M):
    X,L=map(int,input().split())
    S[i][0]=X
    S[i][1]=L


T=sorted(S,key=lambda x:x[1])
#U=sorted(T,key=lambda x:x[1])



count=1
last=T[0][1]
print(T)
for i in range(1,M):
    if T[i][0]>=last:
        count+=1
        last=T[i][1]
print(count)

Submission status: Wrong Answer

Solution code:
import sys, re
from math import ceil, floor, sqrt, pi, factorial, gcd
from copy import deepcopy
from collections import Counter, deque
from heapq import heapify, heappop, heappush
from itertools import accumulate, product, combinations, combinations_with_replacement
from bisect import bisect, bisect_left
from functools import reduce
from decimal import Decimal, getcontext
# input = sys.stdin.readline 
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_list(N): return [s_list() for _ in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 6)
INF = float('inf')
MOD = 10 ** 9 + 7
num_list = []
str_list = []

def main():
    n, m = i_map()
    num_list = i_row_list(m)

    num_list = sorted(num_list, key=lambda x: x[0], reverse=True)
    num_list = sorted(num_list, key=lambda x: x[1], reverse=True)

    count = 0
    tmp = num_list[0][1]
    for num in num_list:
        if num[1] > tmp:
            continue
        tmp = num[0]
        count += 1

    print(count)
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def Main():
    n,m = IL()
    war = [list(IL()) for _ in range(m)]
    war.sort(key=lambda x: x[1])
    print(war)
    bridge = [1]*n
    for rep in war:
        left = rep[0]-1
        right = rep[1]-1
        if not 0 in bridge[left:right]:
            bridge[right-1] = 0
    print(bridge.count(0))
    return

if __name__=='__main__':
    Main()

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
itv=[]
for i in range(m):
  a,b=map(int,input().split())
  start=min(a,b)
  end=max(a,b)
  itv.append([end,start])
t,ans=0,0
itv=sorted(itv)
print(itv)
for e,s in itv:
  if t<=s:
    t=e
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
itv=[]
for i in range(m):
  a,b=map(int,input().split())
  start=min(a,b)
  end=max(a,b)
  itv.append([end,start])
t,ans=0,0
itv=sorted(itv)
for e,s in itv:
  if t<s:
    t=e
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
n,m=map(int,input().split())
itv=[]
for i in range(m):
  a,b=map(int,input().split())
  start=min(a,b)
  end=max(a,b)
  itv.append([end,start])
t,ans=0,0
for e,s in itv:
  if t<s:
    t=e
    ans+=1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from collections import defaultdict

    n, m = map(int, readline().split())
    cum = [0] * n

    war = defaultdict(list)

    for _ in range(m):
        a, b = map(int, readline().split())
        war[a].append(b)

    ans = 0
    cur = n + 1
    for i in range(1, n + 1):
        if cur == i:
            ans += 1
            cur = n + 1
        ng = war[i]
        if ng:
            cur = min(cur, ng[0])

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

ans = 0
ab.sort(reverse = True)
point = 0

for i in range(M):
  if ab[i][1] < point:
    pass
  else:
    point = ab[i][1]
    ans += 1

print(ans)

Submission status: Wrong Answer

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

ans = 1
ab.sort(reverse = True)
point = 0

for i in range(1,M):
  if ab[i][1] < point:
    pass
  else:
    point = ab[i][1]
    ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
N, M = map(int,input().split())
AB = []
for _ in range(M):
    t = tuple(map(int,input().split()))
    AB.append(t)
AB.sort()

left = 0
right = N
cnt = 0
for i,(a,b) in enumerate(AB):
    left = max(a,left)
    right = min(b,right)
    if left +1 >= right:
        cnt += 1
        right = N
    else:
        if i == M-1:
            cnt += 1
print(cnt)

Submission status: Wrong Answer

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

ans = 1
now = line[0][1]
for s, g in line[1:]:
    if s > now:
        ans += 1
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
ab = [0] * m
for i in range(m):
    aa, bb = map(int, input().split())
    ab[i] = (aa, bb)

ab.sort()
ans = 1
prev_left, border = ab[0][0], ab[0][1]
for i in range(1, m):
    if prev_left == ab[i][0]:
        border = min(border, ab[i][1])
    else:
        if border <= ab[i][0]:
            ans += 1
        prev_left = ab[i][0]
        border = ab[i][1]
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
info = [0] * m
for i in range(m):
    aa, bb = map(int, input().split())
    info[i] = (bb-aa, aa, bb)
info.sort()

ans = 1
border = info[0][2]
for i in range(1, m):
    l, r = info[i][1], info[i][2]
    if border <= l:
        ans += 1
        border = r
print(ans)

Submission status: Wrong Answer

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

query = []
bridge = [1 for _ in range(N-1)]

for _ in range(M):
    a, b = map(int, input().split())
    query.append((a-1, b-1))

#街が左にある方を優先
query = sorted(query, key=lambda x: x[1])
#喧嘩する街が近い方を優先
# query = sorted(query, key=lambda x: x[2])

ans = 0
left = 0
for i, j in query:
    if left < i:
        left = j-1
        ans += 1

# print(bridge)
print(ans)

Submission status: Wrong Answer

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

query = []
bridge = [1 for _ in range(N-1)]

for _ in range(M):
    a, b = map(int, input().split())
    query.append((a-1, b-1, b-a))

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

for i, j, _ in query:
    # print(i, j)
    # print(bridge[i:j])
    if sum(bridge[i:j]) == j-i:
        bridge[j-1] = 0
        # print("a", bridge[j-1])

# print(bridge)
print(N-1-sum(bridge))

Submission status: Wrong Answer

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

#入力
# s = input()
# n = int(input())
n,m = map(int, input().split())
# a = list(map(int,input().split()))
# a = [int(input()) for i in range()]

ab=[]
for i in range(m):
    a,b = map(int, input().split())
    ab.append((a,b))
ab = sorted(ab, key = lambda x: x[1])

     
def main():
    left = 0
    ans = 0
    for a,b in ab:
        print(a,b)
        if left < a:
            left = b-1
            ans +=1
    print(ans)


    
    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

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

# 区間の終端でソート
ab = sorted([list(map(int, input().split())) for i in range(m)], key=itemgetter(1))
# 前回除いた橋
print(ab)
removed = -1
ans = 0

for a, b in ab:
    # a が removed より大きい = まだ取り除いてない
    if a > removed:
        removed = b - 1
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
#tempt
n,m=map(int,input().split())
bri=[0 for i in range(n)]

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

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

print(max(bri))

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
AB = [lr() for _ in range(M)]
AB.sort(key=lambda x: [x[0], x[1]])
cur = 0
answer = 0
for a, b in AB:
    if a >= cur:
        answer += 1
        cur = b

print(answer)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys
from itertools import accumulate

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
limit = 2 * (N+1)
need = [0] * limit
for _ in range(M):
    a, b = lr()
    if b < a:
        a, b = b, a
    need[a*2+1] += 1
    need[b*2] += -1

need = list(accumulate(need))
answer = 0
inc = False
for i in range(limit-1):
    if need[i] < need[i+1] and not inc:
        answer += 1
        inc = True
    if need[i] > need[i+1]:
        inc = False

print(answer)

Submission status: Wrong Answer

Solution code:
n,m = (int(x) for x in input().split())

sec = []

for i in range(m):
    list = [int(i) for i in input().split()]
    list.reverse()
    sec.append(list)

sec.sort()
left = sec[0][0]
right = sec[0][1]
x = right - 1
ans = 0

for i in range(m):
    if sec[i][1]<x<sec[i][0]:
        continue
    else:
        x = sec[i][0]
        ans += 1

print(ans)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
L = list()
for i in range(m):
    x, y = map(int, input().split())
    if x > y:
        x, y = y, x
    L.append([x, y])
L = sorted(L, key=lambda x: x[1])
print(L)
A = L[0]
i = 1
for v in L:
    if v[0] >= A[1]:
        A = v
        i += 1
print(i)

Submission status: Wrong Answer

Solution code:
n, m = map(int, input().split())
L = list()
for i in range(m):
    x, y = map(int, input().split())
    if x > y:
        x, y = y, x
    L.append([x, y])
L = sorted(L, key=lambda x: x[1])
A = L[0]
i = 1
for v in L:
    if v[0] > A[1]:
        A = v
        i += 1
print(i)