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

from operator import add
from sys import stdin


class SegmentTree:
    def __init__(self, size, op, e):
        self._op = op
        self._e = e
        self._size = size
        t = 1
        while t < size:
            t *= 2
        self._offset = t - 1
        self._data = [e] * (t * 2 - 1)

    def __getitem__(self, key):
        return self._data[self._offset + key]

    def __setitem__(self, key, value):
        op = self._op
        data = self._data
        i = self._offset + key
        data[i] = value
        while i >= 1:
            i = (i - 1) // 2
            data[i] = op(data[i * 2 + 1], data[i * 2 + 2])

    def build(self, iterable):
        op = self._op
        data = self._data
        data[self._offset:self._offset + self._size] = iterable
        for i in range(self._offset - 1, -1, -1):
            data[i] = op(data[i * 2 + 1], data[i * 2 + 2])

    def query(self, start, stop):
        def iter_segments(data, l, r):
            while l < r:
                if l & 1 == 0:
                    yield data[l]
                if r & 1 == 0:
                    yield data[r - 1]
                l = l // 2
                r = (r - 1) // 2
        op = self._op
        it = iter_segments(self._data, start + self._offset,
                           stop + self._offset)
        result = self._e
        for v in it:
            result = op(result, v)
        return result

readline = stdin.readline

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

ab.sort(key=lambda x: x[1])
st = SegmentTree(N - 1, add, 0)

result = 0
for a, b in ab:
    a, b = a - 1, b - 1
    if st.query(a, b) != 0:
        continue
    result += 1
    st[b - 1] = 1
print(result)

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

l=[list(map(int,input().split())) for i in range(m)]
from operator import itemgetter as it
l.sort(key=it(1))
head=0
ans=0
for a,b in l:
    if not(a<head<=b):ans+=1;head=b
print(ans)

Solution (Python):

icase=0
if icase==0:
    n,m=map(int,input().split())
    ab=[[0]*2 for i in range(m)]
    for i in range(m):
        ai,bi=map(int,input().split())
        ab[i]=[ai-1,bi-1]
    ab.sort(reverse=True)
elif icase==1:
    n,m=5,2
    ab=[[1, 4], [0, 3]]
elif icase==2:
    n,m=9,5
    ab=[[6, 8], [3, 5], [2, 4], [1, 6], [0, 7]]
elif icase==3:
    n,m=5,10
    ab=[[3, 4], [2, 4], [2, 3], [1, 4], [1, 3], [1, 2], [0, 4], [0, 3], [0, 2], [0, 1]]

istat=0
icnt=0
while True:
    lower=ab[istat][0]

    ii=istat
    while lower<ab[ii][1]:
        ii+=1
        if ii>=m:
            break
    istat=ii
    icnt+=1
    if ii>=m:
        break
    
print(icnt)

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

    for i, j in a[1:]:
        check = False
        for k in removes:
            if i < k:
                check = True
                break
        if not check:
            removes.append(j)
    print(len(removes))
            
if __name__ == "__main__":
    IslandsWar()

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

a_b_l = sorted(a_b_l, key=lambda x: x[1])
ans = 0
prev_removed_bridge = 0
for a, b in a_b_l:
    if a <= prev_removed_bridge:
        continue
    prev_removed_bridge = b - 1
    ans += 1
print(ans)

Solution (Python):


def get_input() -> tuple:
    """
    標準入力を取得する.

    Returns:\n
        tuple: 標準入力
    """
    N, M = list(map(int, input().split()))
    requests = []
    for i in range(M):
        a_i, b_i = list(map(int, input().split()))
        requests.append((a_i, b_i))

    return N, M, requests


def main(N: int, M: int, requests: list) -> None:
    """
    メイン処理.

    Args:\n
        N (int): 島の数(2 <= N <= 10^5)
        M (int): 要望の数(1 <= M <= 10^5)
        requests (list): 要望(1 <= a_i < b_i <= N)
    """
    
    requests = sorted(requests, key=lambda x: x[1])
    bridge = 0
    ans = 0
    for i in range(M):
        a_i, b_i = requests[i]
        if a_i > bridge:
            bridge = b_i - 1
            ans += 1

    
    print(ans)


if __name__ == "__main__":
    
    N, M, requests = get_input()

    
    main(N, M, requests)

