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

Solution (Python):
import sys

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(N, M, inputs):
    requests = list(map(lambda x: string_to_int(x), inputs))
    requests = sorted(requests, key=lambda x: x[1])

    deleted = []
    last = 0

    for request in requests:
        if request[0] > last:
            deleted.append(request[1] - 1)
            last = deleted[-1]

    return len(deleted)


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    [N, M] = string_to_int(input())
    ret = solve(N, M, inputs(M))
    print(ret)

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

for i in ab:
    if i[0] < last:
        continue
    else:
        last = i[1]
        ans += 1

print(ans)

Solution (Python):
N, M = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(M)]
ab.sort()
result = 0
min_b = N + 1
p = 0
for i in range(1, N + 1):
    if i == min_b:
        result += 1
        min_b = N + 1
    while p < M and i == ab[p][0]:
        min_b = min(min_b, ab[p][1])
        p += 1
print(result)

Solution (Python):

"""
Created on Sun May 19 20:12:17 2019

@author: Owner
"""

from operator import itemgetter
import bisect

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


ab = [(0, 0)]*M
for m in range(M):
    ab[m] = tuple(map(int, input().split()))

ab = tuple(sorted(ab, key = itemgetter(1)))


x_rm = -1
res = 0
for m in range(M):
    if ab[m][0] < x_rm:
        continue
    else:
        x_rm = ab[m][1]
        res += 1
    
    
        

print(res)

Solution (Python):
N, M = map(int, input().split())
claim = []
for i in range(M):
	claim.append(list(map(int, input().split())))
claim.sort(key=lambda a:a[1])

ans = 0
inter = [-1,-1]
for land in claim:
    if inter[1] <= land[0]:
        inter = land
        ans += 1
print(ans)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M = MAP()
ab = [LIST() for _ in range(M)]

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


tmp = ab[0][1]
count = 1
for i in range(M):
	a, b = ab.pop(0)
	
	if a < tmp:
		continue
	else:
		tmp = b
		count += 1
print(count)

Solution (Python):
n,m=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(m)]
arr=sorted(arr,key=lambda x:x[0])
arr=sorted(arr,key=lambda x:x[1])
cnt=0
pos=0
for i in range(m):
  if arr[i][0]<pos:
    continue
  else:
    cnt+=1
    pos=arr[i][1]
print(cnt)

Solution (Python):
N,M=map(int,input().split())
ab=[list(map(lambda x:int(x)-1,input().split())) for i in range(M)]
x=[0]*(N-1)
for i in range(M):
    if x[ab[i][0]]>ab[i][1] or x[ab[i][0]]==0:
        x[ab[i][0]]=ab[i][1]
flag=0
a=N
cnt=0

for i in range(N-1):
    if flag==0 and x[i]==0:
        continue
    elif flag==0 and x[i]>0:
        flag=1
        a=x[i]
        cnt+=1
    elif i<a:
        if x[i]<a and x[i]!=0:
            a=x[i]
    else:
        if x[i]>0:
            a=x[i]
            cnt+=1
        else:
            flag=0
            a=N
print(cnt)

Solution (Python):
from operator import itemgetter
N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
ab.sort(key=itemgetter(1))
b_min = ab[0][1]
cut = 1
for abi in ab:
    if abi[0] >= b_min:
        cut += 1
        b_min = abi[1]
    b_min = min(b_min ,abi[1])
print(cut)

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

ans = 0
t = 0
for a, b in ab:
    if t <= a:
        ans += 1
        t = b

print(ans)

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

ab.sort(key = lambda x:x[1])
ans = 0
last = -1
for a,b in ab:
    if last <= a:
        ans += 1
        last = b
print(ans)

Solution (Python):
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 x: x[1], reverse=True)

res = 1

mina = pairs[0][0]
for i in range(m):
    a, b = pairs[i]
    if b <= mina:
        res += 1
        mina = a
    mina = max(mina, a)

print(res)

Solution (Python):
N, M = map(int, input().split())
e = [[] for _ in range(N + 1)]
for _ in range(M):
    a, b = map(int, input().split())
    e[a].append(b)
ans = 0
minb = float("inf")
for i in range(1, N + 1):
    if i == minb:
        ans += 1
        minb = float("inf")
    if len(e[i]):
        minb = min(minb, min(e[i]))
print(ans)

Solution (Python):

N,M=map(int,input().split())
ans=0
ba = [[0 for _ in range(2)] for _ in range(M)]

