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: Accepted

Solution code:
N, M = map( int, input().split())
Q = [[int(s) for s in input().split()] for _ in range(M)]
Q = sorted(Q)
ans = 1
stan = Q[0][1]
for i in range(M):
    if Q[i][0] < stan:
        stan = min(stan,Q[i][1])
    else:
        ans += 1
        if i == M-1:
            break
        else:
            stan = Q[i][1]
print(ans)

Submission status: Accepted

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

l = []

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

l.sort()

ans = 0
x = 0

for i in range(m):
    if l[i][1] >= x:
        ans += 1
        x = l[i][0]

print(ans)

Submission status: Accepted

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

ab.sort()
op_sum = 1
left = ab[0][0]
right = ab[0][1]

for a, b in ab:
    if right <= a:
        op_sum += 1
        left = a
        right = b
    else:
        left = a
        right = min(right, b)

print(op_sum)

Submission status: Accepted

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

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

AB.sort(key=lambda x: x[1])
num = 0
p = 0
for i in AB:
    if i[0] >= p:
        num += 1
        p = i[1]

print(num)

Submission status: Accepted

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

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: Accepted

Solution code:
N, M = map(int, input().split())
I = [N + 1 for i in range(N)]
for i in range(M):
  a, b = map(int, input().split())
  I[a - 1] = min(I[a - 1], b - 1)
cut = 0
for i in range(N - 1):
  if I[i] == i + 1:
    cut += 1
  else:
    I[i + 1] = min(I[i + 1], I[i])
print(cut)

Submission status: Accepted

Solution code:
def run(n, m, ab):
    ab = sorted(ab)
    cnt = 1
    b = ab[0][1]
    c = b
    for i in range(1, m):
        a = ab[i][0]
        b = ab[i][1]
        if a < c and c <= b:
            pass
        elif c <= a:
            cnt += 1
            c = b
        else:
            c = b
    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: Accepted

Solution code:
n, m = map(int, input().split())
a = []
for i in range(m):
    a.append(list(map(int, input().split())))
a.sort(key=lambda x: x[1])
t = 0
b = 1
for i in range(m):
    if a[i][0] >= b:
        t += 1
        b = a[i][1]
print(t)

Submission status: Accepted

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

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

ask2 = ask[np.argsort(ask[:,1])]
delete = np.array([ask2[0,1]-1])
for a in ask2[1:]:
    if a[0] <= delete[-1]:
        pass
    else:
        delete = np.append(delete, a[1]-1)
print(len(delete))

Submission status: Accepted

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

Submission status: Accepted

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

sys.setrecursionlimit(10000)


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


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


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


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


def read_str():
    return input()


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


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


def mt(f):
    import time

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

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

    return wrap


@mt
def slv(N, M, AB):
    AB.sort(key=lambda x: x[1])
    ans = 0
    p = -1
    for a, b in AB:
        if a <= p:
            continue
        p = b - 1
        ans += 1
    return ans


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

index = 0
ans = 0
for tmp in a:
	if tmp[0] <= index:
		continue
	else:
		ans += 1
		index = tmp[1] - 1

print(ans)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    n, m = map(int, input().split())
    ab = []
    for i in range(m):
        ab_i = tuple(map(int, input().split()))
        ab.append(ab_i)

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

    ans = 0
    left = 0
    for i in range(m):
        if left <= ab[i][0]:
            left = ab[i][1]
            ans += 1

    print(ans)

Submission status: Accepted

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

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

demand = sorted(demand, key=lambda x: x[1])
count = 0
bridge = None

for d in demand:
    if bridge == None or bridge < d[0]:
        bridge = d[1] - 1
        count += 1

print(count)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ab = [tuple(map(int,input().split())) for _ in range(m)]
ab.sort(key=lambda x:x[1])
last=-1
cnt=0
for i in range(len(ab)):
    if(ab[i][0]<=last):pass
    else:
        last=ab[i][1]-1
        cnt+=1
print(cnt)

