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-----
5 2
1 4
2 5

-----Sample Output-----
1

The requests can be met by removing the bridge connecting the second and third islands from the west.

Difficulty: interview

Starter code:

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

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)

n, m = map(int, input().split())
c = [[0] * 2 for _ in range(m)]
for i in range(m):
    c[i][1] , c[i][0] = map(int, input().split())
c.sort()  #橋を取り除く時はできるだけbの島に近いところで取り除くと良い。
x = -1  #直前に取り除いた橋のindex
ans = 0
for i in range(m):
    if c[i][1] > x:
        x = c[i][0] - 1
        ans += 1
print(ans)

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)


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)

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))
ans = [0]
for a, b in ab:
    if ans[-1] < a:
        ans.append(b-1)
print(len(ans) - 1)

N, M = list(map(int, input().split()))
B = [tuple(map(int, input().split())) for _ in range(M)]
B.sort()
r = 0
res = 0
for a, b in B:
    if a >= r:
        res += 1
        r = b
    else:
        r = min(r, b)
print(res)


import sys

n, m = map(int, sys.stdin.readline().split())

hostility = [[] for _ in range(m)]
for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    hostility[i].append(a - 1)
    hostility[i].append(b - 1)

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

cnt = 0
bridge = -1
for i in range(m):
    if hostility[i][0] <= bridge < hostility[i][1]:
        continue
    bridge = hostility[i][1] - 1
    cnt += 1
print(cnt)

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)    

def __starting_point():
    main()
__starting_point()

N, M = list(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)


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:
    # a が removed より大きい = まだ取り除いてない
    if a > removed:
        removed = b - 1
        ans += 1

print(ans)

N,M =  map(int, input().split())
li = []
for i in range(M):
    a, b = map(int, input().split())
    li.append([b,a])
li.sort()
an = 1
now_end = li[0][0]
for i in range(1,M):
    if now_end <= li[i][1]:
        an += 1
        now_end = li[i][0]
print(an)

n, m = list(map(int, input().split()))
ba = []
for i in range(m):
    a, b = [int(x) - 1 for x in 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)


_,*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)

def resolve():
    import sys
    from operator import itemgetter
    
    readline = sys.stdin.readline    # 1行だけ文字列にする

    N, M = list(map(int, readline().split()))
    AB = [list(map(int, readline().split())) for _ in [0] * M]
    AB.sort(key=itemgetter(1))
    islands = -float('inf')
    ans = 0
    for left, right in AB:
        if islands <= left:
            ans += 1
            islands = right
    print(ans)
    

def __starting_point():
    resolve()

__starting_point()

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:
    # a が removed より大きい = まだ取り除いてない
    if a > removed:
        removed = b - 1
        ans += 1

print(ans)

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:
    # a が removed より大きい = まだ取り除いていない
    if a > removed:
        removed = b - 1
        ans += 1

print(ans)

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)

N, M = map(int, input().split())
q = [list(map(int, input().split())) for _ in range(M)]
q = sorted(sorted(q, key=lambda x: x[0]), key=lambda x: x[1])

last = 0
cnt = 0
for a, b in q:
    if last < a:
        last = b-1
        cnt += 1

print(cnt)

# -*- coding: utf-8 -*-
# 標準入力を取得
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)


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

# 右側が小さい順にソート、制約a<bなのでそのまま使ってよい
Q = sorted(Q, key=lambda x: x[1])
# 境界、右側の区間の始まり
border = []

for a, b in Q:
    flag = True
    for x in border:
        # 既存の境界で分けられるか
        if a < x and x <= b:
            flag = False
            break
    if flag:
        border.append(b)

ans = len(border)
print(ans)

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

def solve() :
    ans,t=0,0
    for i in range (m) :
        if t<=R[i][1]:
            ans+=1
            t=R[i][0]
    return ans
print (solve ())

# atcoder -take a rest-(easy)
#typical greedy
def main():
    N, M = list(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


def __starting_point():
    main()



__starting_point()

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

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

arr.sort(key=lambda x: x[1])
ans = 1
_, pb = arr[0]
for a,b in arr[1:]:
  if a < pb <= b:
    pass
  else:
    ans += 1
    pb = b
print(ans)


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])#interval[1]の大きい順にソート

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