for i in range(M):
  a,b = map(int, input().split())
  ba[i][0]=b
  ba[i][1]=a
  
ba.sort()

br=0
for b,a in ba:
  if not(a<br<b):
    br=b-0.5
    ans +=1
  
print(ans)

Solution (Python):
N,M=map(int,input().split())
need=[tuple(map(int,input().split())) for i in range(M)]
ans=0
need.sort(key=lambda x:x[1])
bef=1
for a,b in need:
    if a<bef:
        continue
    else:
        ans+=1
        bef=b
print(ans)

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

ab = sorted(AB, key=lambda x:x[1])



count, last = 0, None
for a, b in ab:
	if not last:
		last = b
		count += 1
	if last <= a:
		last = b
		count += 1
print(count)

Solution (Python):
n, m = [int(i) for i in input().split()]
a=[]
b=[]
for i in range(m):
    x1, y1 = [int(i) for i in input().split()]
    a.append(x1)
    b.append(y1)

c = zip(b,a)
c = sorted(c)
b,a = zip(*c)


ans = 0
point=0

for i in range(m):
    if a[i]<point<b[i]:
        continue
    else:
        ans += 1
        point=b[i]-0.5

print(ans)

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

cutleftfrom = 0
cnt = 0
for a, b in sorted([list(map(int, input().split())) for _ in range(M)], key=lambda x:x[1]):
    if a < cutleftfrom:
        continue
    cutleftfrom = b
    cnt += 1

print(cnt)

Solution (Python):
"""
- N個の島とN-1個の橋
- i番目の橋は島iと島i+1を接続する
- ai番目とbi番目の島の間での諍いを止めたい
    - aiとbi番目の島を隔離する
- こんな要望がM個

始点と終点が必要そうだから、2次元に値を保存してみる⇨遅い。ダメ
"""
import heapq
N,M = map(int, input().split())




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




cnt = 0
pos = 1000000000000
for j in sorted(dic.keys(),reverse=True): 
    if dic[j] <= pos:
        cnt += 1
        pos = j
print(cnt)

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

conf.sort()
divp.append(conf[0][0]-1)
for i in range(1, M):
  if divp[-1] < conf[i][1]:
    divp.append(conf[i][0]-1)
print(len(divp))

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, M = LI()
    bars = []
    for _ in range(M):
        a, b = LI_()
        bars.append((a,b))
    bars = sorted(bars, key=lambda x: x[0])
    l_max = bars[0][0]
    r_min = bars[0][1]

    count = 1 
    for bar in bars[1:]:
        l, r = bar
        if r_min <= l:
            count += 1
            r_min = r
        else:
            r_min = min(r, r_min)
        l_max = l

    print(count)
main()

Solution (Python):
N,M=map(int,input().split())
hope=[tuple([int(i) for i in input().split()]) for j in range(M)]
hope.sort(key=lambda x:x[1])
ans=0
prebroke=0
for s,g in hope:
    if s<=prebroke:
        continue
    else:
        ans+=1
        prebroke=g-1
print(ans)

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

for a, b in ab:
    
    if a > removed:
        removed = b - 1
        ans += 1

print(ans)

Solution (Python):
N, M = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]
X.sort(key=lambda x: x[1])

bdg = -1
cnt = 0
for a, b in X:
    if a > bdg:
        bdg = b - 1
        cnt += 1
        
print(cnt)

Solution (Python):
"""
区間スケジューリング
終端で降順にソートすれば良い
最適解は，貪欲法で，1つ次の区間を通るように串刺すこと
終端で降順にソートしているので，1本で区間を刺せる条件はi<jのとき，a[i]<b[j]
さらにその後，刺せる範囲が狭まる場合(a[i]>b[i])は，狭めて次の区間に行く
"""
n, m=map(int, input().split())
hope=[]
for i in range(m):
    a, b=map(int, input().split())
    hope.append((a, b))
hope.sort(reverse=True, key=lambda x: x[1])
ans=0
for i in range(m-1):
    if i==0:
        target=hope[i][0]
    if target<hope[i+1][1]:
        if target<hope[i+1][0]:
            target=hope[i+1][0]
    else:
        ans=ans+1
        target=hope[i+1][0]
print(ans+1)

Solution (Python):
"""
区間スケジューリング
終端で降順にソートすれば良い
"""
n, m=map(int, input().split())
hope=[]
for i in range(m):
    a, b=map(int, input().split())
    hope.append((a, b))