Submission status: Accepted

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])
x = sorted(x, key=lambda x:x[1])
no = 0
ans = 0
for i in range(M):
  a = x[i]
  if (a[0] <= no and a[1] >= no):
    pass
  else:
    no = a[1] -1
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter
N, M = map(int, input().split())
ab = []
for i in range(M):
    ab.append([int(xi) for xi in input().split()])
ab = sorted(ab, key=itemgetter(0, 1))
x, y = ab[0]
count = 1
for ai, bi in ab[1:]:
    if bi < x or y <= ai:
        count += 1
        x, y = ai, bi
    else:
        x = max(x, ai)
        y = min(y, bi)
print(count)

Submission status: Accepted

Solution code:
from sys import stdin
from fractions import gcd

N,M=[int(i) for i in input().split()]
datas = []
for i in range(M):
    x,y=[int(i) for i in input().split()]
    datas.append([y,x])
datas.sort()
count = 0
start = 0
for data in datas:
    if data[1] < start : continue
    end = data[0]
    start = end 
    count +=1        
        
print(count)

Submission status: Accepted

Solution code:
from operator import itemgetter

n, m = [int(i) for i in input().split()]
A, B = zip(*[[int(i) for i in input().split()] for j in range(m)])

A, B = zip(*sorted(zip(A, B), key=itemgetter(1, 0)))

last = -1
ans = 0

for a, b in zip(A, B):
    if last <= a:
        ans += 1
        last = b

print(ans)

Submission status: Accepted

Solution code:
# your code goes here
import numpy as np
buf = input().split()
n = int(buf[0])
m = int(buf[1])

l = np.zeros((m, 2))
for i in range(m):
	buf = input().split()
	for j in range(2):
		l[i][j] = int(buf[j])
l = l[l[:,1].argsort(), :]
#print(l)
sum = 0
c1 = 0
c2 = 0
for i in range(m):
	b1 = l[i][0]
	b2 = l[i][1]
	if(b1 >= c2):
		sum += 1
		c1 = b1
		c2 = b2
	elif(b2 < c2):
		c2 = b2
	#print(c1, c2, sum)
print(sum)

Submission status: Accepted

Solution code:
import sys
n, m = map(int, sys.stdin.readline().split())
req = [ list(sorted(map(int, sys.stdin.readline().split())))
        for _ in range(m) ]
req.sort(reverse=True)
lastcut = None
c = 0
for a, b in req:
    if lastcut is None or a > lastcut or lastcut >= b:
        lastcut = a
        c += 1
print(c)

Submission status: Accepted

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

p = demands[0][0]
ans = 1

for i in range(1, m):
    if p <= demands[i][1]:
        ans += 1
        p = demands[i][0]


print(ans)

Submission status: Accepted

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

ans = 0
max_ = 0
for ele in ab:
  if ele[0]>=max_:
    max_ = ele[1]
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m=[int(i) for i in input().split()]
count=m
a=[]

for i in range(m):
  a.append([int(j) for j in input().split()])
 
a.sort(key=lambda x:x[1])

k=0
for i in range(1,m):
    if a[k][1] > a[i][0]:
      count -= 1
    else:
      k = i

print(count)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
store = []
for _ in range(m):
    a, b = map(int, input().split())
    store.append([a, b])
store.sort(key = lambda x:x[0])
count = 0
ans = 0
while count < m:
    index = 1
    t = store[0][1]
    while index < len(store) and store[index][0] < t:
        t = min(t, store[index][1])
        index += 1
    count += index
    store = store[index:]
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
def main():
    in1 = input().split(" ")
    n, m = [int(c) for c in in1]

    arr = []
    for i in range(m):
        _in = input().split(" ")
        a, b = [int(c) for c in _in]
        arr.append((a, b))

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

    n = 1

    mi, ma = sorted_arr[0]
    mi, ma = (mi, ma) if mi < ma else (ma, mi)
    for a, b in sorted_arr[1:]:
        a, b = (a, b) if a < b else (b, a)
        if ma <= a:
            n += 1
            mi, ma = a, b
        if mi < a:
            mi = a
        if ma > b:
            ma = b
    print(n)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

right = -1
count = 0

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

print(count)

Submission status: Accepted