Solution (Python):


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


requests = sorted(requests, key=lambda x: x[1])
bridge = 0
ans = 0
for i in range(M):
    a_i, b_i = requests[i]
    if a_i > bridge:
        bridge = b_i - 1
        ans += 1


print(ans)

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

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

ans = 1
current = req[0][1]
for i in range(1, len(req)):
    if req[i][0] < current:
        continue
    current = req[i][1]
    ans += 1
print(ans)

Solution (Python):


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


requests = sorted(requests, key=lambda x: x[1])
bridges = [requests[0][1] - 1]
for i in range(M):
    a_i, b_i = requests[i]
    if (bridges[-1] < a_i) or (b_i <= bridges[-1]):
        bridges.append(b_i - 1)
ans = len(bridges)


print(ans)

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

intervals = []
for conflict in conflicts:
    intervals.append([conflict[0], conflict[1]-1])

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

count = 0
end = -float("inf")
for interval in intervals:
    if interval[0] > end:
        count += 1
        end = interval[1]

print(count)

Solution (Python):
import sys
input = sys.stdin.readline
INF = 10**18

def li():
    return [int(x) for x in input().split()]


N, M = li()

Intervals = [li() for _ in range(M)]

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

last_end = - INF
required_cnt = 0
for interval in Intervals:
    start, end = interval[0], interval[1]
    
    
    if last_end <= start:
        last_end = end
        required_cnt += 1

print(required_cnt)

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

left=a[0][0]
right=a[0][1]

ans=1

for i in range(1,m):
  x=a[i][0]
  y=a[i][1]
  
  if left<=x<right:
    left=x
    right=min(right,y)
    
  else:
    ans+=1
    left=x
    right=y
    
print(ans)

Solution (Python):
from operator import itemgetter
N,M=map(int,input().split())
islands=[list(map(int,input().split())) for _ in range(M)]
islands.sort(key=itemgetter(1))

i=0
cnt=0
while i<M:
    j=0
    while i+j<M and islands[i+j][0]<islands[i][1]:
        j+=1
    i+=j
    cnt+=1
print(cnt)

Solution (Python):
import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N, M = LI()
    ab = [LI_() for _ in range(M)]
    ab.sort(key=lambda x: x[1])

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

    print(ans)

if __name__ == '__main__':
    resolve()

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

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

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

Solution (Python):
N,M = map(int,input().split())
table = []
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    table.append((a,b))
table = sorted(table,key=lambda x:x[1])
cur_r = table[0][1]
ans = 1
for i in range(1,M):
    l,r = table[i]
    if cur_r <= l:
        ans += 1
        cur_r = r

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

import sys
input = sys.stdin.readline  

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


ab.sort(key=lambda x: x[1],reverse=True)
max_a =ab[0][0]
for a,b in ab:
    if max_a < b:
        max_a =max(max_a,a)
        continue
    else:
        max_a =a
        ans +=1
print(ans)

Solution (Python):
N, M = map(int, input().split())
B = [0] * M
for i in range(M):
  B[i] = list(map(int, input().split()))
  
B = sorted(B, key = lambda x:x[1])
remove = []

for i in range(M):
  a, b = B[i][0], B[i][1]
  if remove == []:
    remove.append(b - 1)
  elif max(remove) >= a:
    continue
  else:
    remove.append(b - 1)
  
print(len(remove))

Solution (Python):


def main():
    N, M = map(int, input().split())
    conflict = [tuple(map(int, input().split())) for i in range(M)]
    newest_destroyed = -1
    conflict.sort(key=lambda x: x[1])
    res = 0
    for l, r in conflict:
        if not (l <= newest_destroyed < r):
            res += 1
            newest_destroyed = r-1
    print(res)
    return


if __name__ == "__main__":
    main()

Solution (Python):


def main():
    N, M = map(int, input().split())
    conflict = [tuple(map(int, input().split())) for i in range(M)]
    newest_destroyed = -1
    conflict.sort(key=lambda x: x[1])
    res = 0
    for l, r in conflict:
        if not (l <= newest_destroyed < r):
            res += 1
            newest_destroyed = r-1
    print(res)
    return


if __name__ == "__main__":
    main()

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

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

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