hope.sort(reverse=True, key=lambda x: x[0])
hope.sort(reverse=True, key=lambda x: x[1])
ans=0
for i in range(m-1):
    if i==0:
        target=hope[i][0]
    if target<hope[i+1][1]:
        if target<hope[i+1][0]:
            target=hope[i+1][0]
    else:
        ans=ans+1
        target=hope[i+1][0]
print(ans+1)

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

ans = 0
ba = [[0 for _ in range(2)] for _ in range(m)]

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

ba.sort()

br = 0
for b,a in ba:
    
    if not (a < br < b):
        
        br = b - 0.5
        ans += 1

print(ans)

Solution (Python):
*D, = open(0)
n, m = map(int, D[0].split())
edges = [list(map(int, it.split())) for it in D[1:]]
edges = sorted(edges, key=lambda x:x[1])

bridge = edges[0][1]
cnt = 1
for a, b in edges[1:]:
    if bridge <= a:
        bridge = b
        cnt += 1
print(cnt)

Solution (Python):
*D, = open(0)
n, m = map(int, D[0].split())
edges = [list(map(int, it.split())) for it in D[1:]]
edges = sorted(edges, key=lambda x:x[1])

cnt = 0
while len(edges)>0:
    cnt += 1
    new_edges = []
    bridge = edges[0][1]
    for it in edges:
        if it[0]>=bridge:
            new_edges.append(it)
            
    edges = new_edges
print(cnt)

Solution (Python):

import sys


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    ll = [[a[i],b[i]] for i in range(M)]

    ll = sorted(ll, key=lambda x:x[1])

    endtime = 0
    ans = 0
    for i in range(M):
        if(endtime <= ll[i][0]):
            endtime = ll[i][1]
            ans += 1
        
    print(ans)
    return



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

if __name__ == '__main__':
    main()

Solution (Python):




from operator import itemgetter
from collections import deque


def find_ans(queue):
    cnt = 0
    while len(queue):
        head = queue.popleft()
        i = 0
        while i < len(queue):
            if head[1] <= queue[i][0]:
                break
            queue.popleft()
        cnt += 1

    return cnt


if __name__ == '__main__':
    N, M = map(int, input().split())
    islands = []
    queue = deque()
    for i in range(M):
        island = list(map(int, input().split()))
        islands.append(island)
    
    islands.sort(key=itemgetter(1))
    for i in range(M):
        queue.append(islands[i])
    print(find_ans(queue))

Solution (Python):
n, m = map(int, input().split())
pair = []
ans = 0
x = 0

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

pair = sorted(pair, key = lambda x: x[1])


for (i,j) in pair:
    if i > x:
        x = j - 1
        ans += 1

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
L = [[int(v) - 1 for v in input().split()] for _ in range(M)]
L.sort(key = lambda x:(-x[1], -x[0]))

ans = 1
sx, sy = L[0]
for i in range(1, M):
    x, y = L[i]
    
    if sx >= y:
        ans += 1
        sx = x
    elif sx <= x:
        sx = x
    
print(ans)

Solution (Python):
n,m=map(int,input().split())
l=[list(map(int,input().split())) for i in range(m)]
l.sort(key=lambda x:x[1])
c=[l[0][1]]
for i,j in l[1:]:
    if i<c[-1]<=j:pass
    else:c.append(j)
print(len(c))

Solution (Python):

import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np

def main():
	N, M = map(int, input().split(" "))
	ab = []
	
	for _ in range(M):
		a, b = map(int, input().split(" "))
		ab.append((a, b))
		
	ab = sorted(ab, key=lambda x:(x[1]))
	ans = 0
	otosu = -1
	for i, val in enumerate(ab):
		a, b = val
		if i == 0:
			ans += 1
			otosu = b
			continue
		if otosu <= a:
			ans += 1
			otosu = b
			continue
	
	print(ans)
	
if __name__ == "__main__":
	main()