print(count)

x=c=0
for a,b in sorted([list(map(int,o.split()))for o in open(0)][1:],key=lambda p:p[1]):
 if a>x:x=b-1;c+=1
print(c)

import sys

input = sys.stdin.readline


def main():
    N, M = list(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)


def __starting_point():
    main()

__starting_point()

N, M = list(map(int, input().split()))
data = [list(map(int, input().split())) for _ in range(M)]
data = sorted(data, key=lambda x: x[1])

count = 1
left = data[0][1]
for i in range(1, M):
    if data[i][0] < left:
        left = max(data[i][0], left)
    else:
        count += 1
        left = data[i][1]
print(count)


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

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

ans = 0
bridge.sort()

sub = -1
ans = 0
for v in bridge:
  b, a = v[0], v[1]
  if a >= sub:
    sub = b
    ans += 1

print(ans)

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)

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)

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)

from operator import itemgetter

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

b = sorted(a, key=itemgetter(1))
#print(b)
removed = -1
ans = 0

for i in range(m):
  if b[i][0] > removed:
    removed = b[i][1] - 1
    ans += 1
    
print(ans)

import sys,math,collections,itertools
input = sys.stdin.readline

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


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



N, M = map(int, input().split())
needs = []
for i in range(M):
    x, y = map(int, input().split())
    needs.append((x, y))
needs.sort(key=lambda x: x[1])
pb = needs[0][1]
res = 1
for i in needs:
    if i[0] >= pb:
        res += 1
        pb = i[1]

print(res)

x=c=0
for b,a in sorted([[*map(int,t.split())][::-1]for t in open(0)][1:]):
 if a>x:x=b-1;c+=1
print(c)

n,m=map(int,input().split())
A=[]
for i in range(m):
    a,b=map(int,input().split())
    a-=1 ;b-=1
    A.append([a,b])

A=sorted(A, key=lambda x:x[1])
ans=0
last=-5000
for l in A:
    #print(a,b)
    if last<l[0]:
        ans+=1
        last=l[1]-1
print(ans)

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)

n,m=list(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)
    


def main():
    n,m = list(map(int,input().split()))
    brg = []
    for i in range(m):
        a,b = list(map(int,input().split()))
        brg.append([a-1,b-1])
    brg.sort()
    ans = 1
    s,e = brg[0]
    for i in range(1,m):
        s_,e_ = brg[i]
        if e_<=e:
            e = e_
        if s_>=s:
            s = s_
        if e <= s_:
            ans += 1
            s = s_
            e = e_
    print(ans)

def __starting_point():
    main()

__starting_point()

N, M, *A = list(map(int, open(0).read().split()))
*A, = list(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)


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

ab=sorted(ab, key=lambda x:(x[0],x[1]), reverse=True)
#print(ab)
now=10**5+1

preb=-1
ans=0
for i in range(m):
  if ab[i][1]==preb:
    continue
  if ab[i][1]<=now:
    now=ab[i][0]
    preb=ab[i][1]
    ans+=1
    #print("now",now)
print(ans)


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

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

ans = m
for i in range(1, m):
    if ab[i][0] < ab[i-1][1]:
        ab[i][1] = ab[i-1][1]
        ans -= 1
print(ans)


N, M = list(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)


n,m=map(int,input().split())
lst=[list(map(int,input().split())) for i in range(m)]
lst.sort(key=lambda x:x[1])
ans=1
pin=lst[0][1]-1

for i in range(1,m):
  if lst[i][0]>pin:
    ans+=1
    pin=lst[i][1]-1

print(ans)

n,m = map(int,input().split())
c = [list(map(int,input().split())) for _ in range(m)]
c.sort(key= lambda val : val[1])

left = 0
ans = 0
for i,[a,b] in enumerate(c):
    if left <= a:
        ans += 1
        left = b
print(ans)

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

import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

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

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

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

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

  return ans