ab = []
for _ in range(M):
    a, b = map(int, input().split())
    ab.append((a, b))
ab.sort(key=lambda ab: ab[::-1])

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

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

def main():
    n, m = map(int, input().split())
    
    ab = [0] * m
    for ind in range(m):
        i, j = map(int, input().split())
        ab[ind] = (i-1, j-1)
    
    ab.sort()

    ans = 1
    right = ab[0][1]
    for ind in range(1, m):
        
        if right <= ab[ind][0]:
            ans += 1
            right = ab[ind][1]

        
        elif ab[ind][1] < right:
                right = ab[ind][1]
        
        
            
    
    print(ans)

main()

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

def main():
    n, m = map(int, input().split())
    
    ab = [0] * m
    for ind in range(m):
        i, j = map(int, input().split())
        ab[ind] = (i-1, j-1)
    
    ab.sort()

    ans = 1
    right = ab[0][1]
    for ind in range(1, m):
        
        if right <= ab[ind][0]:
            ans += 1
            right = ab[ind][1]

        
        elif ab[ind][1] < right:
                right = ab[ind][1]
        
        
            
    
    print(ans)

main()

Solution (Python):
n,m=map(int,input().split())
B=[]
for _ in range(m):
  a,b=map(int,input().split())
  B.append([a-1,b-1])
  
B=sorted(B,key=lambda x:x[1])
ans=m
for i in range(1,m):
  if B[i][0]<B[i-1][1]:
    ans-=1
    B[i][1]=B[i-1][1]
    
print(ans)

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

res = 0
min_r = 0
for ab in ab_list:
    if min_r <= ab[0]:
        res += 1
        min_r = ab[1]
print(res)

Solution (Python):
N,M=list(map(int,input().split()))
ans=0
l=[]
for i in range(M):
   a,b=(map(int,input().split()))
   l.append((a,b))
l.sort(key=lambda x:x[1])
cut=-1
for i,j in l:
   if cut>=i:
      continue
   else:
      ans+=1
      cut=j-1
print(ans)

Solution (Python):
N,M = map(int,input().split())
ls = [tuple(map(int,input().split())) for _ in range(M)]
ls.sort(key=lambda x:x[1],reverse=True)
ls.sort(key=lambda x:x[0],reverse=True)
r = N
cnt = 0
for i in range(M):
    a,b = ls[i]
    if b <= r:
        cnt += 1
        r = a
print(cnt)

Solution (Python):
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    n, m = LI()
    span = [None for _ in range(m)]
    for i in range(m):
        a, b = LI()
        span[i] = [a,b]
    span.sort(key=lambda x: x[1])
    choice = [0, 0]
    ans = 0
    for each_span in span:
        if choice[1]<=each_span[0]:
            choice = each_span
            ans += 1
    print(ans)
main()

Solution (Python):
N,M = map(int,input().split())
W = sorted([list(map(int,input().split())) for m in range(M)],key=lambda x:x[1])
c = 0
x = 0

for a,b in W:
   if x<a:
      x=b-1
      c+=1

print(c)

Solution (Python):
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 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]-0.1
  for x,y in l[1:]:
    if x<kiru<y:
      continue
    ans+=1
    kiru=y-0.1

  return ans


print(main())

Solution (Python):
n,m=map(int,input().split())
ans=0
head=1
from operator import itemgetter as it
for x,y in sorted([list(map(int,input().split()))for i in range(m)],reverse=0,key=lambda x:(it(1)(x)*(n+1)*10-it(0)(x))):
    if not(x<head <=y):
        head=y
        ans+=1
print(ans)

Solution (Python):
N,M = map(int,input().split())
warzones = [[] for i in range(M)]
for i in range(M):
    a,b = map(int,input().split())
    a -= 1
    b -=1
    warzones[i] = [a,b]
warzones = sorted(warzones,key=lambda x:x[0])

shaku = warzones[0]
cnt = 1
for i in range(1,M):
    
    
    if(warzones[i][0] < shaku[1]):
        shaku[0] = max(warzones[i][0],shaku[0])
        shaku[1] = min(warzones[i][1],shaku[1])
    else:
        cnt += 1
        shaku = warzones[i]

print(cnt)