Solution code:
import bisect

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

p = 1

if m != 1:
    

    for i in range(1,m):
        a = ab[i][0]-1
        b = ab[i][1]-1
        if a != l[len(l)-2]:
            if a < l[len(l)-1]:
                l[len(l)-2] = a
                if b < l[len(l)-1]:
                    l[len(l)-1] = b
            else:
                l.append(a)
                l.append(b)
                p += 1
print(p)

Submission status: Accepted

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

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

abM.sort()

tmp_e = abM[0][1]
cnt = 1

for i in range(1,M):
    if tmp_e > abM[i][0]:
        tmp_e = min(abM[i][1], tmp_e)
    else:
        cnt += 1
        tmp_e = abM[i][1]
print(cnt)

Submission status: Accepted

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: Accepted

Solution code:
from operator import itemgetter

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

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



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

print(ans)

Submission status: Accepted

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

s = [n for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    if s[a - 1] > b - 1:
        s[a - 1] = b - 1

result = 0
i = 0
while i < n - 1:
    hoge = min(s[i:])
    if hoge == n:
        break
    i = hoge
    result += 1

print(result)

Submission status: Accepted

Solution code:

import sys
from collections import deque
import copy

from math import *

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline


def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] =  [int(input_raw[0]), int(input_raw[1])]
    sep= []
    for i in range(M):
        input_raw = read_func().strip().split()
        [a, b] =  [int(input_raw[0]), int(input_raw[1])]
        sep.append((a, b))

    sep.sort()

    count = 1
    is_search = False
    i = 0
    while i < M:
        if is_search == False:
            ai = sep[i][0]
            bi = sep[i][1]
            is_search = True
            i += 1
        else:
            aj = sep[i][0]
            bj = sep[i][1]
            if ((ai <= aj and aj < bi)) == False :
                count += 1
                is_search = False
            else:
                ai = max(ai, aj)
                bi = min(bi, bj)
                i += 1

    print count



if __name__ == '__main__':
    main()

Submission status: Accepted

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

bridge=[None]*M

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


bridge.sort()

brilist=[0]*(10**5)
brilist[bridge[0][0]]=bridge[0][1]
#print(brilist[:15])
for i in range(1,M):
    if bridge[i][0]==bridge[i-1][0]:
        brilist[bridge[i][0]]=min(bridge[i][1],brilist[bridge[i][0]])

    elif bridge[i][0]<brilist[bridge[i-1][0]]:

        brilist[bridge[i][0]]=min(bridge[i][1],brilist[bridge[i-1][0]])
        brilist[bridge[i-1][0]]=0
        

    else:

        brilist[bridge[i][0]]=bridge[i][1]

    #print(brilist[:15])


ANS=0
for i in range(10**5):
    if brilist[i]!=0:
        ANS+=1

print(ANS)
#print(brilist[:15])

Submission status: Accepted

Solution code:
from operator import itemgetter
N, M = map(int, raw_input().split())
a = []
b = []
for i in range(M):
	_a, _b = map(int, raw_input().split())
	a.append(_a)
	b.append(_b)

c = zip(a, b)
c.sort(key=itemgetter(0))
a, b = zip(*c)

c = 0
min_b = 0
for i in range(M):
	min_b = min(min_b, b[i])
	if a[i] < min_b:
		continue
	else:
		c += 1
		min_b = b[i]
print(c)

Submission status: Accepted

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

ans = 0
m = -1
for l, r in lrs:
    if r < m:
        m = r
    if l >= m:
        ans += 1
        m = r

print(ans)

Submission status: Accepted

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

ab = [[0 for i in range(2)] for j in range(M)]

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


ab2 = sorted(ab, key=lambda x:(x[0], x[1]), reverse=False)
# print(ab2)

count = 0

def func(ablist):
    mi = 0
    ma = float('inf')
    for i in range(len(ablist)):
        mi = max(mi, ablist[i][0])
        ma = min(ma, ablist[i][1] - 1)
#        print(mi, ma)
        if mi > ma:
            return func(ablist[i:]) + 1
    return 1

print(func(ab2))