# main()
print((main()))


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

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

recent_cut = -1#直近で切り落とした橋の左の街
for i in range(M):
    if recent_cut < ab[i][0]:
        recent_cut = ab[i][1]-1
        ans+=1
print(ans)


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
pos = 0
for i in range(M):
  if pos<ab[i][0]:
    ans+=1
    pos=ab[i][1]-1
print(ans)

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

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

ans = 1
for a, b in a_b_pairs[1:]:
    if a > right:
        right = b - 1
        ans += 1

print(ans)





# Segment tree (+)
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 = list(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)


import sys
import heapq, math
from itertools import zip_longest, permutations, combinations, combinations_with_replacement
from itertools import accumulate, dropwhile, takewhile, groupby
from functools import lru_cache
from copy import deepcopy

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

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

q = []
for ab in AB:
    heapq.heappush(q, ab)

ans = 0
cnt = M
visited = -1
while cnt > 0:
    ab = heapq.heappop(q)
    cnt -= 1

    # print(ab, visited, cnt)

    if ab[1] > ab[0]:
        heapq.heappush(q, [ab[1], ab[0]])
        cnt += 1
    else:
        if visited <= ab[1]:
            visited = ab[0]
            ans += 1
        else:
            pass

print(ans)

N, M = map(int, input().split())
a = []
for i in range(M):
    x, y = map(int, input().split())
    a.append([x, y])
a.sort(key=lambda x: x[1])
ans = 0
for i in range(M-1):
    if a[i+1][0] < a[i][1]:
        a[i+1][1] = a[i][1]
    else:
        ans += 1
ans += 1
print(ans)

INF = 10**9

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

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

end = 1
ans = 0
for i in range(M):
    if end <= requests[i][0]:
        ans += 1
        end = requests[i][1]

print(ans)

N,M = list(map(int,input().split()))
l = [list(map(int,input().split())) for _ in range(M)]
l.sort(key=lambda x: x[1])
broken_bridge = 0
position = 0
for i in range(M):
    if position<l[i][0]:
        broken_bridge+=1
        position = l[i][1]-1
print(broken_bridge)


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)

n,m=list(map(int,input().split()))
p=[]
for _ in range(m):
  a,b=list(map(int,input().split()))
  p.append([a,b])
#print(p)
p.sort(key=lambda x:x[1])
#print(p)
ans=0
cur=0
for i in range(m):
  if cur<=p[i][0]:
    #print("i:%d残す,cur:%d,p[i][1]:%d,p[i][0]:%d" % (i,cur,p[i][1],p[i][0]))
    ans+=1
    cur=p[i][1]
print(ans)


N,M = map(int,input().split())
arr = []
for _ in range(M):
  a,b = map(int,input().split())
  arr.append((a,b))
arr.sort(key=lambda x: x[1])
ans = 1
_, pb = arr[0]
for a,b in arr[1:]:
  if pb <= a:
    ans += 1
    pb = b
print(ans)

N, M = list(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 = []
#print(B)
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(remove)  
print((len(remove)))    




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))
#print(cd)
removed = -1
ans = 0

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

import sys
input = sys.stdin.readline

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

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

p = 0
t = 0

while len(bridges) > 0:
    t = bridges[0][1]
    p += 1
    bridges = [i for i in bridges if i[0] >= t]

print(p)

# -*- coding: utf-8 -*-

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)


def __starting_point():
    # 標準入力を取得
    N, M, requests = get_input()

    # メイン処理
    main(N, M, requests)

__starting_point()

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)

N, M = list(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  # 上で一つ壊してるので+1
for a, b in AB:
    if a <= last_b:
        continue
    else:
        last_b = b - 1
        cnt += 1
print(cnt)



n, m = list(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)


n, m = list(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)


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:
    # a が removed より大きい = まだ取り除いてない
    if a > removed:
        removed = b - 1
        ans += 1

print(ans)

(n, m), *l = [list(map(int, o.split())) for o in open(0)]
x = c = 0
for a, b in sorted(l, key = lambda p:p[1]):
  if a > x:
    x = b - 1
    c += 1
print(c)

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)