'''尺取法の初期化
最初に配列のlists[0]で初期化
for i in range(1,M):でまわして
okの場合lists[i]を代入
ngのときはカウントを増やしてngで再初期化
'''

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

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

Rsort = sorted(AB, key=lambda x: x[1])
cnt = 0
R = 0

for a, b in Rsort:
  if a <= R:
    continue
  else:
    cnt += 1
    R = b-1

print(cnt)

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

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

Rsort = sorted(AB, key=lambda x: x[1])
cnt = 0
R = 0

for a, b in Rsort:
  if a <= R:
    continue
  else:
    cnt += 1
    R = b-1

print(cnt)

Solution (Python):
n, m = list(map(int, input().split()))
ab = [list(map(int, input().split())) for i in range(m)]
ab.sort()
ans = 0
now = 1
for i in range(m):
	if now <= ab[i][0]:
		ans += 1
		now = ab[i][1]
	now = min(now, ab[i][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])
ans = 0
s = 0 
for i in range(M):
    a, b = ab[i]
    if a >= s: 
        
        s = b
        ans += 1
print(ans)

Solution (Python):
n, m  = map(int, input().split())
a = [list(map(int, input().split())) for i in range(m)]
a = sorted(a, key=lambda x :x[1])
bridge = a[0][1] - 1
ans = 1

for i in range(1, m):
    if a[i][0] > bridge:
        bridge = a[i][1] - 1
        ans += 1
        
print(ans)

Solution (Python):
import sys


def main():
    input = sys.stdin.buffer.readline
    n, m = map(int, input().split())
    demand = [tuple(map(int, input().split())) for _ in range(m)]
    demand.sort(key=lambda x: x[1])
    prev_cut = 0
    ans = 0
    for a, b in demand:
        if prev_cut < a:
            ans += 1
            prev_cut = b - 1
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
from operator import itemgetter

n, m = map(int, input().split())
a = [0] * m
b = [0] * m

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

ab = sorted([(a[i], b[i]) 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())

instructions = []
for _ in range(M):
    a = list(map(int, input().split()))
    instructions.append(a)
instructions.sort(key=lambda x:x[1])

ans = 0
current = 0
for a, b in instructions:
    if current < a: 
        current = b-1
        ans += 1
print(ans)

Solution (Python):
from operator import itemgetter
n,m = map(int,input().split())
lis = []
for _ in range(m):
    lis.append(list(map(int,input().split())))
lis.sort(key = itemgetter(1))
ans = 0
last = 0
for i in range(m):
    if last <= lis[i][0]:
        ans += 1
        last = lis[i][1]
print(ans)

Solution (Python):
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][1]
        cnt -= 1
 
print(cnt)

Solution (Python):

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 = 0
con_l = 0

for i in range(m):
    if con_l <= l[i][0]:
        cnt += 1
        con_l = l[i][1]

print(cnt)

Solution (Python):
n_node, Q = map(int,input().split())
Q_ls = [[0,0] for _ in range(Q)]
for i in range(Q):
    a,b = map(int,input().split())
    Q_ls[i] = [a-1,b-1]
Q_ls.sort(key=lambda x: x[1])

last_r = -1
ans = 0
for i in range(Q):
    if Q_ls[i][1] > last_r and Q_ls[i][0] >= last_r:
        ans += 1
        last_r = Q_ls[i][1]
print(ans)

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


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

ans = 0



pre_x = 0

for a, b in ab_list:
    
    if pre_x >= a:
        continue
    
    else:
        pre_x = b - 1
        ans += 1
print(ans)

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

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

ans = 0
pre_x = -1
for a, b in ab_list:
    
    if pre_x >= a:
        continue
    
    else:
        pre_x = b - 1
        ans += 1
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])
s = ab[0][1]
ans = 1
for i in ab:
    if s <= i[0]:
        ans += 1
        s = i[1]
print(ans)

Solution (Python):
from operator import itemgetter

N, M = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(M)]
ab = sorted(ab, key=itemgetter(1))


removed = -1
ans = 0

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

print(ans)

Solution (Python):
def Schedule(schedule):
    """
    :return: 複数の区間が与えられた時の重複の無い区間の選び方の最大数
    """
    schedule = sorted(schedule, key=lambda x: x[1])
    N = len(schedule)
    res = 0
    end = -float("inf")

    for i in range(N):
        if end <= schedule[i][0]:  
            end = schedule[i][1]  
            res += 1
    return res