Submission status: Accepted

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

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

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

Submission status: Accepted

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

R.sort()

inf = float('inf')
Ra = [inf for a in range(N + 1)]
for a, b in R:
    Ra[a] = min(Ra[a], b)
R = [(a, Ra[a]) for a in range(1, N+1) if Ra[a] != inf]

R.sort(key=lambda r: r[1])

bridge = [True] * (N)

last = None
for a, b in R:
    if last == None or last < a:
        bridge[b-1] = False
        last = b-1
print(sum(1 for b in bridge if not b))

Submission status: Accepted

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

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

abM.sort(key = lambda x: (x[0], x[1]))

tmp_e = abM[0][1]
cnt = 1

for i in range(1,M):
    if tmp_e > abM[i][0]:
        tmp_e = min(abM[i][1], tmp_e)
    else:
        cnt += 1
        tmp_e = abM[i][1]
print(cnt)

Submission status: Accepted

Solution code:
import bisect
N,M = map(int,input().split())
l = [0]*M
for i in range(M):
     l[i] = list(map(int,input().split()))
l.sort()
a = [0]*M
b = [0]*M
for i in range(M):
    a[i] = l[i][0]
    b[i] = -l[i][1]
ans = 0
while len(a)>0:
    min = -max(b)
    i = bisect.bisect(a,min-1)
    a = a[i:]
    b = b[i:]
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
from operator import itemgetter


def main():
    n, m = map(int, input().split())
    li = []
    for i in range(m):
        a, b = map(int,input().split())
        li.append([a,b])
    li = sorted(li,reverse = True)
    count = 1
    mark = 0
    i = 0
    j = 0
    while m > 1:
        check = li[j][0]
        i = i + 1
        if check < li[i][1]:
            m = m - 1
        else:
            count = count + 1
            m = m - 1
            j = i
    print (count)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,M=map( int, raw_input().split() ) 
A= [ map( int, raw_input().split() )  for i in range(M) ]

A.sort(key=lambda x:(x[0],-x[1]))

ans=0
for i  in range(M):
	x=A[i][0]
	y=A[i][1]
	if i==0:
		l=x
		r=y
		ans+=1
	else:
		if l<=x and x<r:
			#print "x,y,l,r::", x,y,l,r
			l=max(l,x)
			r=min(r,y)
		else:
			ans+=1
			l=x
			r=y
print ans

Submission status: Accepted

Solution code:
def spaceinput():
    return list(map(int,input().split(" ")))


N,M=spaceinput()

sima=[]
for i in range(M):
    sima.append(spaceinput())


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

#print(sima)

blr=[0,0]

count=0
for i in range(M):
    if sima[i][0]>=blr[1]:
        count+=1
        blr=sima[i][:]
    elif blr[1]>=sima[i][1]:
        blr[0]=sima[i][0]
        blr[1]=sima[i][1]

    else:
        blr[0]=sima[i][0]


print(count)

Submission status: Accepted

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

E.sort()
l, r = 0, float('inf')
ans = 0
for a, b in E:
    if b <= l or a >= r:
        ans += 1
        l, r = a, b
    else:
        l = max(a, l)
        r = min(b, r)

print(ans + 1)

Submission status: Accepted

Solution code:
# coding=utf-8

if __name__ == '__main__':
    N, M = map(int, input().split())
    cut_list = []
    demand_list = [list(map(int, input().split())) for i in range(M)]
    demand_list.sort()

    # demand_list2 = [demand_list[0]]
    previous_demand = demand_list[0]
    demand_list = demand_list[1:]
    counter = 1

    if M == 1:
        print(counter)
    else:
        for demand in demand_list:
            if previous_demand[0] == demand[0]:
                pass
            elif previous_demand[1] <= demand[0]:
                previous_demand = demand
                counter += 1
            else:
                previous_demand = [demand[0], min(previous_demand[1], demand[1])]

        print(counter)

Submission status: Accepted

Solution code:
# your code goes here
N,M = map(int,input().split())
query = [list(map(int,input().split())) for i in range(M)]

query.sort()