import sys
import math
import collections
import bisect
import copy

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: list(map(int, sys.stdin.readline().split()))
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list([int(x) - 1 for x in sys.stdin.readline().split()])


# ===CODE===


def main():
    n, m = ns()
    d = []
    for _ in range(m):
        a, b = ns()
        d.append([a - 1, b - 1])

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

    down = []

    for a, b in d:
        idx = bisect.bisect_left(down, a)
        if idx == len(down):
            down.append(b - 1)
    print((len(down)))


def __starting_point():
    main()

__starting_point()

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

# 右側が小さい順にソート、制約a<bなのでそのまま使ってよい
Q = sorted(Q, key=lambda x: x[1])
# 境界、右側の区間の始まり
border = -1
ans = 0

for a, b in Q:
    # 既存の境界で分けられないときは右にずらす
    if border <= a:
        ans += 1
        border = b

print(ans)

n, m = list(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)


n,m=map(int,input().split())
data=[]
for i in range(m):
  a,b=map(int,input().split())
  data.append([b,a])
data.sort()
r,l=data[0]
cnt=1
for i in range(1,m):
  if data[i][1]>=r:
    cnt+=1
    r,l=data[i]
  else:
    r=min(r,data[i][0])
    l=max(l,data[i][1])
print(cnt)

def IslandsWar():
    n, m = list(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)))
            
def __starting_point():
    IslandsWar()

__starting_point()

_,*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)

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)

import sys
import math
import collections
import bisect
import copy

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: list(map(int, sys.stdin.readline().split()))
na = lambda: list(map(int, sys.stdin.readline().split()))
na1 = lambda: list([int(x) - 1 for x in sys.stdin.readline().split()])


# ===CODE===


def main():
    n, m = ns()
    d = []
    for _ in range(m):
        a, b = ns()
        d.append([a - 1, b - 1])

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

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


def __starting_point():
    main()

__starting_point()

import bisect
N, M, *AB = [int(_) for _ in open(0).read().split()]
AB = sorted(zip(AB[::2], AB[1::2]))
l, r = AB[0]
ans = 1
for a, b in AB[1:]:
    if r <= a:
        l, r = a, b
        ans += 1
    else:
        r = min(r, b)
print(ans)


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)

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
    # print(ab)
    right = -1
    for a, b in ab:
        if right <= a:
            right = b
            ans += 1

    print(ans)

def __starting_point():
    resolve()

__starting_point()

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)

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

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

def main():
    N, M = list(map(int, input().split()))
    ab = []
    for _ in range(M):
        a, b = [int(x)-1 for x in input().split()]
        ab.append((b,a))
    ab.sort()
    # print(ab)
    ans = 0
    x = -1
    for i in range(M):
        if ab[i][1] > x:
            ans += 1
            x = ab[i][0]-1
    print(ans)

def __starting_point():
    main()

__starting_point()

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:
    # a が removed より大きい = まだ取り除いてない
    if a > removed:
        removed = b - 1
        ans += 1

print(ans)

#!/usr/bin/env python3

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

# for i in range():

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

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

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

print(ans)


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

ab.sort(key=lambda x: x[1])  # Sort the list of (a, b) by b

ans = 0
cur = -1
for i in range(M):
    a, b = ab[i]
    if a < cur:
        continue
    ans += 1
    cur = b

print(ans)


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)

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])
#print(warzones)
shaku = warzones[0]
cnt = 1
for i in range(1,M):
    #print(shaku)
    #尺継続条件
    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で再初期化
'''

# 初期入力
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を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)

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)

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 = list(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


def __starting_point():
    main()

__starting_point()

n,m = list(map(int,input().split()))
l = sorted(list( list(map(int,input().split())) for _ in range(m)), key=lambda x: x[1])
br = -1
ans = 0
for i in l:
    head, tail = i[0], i[1]
    if head < br:
        continue
    else:
        br = tail
        ans += 1
print(ans)


import sys
input = sys.stdin.readline

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


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


# -*- coding: utf-8 -*-
# 標準入力を取得
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)