import sys
input = sys.stdin.readline

N, M = map(int, input().split())
schedule = []
for i in range(M):
    start, end = map(int, input().split())
    schedule.append((start, end))               

print(Schedule(schedule))

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
ab = [tuple(map(int, input().split())) for _ in range(m)]
from heapq import heappop as hpp, heappush as hp
h = []
for i,(a,b) in enumerate(ab):
    hp(h, (a,i,0))
ans = 0
m = -1
while h:
    val,ind,c = hpp(h)
    if c==0:
        hp(h, (ab[ind][1],ind,1))
    else:
        if m>=0 and ab[ind][0]<=m<val:
            pass
        else:
            m = ab[ind][1]-1
            ans += 1

print(ans)

Solution (Python):

f=lambda:map(int,input().split())
N,M=f()
wars=[]
for i in range(M):
    l,r=f()
    wars.append((r,l))
wars.sort()

res=M
r,l=wars.pop(0)
for nr,nl in wars:
    if nl<r:
        res-=1
    else:
        r=nr
print(res)

Solution (Python):
def main():
    N, M = map(int, input().split())
    X = []
    for _ in range(M):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        X.append([a,b])
    
    X.sort(key=lambda x: x[1])
    cnt = 1
    now = X[0][1]
    for a, b in X:
        if now <= a:
            cnt += 1
            now = b

    print(cnt)



if __name__ == "__main__":
    main()

Solution (Python):
import sys

input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    AB = [None] * M
    for i in range(M):
        AB[i] = tuple(map(int, input().split()))

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

    ans = 0
    prev_x = -1
    for a, b in AB:
        if a <= prev_x < b:
            pass
        else:
            ans += 1
            prev_x = b - 1

    print(ans)


if __name__ == "__main__":
    main()

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

condition.sort(key=lambda a: (a[1], a[0]))

right_end = 0
ans = 0
for c in condition:
    if c[0] >= right_end:
        ans += 1
        right_end = c[1]
print(ans)

Solution (Python):
n, m = map(int, input().split())
ab = sorted([tuple(map(int, input().split())) for _ in range(m)], key = lambda x:x[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())
AB = sorted([list(map(int, input().split())) for _ in range(M)])

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

last_b = AB[0][1] - 1  
cnt = 1  
for a, b in AB:
    if a <= last_b:
        continue
    else:
        last_b = b - 1
        cnt += 1
print(cnt)

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())
items = [list(map(int, input().split())) for i in range(M)]
items = sorted(items, key=lambda x: x[1])
last = 0
res = 0
for a, b in items:
    if last <= a:
        res += 1
        last = b
print(res)

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

ls = []
for i in range(m):
    x,l = map(int,input().split())
    ls.append([x,l])
    
ls = sorted(ls, key=lambda x: x[1])
ans =m
for i in range(1,m):
    if ls[i][0] < ls[i-1][1]:
      ls[i][1] = ls[i-1][1]
      ans -=1
        
print(ans)

Solution (Python):
_,*l = [list(map(int,i.split())) for i in open(0)]
l.sort(key=lambda x:x[1])
A=S=0
for s,t in l:
    if S<=s:
        A+=1
        S=t
print(A)

Solution (Python):
_,*li = [list(map(int,i.split())) for i in open(0)]
li.sort(key=lambda x:x[1])
A = 0
S = 0
for s,t in li:
    if S<=s:
        A+=1
        S=t
print(A)

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

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

want_list = [0]*(N+1)
for _ in range(M):
    a,b = map(int,input().split())
    want_list[b]=max(want_list[b],a)



cnt = 0
cutNo = 0
for idx,val in enumerate(want_list):
    if val >cutNo:
        cutNo = idx-1
        cnt += 1
print(cnt)

Solution (Python):
import sys,math,collections,itertools
input = sys.stdin.readline

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

want_list = [0]*(N+1)
for _ in range(M):
    a,b = map(int,input().split())
    want_list[b]=max(want_list[b],a)



cnt = 0
cutNo = 0
for idx,val in enumerate(want_list):
    if val >cutNo:
        cutNo = idx-1
        cnt += 1