Solution (Python):
from collections import Counter
from collections import deque
from functools import reduce
from pprint import pprint
import bisect
import copy
import fractions
import itertools
import math
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
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 LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers): return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers): return reduce(LCM, numbers)
def LCM(m, n): return (m * n // fractions.gcd(m, n))


n, m = MI()
bridge = sorted([LI() for _ in range(m)], key=lambda x: x[1])
ans = 0
endtime = 0
for i in range(m):
    if endtime <= bridge[i][0]:
        endtime = bridge[i][1]
        ans += 1 
print(ans)

Solution (Python):
class UnionFind():
    def __init__(self,n):
        self.parent = [-1 for _ in range(n)]

    def size(self,x):
        return -self.parent[self.find(x)]

    def find(self,x):
        if(self.parent[x]<0):
            return x
        else:
            self.parent[x]=self.find(self.parent[x])
            return self.parent[x]

    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if(x == y):
            return False
        if(self.size(x)<self.size(y)):
            self.parent[y]+=self.parent[x]
            self.parent[x]=y
        else:
            self.parent[x]+=self.parent[y]
            self.parent[y]=x
        return True

    def same(self,x,y):
        return self.find(x)==self.find(y)

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

di = {}
for i in ab:
    if(i[0] in di):
        di[i[0]].append(i[1])
    else:
        di[i[0]]=[i[1]]
    if(i[1] in di):
        di[i[1]].append(i[0])
    else:
        di[i[1]]=[i[0]]

joint = 0
un = UnionFind(N)
for i in range(N):
    if(i==0): pass
    else:
        flag = True
        if(i+1 in di):
            for j in di[i+1]:
                if(un.find(i-1)==un.find(j-1)):
                    flag = False
        if(flag):
            joint += 1
            un.unite(i-1,i)
print(N-1-joint)

Solution (Python):
import math
import copy
from collections import defaultdict
from collections import Counter
from collections import deque

from itertools import product

from itertools import permutations

from itertools import combinations
from bisect import bisect_left, bisect_right

 
def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W
 

dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def s_inpl(): return map(int,input().split())
def l_inpl(): return list(map(int, input().split()))
INF = float("inf")

N, M = l_inpl()
l = []
for _ in range(M):
    li = l_inpl()
    l.append(li)

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

ans = 0
cur = None
for li in l:
    if cur is None:
        cur = li[1] - 1
        ans += 1
    elif not (li[0] <= cur <= li[1]):
        cur = li[1] - 1
        ans += 1

print(ans)

Solution (Python):
N, M = map(int, input().split())
qs = [list(map(int, input().split())) for _ in range(M)]
qs.sort(key = lambda x: x[1], reverse = True)
ans = 0
prv = 0
while qs:
    a, b = qs.pop()
    if prv <= a:
        ans += 1
        prv = b
print(ans)

Solution (Python):
n,m=map(int,input().split())
st=[[] for i in range(n)]
en=[[] for i in range(n)]
ju=[0 for i in range(m)] 
for i in range(m):
    a,b=map(int,input().split())
    st[a-1].append(i)
    en[b-1].append(i)
ans=0
co=0
now=[]
while(co<n):
    if len(now)!=0 and len(en[co])!=0:
        ch=False
        for i in en[co]:
            if ju[i]==1:
                ch=True
        if ch:       
            for i in now:
                ju[i]=-1
            ans+=1
            now=[]
    for i in st[co]:
        ju[i]=1
        now.append(i)
    co+=1
print(ans)

Solution (Python):
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 b not in dic or dic[b] < a:
        dic[b] = a

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

Solution (Python):

import sys
import operator


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

    AB = list(zip(a,b))
    AB.sort(key=operator.itemgetter(1))

    db = []
    for a,b in AB:
        bAppend = True
        for di in db:
            if a <= di < b:
                bAppend = False
                break
        if bAppend:
            db.append(b-1)

    print(len(db))


    return



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

if __name__ == '__main__':
    main()

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

war.sort(key = lambda x: x[1])
ans = 0

r = -1
for i in range(M):
    if war[i][0] <= r:
        continue
    else:
        ans += 1
        r = war[i][1]-1
print(ans)

Solution (Python):
N,M = map(int,input().split())
L = sorted([list(map(int,input().split())) for i in range(M)],key = lambda x:x[1])
p,res = 0,0
for a,b in L:
    if a > p:
        p = b-1
        res += 1
print(res)

Solution (Python):
N,M = map(int,input().split())
L = [list(map(int,input().split())) for i in range(M)]
L.sort()
ans = 0
l,r = 0,0
for a,b in L:
    l = a
    if r <= a:
        ans += 1
        r = b
    else:
        r = min(r,b)
print(ans)

Solution (Python):
N,M = map(int,input().split())
L = [list(map(int,input().split())) for i in range(M)]
L.sort()
ans = 1
l = L[0][0]
r = L[0][1]
for a,b in L:
    if r <= a:
        ans += 1
        l = a
        r = b
    else:
        l = a
        r = min(r,b)
print(ans)

Solution (Python):
N,M = map(int,input().split())
L = [list(map(int,input().split())) for i in range(M)]
L.sort()
ans = 1
l = L[0][0]
r = L[0][1]
for a,b in L:
    if r <= a or l >= b:
        ans += 1
        l = a
        r = b
    else:
        l = a
        r = min(r,b)
print(ans)

Solution (Python):

N, M = map(int, input().split())
L = [tuple(map(int, input().split())) for i in range(M)]
L_sort = sorted(L, key=lambda x:x[1])
ans = 0
rb = 0
for l in L_sort:
    if l[0] > rb:
        rb = l[1] - 1
        ans += 1
print(ans)

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

count = 0
c = 0
for (a, b) in AB:
    if a >= c:
        count += 1
        c = b

print(count)

Solution (Python):

N,M= list(map(int,input().split(" ")))
yobos = []

for _ in range(M):
     yobos.append(list(map(int, input().split(" "))))
yobos.sort(key=lambda x:x[1])
right = yobos[0][1]
ans = 1
for yobo in yobos[1:]:
    if yobo[0] >= right:
        right = yobo[1]
        ans += 1
print(ans)

Solution (Python):

import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(N: int, M: int, a: "List[int]", b: "List[int]"):
    qs = sorted(list(zip(a, b)), reverse=True)
    
    ret = 0
    d = float('inf')
    for ai, bi in qs:
        if bi < d:
            ret += 1
            d = ai + 1
    return ret


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

if __name__ == '__main__':
    main()

Solution (Python):
import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def SI(): return input()
YN = lambda b: print('YES') if b else print('NO')
yn = lambda b: print('Yes') if b else print('No')

def main():
    N, M = LI()
    demands = []
    for i in range(M):
        demands.append(LI())

    demands = sorted(demands, key=lambda x: x[1])
    demands_met_flag = [False]*len(demands)

    counter = 0
    deleting_bridge = 0
    for i in range(len(demands)):
        if demands_met_flag[i] == True: continue
        if demands[i][0] <= deleting_bridge:
            demands_met_flag[i] = True
            continue
        demand = demands[i]
        demands_met_flag[i] = True
        counter += 1
        deleting_bridge = demand[1]-1

    print(counter)

main()

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

Solution (Python):
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(m)]
ab.sort()
L=10**6
ans=0
for a,b in ab[::-1]:
    if not a<=L<b:
        ans+=1
        L=a