left = 0
right = N+1
ans = 1
for q in query:
	if (left <= q[0] and q[0] < right) or (left < q[1] and right >= q[1]):
		left = max(left,q[0])
		right = min(right,q[1])
	else:
		ans += 1
		left = q[0]
		right = q[1]
print(ans)

Submission status: Accepted

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

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

count = 1
start = com[0][0]
end = com[0][1]

for i in range(m):
    if com[i][0]>= end:
        end = com[i][1]
        count += 1

print(count)

Submission status: Accepted

Solution code:
n,m=[int(i) for i in input().split()]
x=[10**5+1 for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  x[a-1]=min([x[a-1],b-1])


y=0
t=10**5+1
r=0
for i,j in enumerate(x):
  if j !=10**5+1:
    if i >= t or r==0:
      y+=1
      r=1
      t=j
    elif t>j:
      t=j

print(y)

Submission status: Accepted

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

MinBar = 1
abar = AB[0][0]
bbar = AB[0][1]
for i in range(1, M):
    if AB[i][0] < bbar:
        bbar = min(bbar, AB[i][1])
    else:
        MinBar += 1
        abar = AB[i][0]
        bbar = AB[i][1]
print(MinBar)

Submission status: Accepted

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

reqs.sort(key=lambda x:(x[0],x[1]))
query = []
tmp = 0
for req in reqs:
  if tmp == req[0]:
    continue
  else:
    query.append(req)
    tmp = req[0]
    
left = 0
right = n
count = 1
for q in query:
  if left <= q[0] and q[1]-1 <= right:
    left = q[0]
    right = q[1]-1
  elif left <= q[0] <= right:
    left = q[0]
  else:
    count += 1
    left = q[0]
    right = q[1]-1
print(count)

Submission status: Accepted

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
[n,m]=i2()
c=[[] for i in range(n)]
for i in range(m):
 [a,b]=i2()
 c[a-1].append(b-1)
d=[]
e=0
for i in range(n):
 if i in d:
   e+=1
   d=[]
 if len(c[i]):
  d.append(min(c[i]))
print(e)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ab = []
for i in range(m):
    a,b = map(int,input().split())
    ab.append((a,b))
ab = sorted(ab,key=lambda x:x[1])
count = 0
while len(ab) != 0:
    x = ab.pop(0)
    cut = x[1]-1
    count += 1
    while len(ab) != 0:
        if ab[0][0] <= cut <= ab[0][1]:
            ab.pop(0)
        else:
            break
print(count)

Submission status: Accepted

Solution code:
from operator import itemgetter
n,m = map(int,input().split())
ab = []
for i in range(0,m):
    aa,bb = map(int,input().split())
    ab.append((aa,bb))
ab.sort(key=itemgetter(1))
ans = 0
last = 0
for i in range(0,m):
    s,t = ab[i]
    if last <= s:
        ans += 1
        last = t
print(ans)

Submission status: Accepted

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

ABs.sort()

ans = 0
minB = N+1
for A, B in ABs + [(N+1, N+1)]:
    if minB <= A:
        ans += 1
        minB = B
    minB = min(minB, B)

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
ab=[list(map(int, input().split())) for _ in range(m)]
ab.sort()
xy=[[ab[0][0], ab[0][1]]]
for i in range(1,m):
    if ab[i][0]<xy[-1][1]:
        xy[-1][0],xy[-1][1]=ab[i][0],min(xy[-1][1],ab[i][1])
    else:
        xy.append([ab[i][0], ab[i][1]])
print(len(xy))

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
m_list = []
for i in range(m):
    m_list.append(list(map(int, input().split())))
m_list = sorted(m_list)
b_s = 0
b_e = n
cnt = 1
for i in range(m):
    a, b = m_list[i][0], m_list[i][1]
    if b_s <= a < b_e:
        if b_s < a:
            b_s = a
        if b < b_e:
            b_e = b
    else:
        cnt += 1
        b_s = a
        b_e = b
print(cnt)

Submission status: Accepted

Solution code:
from operator import itemgetter

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

ab = sorted(ab, key=itemgetter(0, 1))
ans = 1
x, y = ab[0]
for i in range(1, M):
    a, b = ab[i]
    if b <= x or y <= a:
        ans += 1
        x, y = a, b
    else:
        x = max(x, a)
        y = min(y, b)
print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

cut_set = set()

for t in ab:
    todo = 1
    for s in cut_set:
        if t[0] <= s <= t[1]:
            todo = 0
            break
    if todo:
        cut_set.add(t[1] - 1)
print(len(cut_set))

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

N, M  = getNM()
req = [N for i in range(N)]
for i in range(M):
    l,r = getNM()
    if req[l] > r-1:
        req[l] = r-1
ans = 0
tar = 0
#print(req) #[9, 7, 6, 4, 5, 9, 9, 8, 9] :9 is ignored
req2 = []
cut = N
for i in range(N):
    if (req[N-i-1]) < cut:
        cut = N-i-1
        ans += 1
    else:
        pass


print(ans)

Submission status: Accepted

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

l, r = a[0][0], a[0][1]

for i in range(len(a)):
    if a[i][0] < r:
        if a[i][1] < r:
            l, r = a[i][0], a[i][1]
        else:
            l = a[i][0]
    else:
        ans += 1
        l, r = a[i][0], a[i][1]

ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m=map(int, input().split())
ab=[list(map(int, input().split())) for _ in range(m)]
ab.sort()
a=[ab[i][0] for i in range(m)]
b=[ab[i][1] for i in range(m)]
xy=[[a[0], b[0]]]
for i in range(1,m):
    if a[i]<xy[-1][1]:
        xy[-1][0],xy[-1][1]=a[i],min(xy[-1][1],b[i])
    else:
        xy.append([a[i], b[i]])
print(len(xy))

Submission status: Accepted

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

count = 1
ab = []

for i in range(M):
    ab.append(list(map(int, input().split())))
ab.sort()

a, b = ab[0]

for i in range(1, M):
    a_new, b_new = ab[i]

    if b <= a_new:
        a, b = a_new, b_new
        count += 1

    elif  b_new <= b:
        a, b = a_new, b_new

    else:
        a = a_new

print(count)

Submission status: Accepted

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

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

    pairs.sort(key=lambda tup: tup[0])

    cnt = 1
    left, right = -1, 100001
    for i in range(m):
        if right <= pairs[i][0]:
            cnt += 1
            left, right = pairs[i][0], pairs[i][1]
        else:
            if left < pairs[i][0]:
                left = pairs[i][0]
            if pairs[i][1] < right:
                right = pairs[i][1]

    print(cnt)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

arr.sort()

prev = 0
ans = 0
for b, a in arr:
  if prev <= a:
    ans += 1
    prev = b

print(ans)

Submission status: Accepted

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

s = [[0, 0] for i in range(m)]
for i in range(m):
    a[i], b[i] = [int(i) for i in input().split()]
    s[i] = [b[i], a[i]]
count = 0
s = sorted(s)
#print(s)
i = 0
pivot = -1

for i in range(m):
    if s[i][1] >= pivot:
        count += 1
        pivot = s[i][0]
        #print("i :{} piv:{}".format(i, pivot))

"""
    count += 1
    pivot = s[i][0]
    print("i :{} piv:{}".format(i, pivot))
    i += 1
    if i < m:
        while s[i][1] < pivot:
            i += 1
            print("i2:{} piv:{}".format(i, pivot))
"""
print(count)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(m)]
lst.sort()
lst = [[lst[i][0] - 1, lst[i][1] - 1, i] for i in range(m)]
dic = {}
for a, b, i in lst:
  if b in dic:
    dic[b].append(i)
  else:
    dic[b] = [i]

used = [False] * m
ans = 0
right = -1
for i in range(m):
  a, b, _ = lst[i]
  if used[i]:
    continue
  if right >= a:
    used[i] = True
    continue
  used[i] = True
  ans += 1
  for p in range(a, b):
    flag = False
    if p in dic:
      for j in dic[p]:
        if not used[j]:
          used[j] = True
          right = p - 1
          flag = True
    if flag:
      break
  else:
    right = p
print(ans)