print(cnt)

Solution (Python):
import sys
import math
import itertools
import collections
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    N, M = NMI()
    ab = [NLI() for _ in range(M)]
    
    ENDsorted_sections= sorted(ab, key=lambda x: x[1])
    
    ans = 1
    dropped_bridge = ENDsorted_sections[0][1]

    for m in range(M):
        if ENDsorted_sections[m][0] >= dropped_bridge:
            ans += 1
            dropped_bridge = ENDsorted_sections[m][1]
    print(ans)    

if __name__ == '__main__':
    main()

Solution (Python):
N,M,*A=map(int,open(0).read().split());c=0
for a,b in sorted(zip(*[iter(A)]*2))[::-1]:
	if b<=N:c+=1;N=a
print(c)

Solution (Python):
N, M, *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)

Solution (Python):
n, m = map(int, input().split())
ba = []
for i in range(m):
    a, b = map(lambda x: int(x) - 1, input().split())
    ba.append((b,a))
ba.sort()
count = 0
prev_b = -1
for b, a in ba:
    if a < prev_b:
        continue
    prev_b = b
    count += 1
print(count)

Solution (Python):
import sys
from operator import itemgetter

read = sys.stdin.buffer.read
INF = 1 << 60


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

    Q = list(zip(*[iter(AB)] * 2))
    Q.sort(key=itemgetter(1))

    ans = 0
    last = 0
    for a, b in Q:
        if last < a:
            last = b - 1
            ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from operator import itemgetter

read = sys.stdin.buffer.read
INF = 1 << 60


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

    Q.sort(key=itemgetter(1))

    ans = 0
    last = -1
    for a, b in Q:
        if last < a:
            last = b - 1
            ans += 1

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.buffer.read
INF = 1 << 60


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

    Q = [[] for _ in range(N - 1)]
    for a, b in zip(*[iter(AB)] * 2):
        Q[a - 1].append(b - 2)

    min_y = INF
    ans = 0
    for i, ys in enumerate(Q):
        if ys:
            min_y = min(min_y, min(ys))
        if i == min_y:
            ans += 1
            min_y = INF

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys

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 = [[] for _ in range(N - 1)]
    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2)):
        Q[a - 1].append(b - 2)

    min_y = INF
    ans = 0
    for i, ys in enumerate(Q):
        if ys:
            min_y = min(min_y, min(ys))
        if i == min_y:
            ans += 1
            min_y = INF

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
'''
自宅用PCでの解答
'''
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7
dir = [(-1,0),(0,-1),(1,0),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"

class Binary_Indexed_Tree:
    
    
    def __init__(self,n):
        self.N = n
        self.BIT = [0]*(n+1)
        self.l2 = 2**(len(format(n,'b'))-1)

    
    def query(self,idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    
    def update(self,idx,x):
        while idx <= self.N:
            self.BIT[idx] += x
            idx += idx&(-idx)
        return

    def lower_bound(self,w):
        if w <= 0:
            return 0
        x = 0
        k = self.l2
        while k > 0:
            if x+k <= self.N and self.BIT[x+k] < w:
                w -= self.BIT[x+k]
                x += k
            k //= 2
        return x+1

    def upper_bound(self,w):
        x = 0
        k = self.l2
        while k > 0:
            if x+k <= self.N and self.BIT[x+k] <= w:
                w -= self.BIT[x+k]
                x += k
            k //= 2
        return x


def main():
    n,m = map(int,ipt().split())
    nms = []
    for i in range(m):
        a,b = map(int,ipt().split())
        nms.append(b*(10**6)+a)
    nms.sort()

    ans = 0
    bt = Binary_Indexed_Tree(n)

    for i in nms:
        a = i%(10**6)
        b = i//(10**6)
        if bt.query(b)-bt.query(a):
            continue
        else:
            bt.update(b,1)
            ans += 1

    print(ans)



    return None

if __name__ == '__main__':
    main()

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
cur = -1
for i in range(M):
    a, b = ab[i]
    if a < cur:
        continue
    ans += 1
    cur = b

print(ans)

Solution (Python):
from operator import itemgetter

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

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

removed = -1
ans = 0

for a, b in cd:
  if a > removed:
    removed = b - 1
    ans += 1
    
print(ans)