print(ans)

Solution (Python):
import sys, os

f = lambda:list(map(int,input().split()))
if 'local' in os.environ :
    sys.stdin = open('./input.txt', 'r')

def solve():
    n , m = f()
    d = []
    for i in range(m):
        d.append(f())
    
    d = [(i[0], i[1]-1) for i in d]

    d = sorted(d, key = lambda x: (x[1]))


    cover = 0
    cnt = 0
    for i in d:
        if i[0]>cover:
            cover = i[1]
            cnt += 1

    
    print(cnt)



solve()

Solution (Python):
from functools import partial
from itertools import islice


def take(n, iterable):
    return list(islice(iterable, n))


def chunked(iterable, n):
    return iter(partial(take, n, iter(iterable)), [])


def solve(string):
    n, m, *ab = map(int, string.split())
    ab = sorted([tuple(_ab) for _ab in chunked(ab, 2)])
    cl = cr = None
    ans = 0
    for a, b in ab:
        if cr is None or cr <= a:
            cl, cr = a, b
            ans += 1
            continue
        cl = a if cl < a else cl
        cr = cr if cr < b else b
    return str(ans)


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(m)])))

Solution (Python):
from operator import itemgetter

N, M = list(map(int, input().split()))
ab = sorted([list(map(int, input().split())) for i in range(M)], key=itemgetter(1))
ans = B = 0

for a, b in ab:
    if a >= B:
        ans += 1
        B = b
print(ans)

Solution (Python):
N, M = [int(t) for t in input().split()]
a = [[0]*2 for i in range(M)]
for i in range(M):
    a[i][0], a[i][1] = [int(t) for t in input().split()]

b = sorted(a, key=lambda x: x[1])

count = 1
flag = b[0][1]
for i in range(1, M):
    if b[i][0] < flag:
        continue
    elif b[i][1] > flag:
        flag = b[i][1]
        count += 1

print(count)

Solution (Python):
N, M = [int(t) for t in input().split()]
a = [[0]*2 for i in range(M)]  
for i in range(M):
    s, e = [int(t) for t in input().split()]
    a[i][0] = s - 1
    a[i][1] = e - 1

b = sorted(a, key=lambda x: x[1])

count = 1
flag = b[0][1]
for i in range(1, M):
    if b[i][0] < flag:
        continue
    elif b[i][1] > flag:
        flag = b[i][1]
        count += 1

print(count)

Solution (Python):
from functools import partial
from itertools import islice


def take(n, iterable):
    return list(islice(iterable, n))


def chunked(iterable, n):
    return iter(partial(take, n, iter(iterable)), [])


def solve(string):
    n, m, *ab = map(int, string.split())
    ab = sorted([tuple(_ab) for _ab in chunked(ab, 2)])
    cl = cr = None
    ans = 0
    for a, b in ab:
        if cr is None or cr <= a:
            cl, cr = a, b
            ans += 1
            continue
        cl, cr = max(cl, a), min(cr, b)
    return str(ans)


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(m)])))

Solution (Python):
N,M=map(int,input().split())
T=[]
for i in range(M):
    u,v=map(int,input().split())
    u,v=u,v-1
    T.append([u,v])
T.sort(key=lambda x:x[1])
tmp=0
ans=0
for i in range(M):
    if tmp<T[i][0]:
        tmp=T[i][1]
        ans+=1
print(ans)

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

war.sort()

ans = 1
removed_bridge = war[0][0]-1
for i in range(M):
    if war[i][1] > removed_bridge:
        removed_bridge = war[i][0]-1
        ans += 1

print(ans)

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

s, t = list(), list()

for i in range(m):
    a, b = map(int, input().split())
    s.append(a)
    t.append(b)

time = list()
for i in range(m):
    time.append([s[i], t[i]])

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

ans = 0
now_end = 0

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

print(ans)

Solution (Python):
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)



N,M = map(int,input().split())
ab =[list(map(int,input().split())) for i in range(M)]
ab.sort(reverse=True)
ans = 0
tmp = inf
for i in range(M):
    if ab[i][1] > tmp:
        continue
    else:
        ans += 1
        tmp = ab[i][0]
print(ans)

Solution (Python):

import sys

def solve():
    pairs.sort(key=lambda pair: pair[1])
    cnt = 0
    base = 0
    for (a, b) in pairs:
        if a >= base:
            cnt += 1
            base = b
    return cnt

n, m = map(int, input().split())
pairs = [tuple(int(c) for c in input().split()) for _ in range(m)]
print(n, pairs, file=sys.stderr)
print(solve())

Solution (Python):
N,M=map(int,input().split())
need=[tuple(map(int,input().split())) for i in range(M)]
need.sort(key=lambda x:x[0])
ans=0
bef=0
for a,b in need:
    if a<=bef:
        bef=min(b-1,bef)
    else:
        ans+=1
        bef=b-1
print(ans)

Solution (Python):



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

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

bridge = sorted(bridge,key=lambda x:x[1])


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

Solution (Python):
n, m = map(int, input().split())
ab = []
for i in range(m):
    a, b = map(int, input().split())
    ab.append([a, b])
ab.sort()
ab += [[n, n + 1]]
ans = 0
s = 0
f = n

for i in range(m + 1):
    if ab[i][0] >= f:
        ans += 1
        s = ab[i][0]
        f = ab[i][1]
    else:
        if ab[i][1] < f:
            f = ab[i][1]
print(ans)

Solution (Python):

import sys


def solve(N: int, M: int, a: "List[int]"):
    a.sort(key=lambda x: x[1])
    ret = 1
    cur = a[0][1]
    for t in a:
        if t[0] >= cur:
            ret += 1
            cur = t[1]
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    a = []
    for i in range(M):
        a.append((int(next(tokens)), int(next(tokens))))
    solve(N, M, a)

if __name__ == '__main__':
    main()

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

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

fights = AB[:]

fights = sorted(fights, reverse=True)

import bisect


bridges = []
for a,b in fights:
    a_position = bisect.bisect(bridges, a)
    b_position = bisect.bisect(bridges, b)
    
    if a_position == b_position:
        bisect.insort(bridges, a+1)
        

print(len(bridges))