AtCoder Beginner Contest 103 - Islands War

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.

Source: atcoder | Difficulty: MEDIUM


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


(n, m) = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
ab = sorted(ab, key=lambda x: x[1])
ans = 0
bridge = 0
for i in range(m):
	if bridge < ab[i][0]:
		ans += 1
		bridge = ab[i][1] - 1
print(ans)


(n, m) = map(int, input().split())
mx = [-1 for i in range(0, n)]
for z in range(0, m):
	(a, b) = map(int, input().split())
	mx[b - 1] = max(mx[b - 1], a - 1)
cut = -1
cn = 0
for z in range(0, n):
	if cut < mx[z]:
		cut = z - 1
		cn = cn + 1
print(cn)


(n, m) = map(int, input().split())
ab = sorted([list(map(int, input().split())) for _ in [0] * m], key=lambda x: x[1])
x = 0
l = [0] * n
for (a, b) in ab:
	if a > x:
		x = b - 1
		l[x] = 1
print(sum(l))


(N, M) = map(int, input().split())
ab = sorted([list(map(int, input().split())) for _ in range(M)], key=lambda x: x[1])
x = l = 0
for (a, b) in ab:
	if x < a:
		x = b - 1
		l += 1
print(l)


(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) = map(int, input().split())
L = []
for i in range(M):
	(a, b) = map(int, input().split())
	L.append((b, a))
L = sorted(L)
preb = 0
ans = 0
for l in L:
	(b, a) = l
	if preb <= a:
		ans += 1
		preb = b
print(ans)


(N, M) = map(int, input().split())
m = [list(map(int, input().split()))[::-1] for _ in range(M)]
m.sort()
b = []
for i in m:
	if len([tmp for tmp in b if tmp >= i[1]]) == 0:
		b.append(i[0] - 1)
print(len(b))


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


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


(N, M) = map(int, input().split())
Q = [tuple(map(int, input().split())) for _ in range(M)]
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())
ab = [list(map(int, input().split())) for _ in range(M)]
ab.sort(key=lambda x: x[1])
ans = 0
x = -9999999999
for (a, b) in ab:
	if x <= a:
		x = b
		ans += 1
print(ans)


(n, m) = map(int, input().split())
SG = sorted([[int(i) for i in input().split()] for i in range(m)], key=lambda x: x[1])
cnt = 1
b = SG[0][1]
for (s, g) in SG:
	if s >= b:
		b = g
		cnt += 1
print(cnt)


(n, m) = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(m)]
l.sort(key=lambda x: x[1])
res = 0
pos = 0
for (a, b) in l:
	if (a - pos) * (b - pos) > 0:
		res += 1
		pos = b - 0.5
print(res)


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


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


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)


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


(N, M) = map(int, input().split())
ablist = sorted([tuple(map(int, input().split())) for _ in range(M)], key=lambda x: x[1])
broken = 0
ans = 0
for (a, b) in ablist:
	if a > broken:
		ans += 1
		broken = b - 1
print(ans)


(N, M) = list(map(int, input().split()))
D = []
L = [0] * N
for i in range(M):
	D.append(list(map(int, input().split())))
D.sort(key=lambda x: x[1])
Ans = 0
Re = 0
for i in D:
	if Re < i[0]:
		Re = i[1] - 1
		Ans += 1
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())
a = []
for i in range(m):
	(x, y) = map(int, input().split())
	a.append((x, y))
a.sort(key=lambda x: x[1])
ans = 1
(l, r) = a[0]
for (x, y) in a[1:]:
	if r <= x:
		ans += 1
		l = x
		r = y
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:
	if a > removed:
		removed = b - 1
		ans += 1
print(ans)


(n, m) = map(int, input().split())
requests = [list(map(int, input().split())) for _ in range(m)]
requests.sort(key=lambda x: x[1])
ans = 0
pos = 0
for (a, b) in requests:
	if pos <= a:
		ans += 1
		pos = b
print(ans)


(n, m) = map(int, input().split())
ab = [[int(i) for i in input().split()] for j in range(m)]
ab = sorted(ab, reverse=True)
ans = 0
check = float('inf')
for (a, b) in ab:
	if b <= check:
		check = a
		ans += 1
print(ans)


(n, m) = map(int, input().split())
ass = [tuple(map(int, input().split())) for i in range(m)]
ass.sort(key=lambda x: x[1])
reg = 0
counter = 0
for ab in ass:
	if ab[0] >= reg:
		counter = counter + 1
		reg = ab[1]
print(counter)


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


(N, M) = map(int, input().split())
req = [tuple(map(int, input().split())) for _ in range(M)]
req.sort(key=lambda x: x[1])
res = 0
i = 1
for m in range(M):
	if req[m][0] >= i:
		i = req[m][1]
		res += 1
print(res)


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


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


(n, m) = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab.sort()
(l, r) = ab[0]
ans = 1
for (a, b) in ab[1:]:
	if r <= a:
		ans += 1
		(l, r) = (a, b)
	else:
		l = max(l, a)
		r = min(r, b)
print(ans)


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)


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)


(n, m) = map(int, input().split())
s = []
for i in range(m):
	(a, b) = map(int, input().split())
	s.append([a, b - 1])
s.sort(key=lambda x: x[1])
ans = 0
t = None
for (i, j) in s:
	if t is None or t < i:
		t = j
		ans += 1
print(ans)


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


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


(N, M) = map(int, input().split())
L = []
for _ in range(M):
	L.append(list(map(int, input().split())))
L = sorted(L, key=lambda x: x[1])
now = -10
cnt = 0
for x in L:
	if now <= x[0]:
		now = x[1]
		cnt += 1
print(cnt)


(N, M) = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
ab.sort(key=lambda x: x[1])
point = 0
cnt = 0
for (a, b) in ab:
	if a < point:
		continue
	else:
		cnt += 1
		point = b
print(cnt)


(N, M) = map(int, input().split())
NG = []
for _ in range(M):
	(a, b) = map(int, input().split())
	NG.append((a - 1, b - 1))
NG.sort(key=lambda x: x[1])
x = 0
Ans = 0
for i in range(M):
	if NG[i][0] >= x:
		x = NG[i][1]
		Ans += 1
print(Ans)


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
ab.sort()
m = 0
ans = 0
for (a, b) in ab:
	if m <= a:
		ans += 1
		m = n
	m = min(b, m)
print(ans)


(N, M) = map(int, input().split())
Q = [tuple(map(int, input().split())) for i in range(M)]
Q.sort(key=lambda x: x[1])
ans = 0
prev = 0
for (ai, bi) in Q:
	if prev < ai:
		ans += 1
		prev = bi - 1
print(ans)


from operator import itemgetter
(N, M) = map(int, input().split())
ab = [[int(i) for i in input().split()] for j in range(M)]
ab = sorted(ab, key=itemgetter(1))
ans = 0
k = 0
for i in ab:
	if i[0] > k:
		k = i[1] - 1
		ans += 1
print(ans)


(N, M) = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(M)]
l.sort(key=lambda x: x[1])
removed = 0
ans = 0
for i in l:
	s = i[1]
	if removed < i[0]:
		removed = s - 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])
c = 0
brid = -1
for (a, b) in ab:
	if a > brid:
		c += 1
		brid = b - 1
print(c)


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


(N, M, *AB) = map(int, open(0).read().split())
L = [(a, b) for (a, b) in zip(*[iter(AB)] * 2)]
L.sort(key=lambda t: t[1])
ans = end = 0
for (a, b) in L:
	if a >= end:
		end = b
		ans += 1
print(ans)


(N, M) = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(M)]
AB.sort(key=lambda ab: (ab[1], ab[0]))
ans = 0
pre = 0
for (a, b) in AB:
	if pre <= a:
		pre = b
		ans += 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)


(_, n) = map(int, input().split())
itv = []
for i in range(n):
	(a, b) = map(int, input().split())
	itv.append([b, a])
itv.sort()
(ans, x) = (0, 0)
for [b, a] in itv:
	if a > x:
		ans += 1
		x = b - 1
print(ans)


(N, M) = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(M)]
ab.sort(key=lambda x: x[1])
now = 0
ans = 0
for i in range(M):
	if now <= ab[i][0]:
		now = ab[i][1]
		ans += 1
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 = []
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))


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)

def __starting_point():
	resolve()
__starting_point()


(n, m) = map(int, input().split())
x = sorted((tuple(map(int, input().split()))[::-1] for _ in range(m)))
r = p = 0
for (b, a) in x:
	if p <= a:
		r += 1
		p = b
print(r)


(n, m) = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(m)]
ab.sort()
ans = 0
div = (-1, -1)
for i in range(len(ab)):
	(a, b) = ab[i]
	if a == div[0]:
		continue
	elif a >= div[1]:
		div = (a, b)
		ans += 1
	else:
		div = (a, min(b, div[1]))
print(ans)


(n, m) = map(int, input().split())
A = sorted([[int(i) for i in input().split()] for i in range(m)], key=lambda x: x[1])
cnt = 0
posi = 0
for (s, g) in A:
	if s >= posi:
		posi = g
		cnt += 1
print(cnt)


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


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


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


(N, M) = map(int, input().split())
A = sorted([list(map(int, input().split())) for _ in range(M)], key=lambda x: x[1])
cnt = 1
cur = A[0][1]
for i in range(1, M):
	if A[i][0] < cur:
		continue
	cur = A[i][1]
	cnt += 1
print(cnt)


(N, M) = map(int, input().split())
B = [list(map(int, input().split())) for i in range(M)]
A = sorted(B, key=lambda x: x[1])
ans = 0
removed = -1
for i in range(M):
	if A[i][0] > removed:
		ans += 1
		removed = A[i][1] - 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) = 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)


(n, m) = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(m)]
AB = sorted(AB, key=lambda x: x[1])
(cnt, cut) = (0, 0)
for (a, b) in AB:
	if cut <= a:
		cnt += 1
		cut = b
print(cnt)


(N, M) = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
AB.sort()
ar = N + 1
ans = 0
for i in reversed(range(M)):
	(a, b) = AB[i]
	if b <= ar:
		ans += 1
		ar = a
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())
H = [list(map(int, input().split())) for _ in range(M)]
H.sort(key=lambda x: x[1])
b = H[0][1]
ans = 1
for i in range(M):
	if H[i][0] >= b:
		ans += 1
		b = H[i][1]
print(ans)


(n, m) = map(int, input().split())
spans = sorted([list(map(int, input().split())) for _ in range(m)], key=lambda x: x[1])
cnt = 0
x = 0
for span in spans:
	if span[0] > x:
		x = span[1] - 1
		cnt += 1
print(cnt)


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


(N, M) = map(int, input().split())
H = [list(map(int, input().split())) for _ in range(M)]
H.sort()
a = H[-1][0]
s = 1
for i in range(M - 2, -1, -1):
	if H[i][1] <= a:
		s += 1
		a = H[i][0]
print(s)


(n, m) = map(int, input().split())
ab = [[0] * 2 for _ in range(m)]
for i in range(m):
	(a, b) = map(int, input().split())
	(ab[i][0], ab[i][1]) = (b, a)
ab.sort()
cnt = 0
chk = 0
for (b, a) in ab:
	if chk <= a:
		cnt += 1
		chk = 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)
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(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())
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)


(N, M) = map(int, input().split())
Y = [list(map(int, input().split())) for i in range(M)]
Y.sort(key=lambda x: x[1])
K = 1
x = Y[0][1]
for (a, b) in Y[1:]:
	if a + 1 > x:
		x = b
		K += 1
print(K)


(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())
AB = [list(map(int, input().split())) for _ in [0] * m]
AB.sort(key=lambda x: x[1])
l = -1
ans = 0
for i in range(m):
	if AB[i][0] > l:
		ans += 1
		l = AB[i][1] - 1
print(ans)


(N, M) = map(int, input().split())
AB = sorted([list(map(int, input().split())) for i in range(M)], key=lambda x: x[1])
hasi = 0
count = 0
for (a, b) in AB:
	if a >= hasi:
		hasi = b
		count += 1
print(count)


(n, m) = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
ab.sort(key=lambda x: x[1])
cnt = 0
x = -1
for i in range(m):
	if x < ab[i][0]:
		x = ab[i][1] - 1
		cnt += 1
print(cnt)


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)


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


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


(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) = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
ab.sort(key=lambda x: x[1])
drop = -1
ans = 0
for tmp in ab:
	(a, b) = tmp
	if a < drop:
		continue
	ans += 1
	drop = b
print(ans)


(n, m) = map(int, input().split())
l = [0] * m
for i in range(m):
	(a, b) = map(int, input().split())
	l[i] = [b, a]
l.sort()
ans = 0
x = 0
for i in range(m):
	if x < l[i][1]:
		ans += 1
		x = l[i][0] - 1
print(ans)


(n, m) = map(int, input().split())
p = []
for i in range(m):
	(r, l) = map(int, input().split())
	p.append((r, l))
p.sort()
mr = 0
c = 0
for (l, r) in p:
	if l >= mr:
		mr = r
		c += 1
		continue
	mr = min(mr, r)
print(c)


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


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


(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 = 0
m = 0
for ab in AB:
	if not ab[0] < m <= ab[1]:
		m = ab[1]
		ans += 1
print(ans)


(n, m) = list(map(int, input().split()))
M = [list(map(int, input().split())) for _ in range(m)]
M.sort(key=lambda X: X[1])
(end, ans) = (0, 0)
for (a, b) in M:
	if a >= end:
		ans += 1
		end = b
print(ans)


(n, m) = map(int, input().split())
qp = [tuple(map(int, input().split())) for _ in range(m)]
qp.sort(key=lambda x: x[1])
ans = 0
pre = 0
while qp:
	(a, b) = qp.pop(0)
	if pre < a:
		ans += 1
		pre = b - 1
print(ans)


(a, b) = map(int, input().split())
List = []
for i in range(b):
	(p, q) = map(int, input().split())
	List.append([p, q])
List = sorted(List, key=lambda x: x[1])
ans = 0
l = 1
for i in range(b):
	if List[i][0] >= l:
		ans += 1
		l = List[i][1]
print(ans)


(n, m) = map(int, input().split())
youbou = [list(map(int, input().split())) for i in range(m)]
youbou.sort(key=lambda x: x[1])
(ans, prev) = (0, -1)
for i in range(m):
	if prev < youbou[i][0]:
		prev = youbou[i][1] - 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) = map(int, input().split())
itv = []
for i in range(m):
	(a, b) = map(int, input().split())
	itv += [(b, a)]
itv = sorted(itv)
cnt = 0
l = 1
for (t, s) in itv:
	if l <= s:
		l = t
		cnt += 1
print(cnt)


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


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


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


(n, m) = map(int, input().split())
lrs = [[int(x) for x in input().split()] for _ in range(m)]
lrs.sort()
ans = 0
m = -1
for (l, r) in lrs:
	if r < m:
		m = r
	if l >= m:
		ans += 1
		m = r
print(ans)


(n, m) = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab.sort(key=lambda x: x[1])
c = 0
d = 0
for t in ab:
	if d < t[0]:
		c += 1
		d = t[1] - 1
print(c)


from operator import itemgetter
(n, m) = map(int, input().split())
ab = sorted([list(map(int, input().split())) for i in range(m)], key=itemgetter(1, 0))
end = 1
ans = 0
for (s, e) in ab:
	if s >= end:
		ans += 1
		end = e
print(ans)


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)


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


(n, m) = map(int, input().split())
data = [list(map(int, input().split())) for i in range(m)]
data.sort(key=lambda x: x[1])
idx = ans = 0
for x in data:
	if x[0] >= idx:
		idx = x[1]
		ans += 1
print(ans)


(n, m) = map(int, input().split())
data = sorted([tuple(map(int, input().split())) for i in range(m)], reverse=True)
ans = 0
last = -1
for d in data:
	if d[0] <= last < d[1]:
		pass
	else:
		ans += 1
		last = d[0]
print(ans)


(n, m, *t) = map(int, open(0).read().split())
r = [n + 1] * (n + 1)
for (a, b) in zip(*[iter(t)] * 2):
	r[a] = min(r[a], b)
a = 0
cur = n + 1
for i in range(n + 1):
	cur = min(cur, r[i])
	if i == cur:
		cur = r[i]
		a += 1
print(a)


import sys
import math
import collections
import bisect
import copy
sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7
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()])

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


(n, m) = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(m)]
AB.sort(key=lambda x: x[0])
x = n
l = 0
for (a, b) in reversed(AB):
	if b > x:
		continue
	else:
		x = a
		l += 1
print(l)


(N, M) = map(int, input().split())
koe = []
for i in range(M):
	(a, b) = map(int, input().split())
	koe.append([a, b])
koe.sort(key=lambda x: x[1])
right = 0
answer = 0
for (l, r) in koe:
	if l >= right:
		right = r
		answer += 1
print(answer)


(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
for (a, b) in AB:
	if a <= last_b:
		continue
	else:
		last_b = b - 1
		cnt += 1
print(cnt)


m = lambda : map(int, input().split())
(N, M) = m()
l = [tuple(m()) for _ in range(M)]
ans = []
l.sort(key=lambda x: x[1])
for i in range(M):
	if not ans or ans[-1] < l[i][0]:
		ans.append(l[i][1] - 1)
print(len(ans))


(N, M) = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(M)]
A.sort(key=lambda a: a[1])
last = -1
ans = 0
for a in A:
	if last < a[0]:
		last = a[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], x[0]))
ans = 0
rb = -1
for (a, b) in AB:
	if a > rb:
		ans += 1
		rb = b - 1
print(ans)


(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[1])
cut = -1
ct = 0
for (a, b) in ab:
	if a <= cut:
		continue
	else:
		cut = b - 1
		ct += 1
print(ct)


(N, M) = map(int, input().split())
c = [list(map(int, input().split())) for i in range(M)]
c.sort()
r = 0
bridge = N
for i in range(M):
	(a, b) = c[M - 1 - i]
	if a > bridge or bridge >= b:
		r += 1
		bridge = a
print(r)


(n, m) = map(int, input().split())
w = [list(map(int, input().split())) for _ in range(m)]
w.sort(key=lambda x: x[1])
f = -float('inf')
ans = 0
for (p, q) in w:
	if p >= f:
		ans += 1
		f = q
print(ans)


(n, m) = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(m)]
ab.sort(key=lambda x: x[1])
ans = 0
now = -1
for (s, e) in ab:
	if now <= s:
		ans += 1
		now = e
print(ans)


(n, m) = map(int, input().split())
l = []
for i in range(m):
	(a, b) = map(int, input().split())
	l.append((b, a))
l.sort()
answer = 0
last = 0
for (b, a) in l:
	if a >= last:
		answer += 1
		last = b
print(answer)


(n, m) = map(int, input().split())
lis = [list(map(int, input().split())) for i in range(m)]
lis.sort(key=lambda x: x[1])
ans = 0
cou = 0
for (num, nu) in lis:
	if cou <= num:
		ans += 1
		cou = nu
print(ans)


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


(N, M) = map(int, input().split())
ab = []
for i in range(M):
	ab.append(list(map(int, input().split())))
ab.sort(key=lambda ab: ab[1])
count = 0
now = 0
for (a, b) in ab:
	if a >= now:
		count += 1
		now = b
print(count)


(n, m) = map(int, input().split())
a = [list(map(int, input().split())) for i in range(m)]
a.sort()
end = n
ans = 0
for i in range(m):
	if a[i][0] >= end:
		ans += 1
		end = n
	end = min(a[i][1], end)
print(ans + 1)


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


(n, m) = list(map(int, input().split()))
l = [list(map(int, input().split())) for _ in range(m)]
l = sorted(l, key=lambda x: x[1])
bmax = 0
ans = 0
for (a, b) in l:
	if bmax > a:
		continue
	bmax = b
	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])
count = 0
x = 0
for (a_i, b_i) in ab:
	if a_i <= x < b_i:
		continue
	x = b_i - 1
	count += 1
print(count)


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


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)


(n, m) = map(int, input().split())
a = sorted([list(map(int, input().split())) for i in range(m)], key=lambda x: x[1])
x = 0
d = 0
for i in a:
	if i[0] > x:
		x = i[1] - 1
		d += 1
print(d)


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


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


(N, M) = map(int, input().split())
Q = [tuple(map(int, input().split())) for _ in range(M)]
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) = map(int, input().split())
Ai = [list(map(int, input().split())) for _ in range(M)]
Ai.sort(key=lambda x: x[1])
count = 0
left = 0
for a in Ai:
	if a[0] >= left:
		left = a[1]
		count += 1
print(count)


(N, M) = map(int, input().split())
s = [list(map(int, input().split())) for i in range(M)]
s.sort(key=lambda x: x[1])
count = 1
mae = s[0][1]
for i in range(1, M):
	if s[i][0] >= mae:
		count += 1
		mae = s[i][1]
print(count)


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


(n, m) = [int(_) for _ in input().split()]
spam = [[int(_) for _ in input().split()] for _ in range(m)]
spam.sort(key=lambda x: x[1])
pre = -1
cnt = 0
for (a, b) in spam:
	if pre < a:
		cnt += 1
		pre = b - 1
print(cnt)


(N, M) = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(M)]
A.sort(key=lambda x: x[1])
ans = 1
end = A[0][1]
for i in range(1, M):
	if A[i][0] >= end:
		ans += 1
		end = A[i][1]
print(ans)


(n, m) = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(m)]
l.sort()
l = l[::-1]
cnt = 1
key = l[0][0]
for i in range(1, m):
	if key >= l[i][1]:
		cnt += 1
		key = l[i][0]
print(cnt)


def resolve():
	import sys
	from operator import itemgetter
	readline = sys.stdin.readline
	(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()


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


(N, M) = map(int, input().split())
bs = [tuple(map(int, input().split())) for _ in range(M)]
bs.sort(key=lambda x: x[1])
rbs = []
for (a, b) in bs:
	if not rbs or a > rbs[-1]:
		rbs.append(b - 1)
ans = len(rbs)
print(ans)


(N, M) = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
ans = 0
ab = sorted(ab, key=lambda x: x[1])
n = 0
for i in range(M):
	if ab[i][0] >= n:
		n = ab[i][1]
		ans += 1
print(ans)


(a, m) = map(int, input().split())
hl = [tuple(map(int, input().split())) for i in range(m)]
hl.sort()
(l, r) = (-1, a + 1)
c = 0
for i in hl:
	l = i[0]
	r = min(r, i[1])
	if l >= r:
		c += 1
		r = i[1]
print(c + 1)


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


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


(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())
count = 0
t = 0
base = [list(map(int, input().split())) for i in range(m)]
base.sort(key=lambda x: x[1])
for temp in base:
	if t <= temp[0]:
		count = count + 1
		t = temp[1]
print(count)


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


(N, M) = map(int, input().split())
d = [list(map(int, input().split())) for _ in range(M)]
d.sort(key=lambda x: x[1])
ans = 0
c = 0
for i in range(M):
	(a, b) = d[i]
	if a >= c:
		ans += 1
		c = b
print(ans)


(N, M) = map(int, input().split())
Q = [list(map(int, input().split())) for _ in range(M)]
Q.sort(key=lambda x: (x[1], x[0]))
b = 0
res = 0
for i in range(M):
	if Q[i][0] >= b:
		b = Q[i][1]
		res += 1
print(res)


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


def solve():
	(n, m, *t) = map(int, open(0).read().split())
	r = sorted([(b, a) for (a, b) in zip(*[iter(t)] * 2)])
	c = bef = 0
	for (b, a) in r:
		if a > bef:
			c += 1
			bef = b - 1
	print(c)
solve()


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


(n, m) = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(m)]
A.sort(key=lambda a: a[1])
ans = 0
last = 0
for (a, b) in A:
	if a >= last:
		ans += 1
		last = b
print(ans)


(n, m) = map(int, input().split())
a = sorted([tuple(map(int, input().split())) for _ in range(m)], key=lambda x: x[1])
(cut, ans) = (0, 0)
for (l, r) in a:
	if l >= cut:
		ans += 1
		cut = r
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())


(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, *t) = map(int, open(0).read().split())
c = d = 0
for (b, a) in sorted([(b, a) for (a, b) in zip(*[iter(t)] * 2)]):
	if a > d:
		c += 1
		d = b - 1
print(c)


(N, M) = map(int, input().split())
lst = [list(map(int, input().split())) for _ in range(M)]
lst.sort(key=lambda x: x[1])
div = 0
cnt = 0
for (a, b) in lst:
	if a > div:
		div = b - 1
		cnt += 1
print(cnt)


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


(n, m) = map(int, input().split())
ab = sorted([tuple(map(int, input().split())) for _ in range(m)], key=lambda x: x[1])
broken = -1
ans = 0
for (a, b) in ab:
	if broken < a:
		broken = b - 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())
ab = [tuple(map(int, input().split())) for _ in range(m)]
ab.sort(key=lambda x: x[1])
ans = 0
right = -1
for (a, b) in ab:
	if a < right:
		continue
	ans += 1
	right = b
print(ans)


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


(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) = map(int, input().split())
ab = []
for i in range(m):
	(a, b) = map(int, input().split())
	ab.append([a, b])
ab = sorted(ab, key=lambda x: x[1])
mn = ab[0][1]
c = 1
for i in ab:
	if i[0] >= mn:
		c += 1
		mn = i[1]
print(c)


(n, m) = map(int, input().split())
ts = [list(map(int, input().split()))[::-1] for j in range(m)]
ts.sort()
count = 0
t = 0
for j in range(m):
	if ts[j][1] >= t:
		count += 1
		t = ts[j][0]
print(count)


(n, m) = map(int, input().split())
x = [-1] * (n + 1)
for _ in range(m):
	(a, b) = map(int, input().split())
	x[b] = max(x[b], a)
ans = 0
bmx = 0
for i in range(n + 1):
	if bmx <= x[i]:
		ans += 1
		bmx = i
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)


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)


(N, M) = list(map(int, input().split()))
req = [list(map(int, input().split())) for i in range(M)]
req.sort(key=lambda x: x[1])
left = 0
cnt = 0
for i in range(M):
	if left <= req[i][0]:
		cnt += 1
		left = req[i][1]
print(cnt)


(n, m) = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(m)]
AB.sort(reverse=1)
res_L = float('inf')
ans = 0
for (a, b) in AB:
	cur_R = b
	if cur_R <= res_L:
		res_L = a
		ans += 1
print(ans)


(n, m) = map(int, input().split())
l = [tuple(map(int, input().split())) for _ in range(m)]
l.sort(key=lambda x: x[1])
dec = 0
cur = 0
for i in l:
	if i[0] < cur <= i[1]:
		continue
	else:
		dec += 1
		cur = i[1]
print(dec)


(n, m) = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(m)]
a = sorted(a, key=lambda x: x[1])
ans = [0]
for a_ in a:
	if not a_[0] < ans[-1] <= a_[1]:
		ans.append(a_[1])
print(len(ans) - 1)


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


(N, M) = map(int, input().split())
ts = [list(map(int, input().split()))[::-1] for i in range(M)]
ts.sort()
count = 0
tmp = 0
for i in ts:
	if i[1] >= tmp:
		count += 1
		tmp = i[0]
print(count)


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


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)


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


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


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


(n, m) = map(int, input().split())
q = [None] * m
for i in range(m):
	(a, b) = map(int, input().split())
	q[i] = [a, b]
q = sorted(q, key=lambda x: x[1])
cut = -1
ans = 0
for i in range(m):
	if q[i][0] >= cut:
		ans += 1
		cut = q[i][1]
print(ans)


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


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) = map(int, input().split())
d = sorted([[int(x) for x in input().split()] for y in range(m)], key=lambda x: x[1])
(c, e) = (0, 0)
for i in range(m):
	if d[i][0] > e:
		e = d[i][1] - 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()
x = -1
ans = 0
for i in range(m):
	if c[i][1] > x:
		x = c[i][0] - 1
		ans += 1
print(ans)


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


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) = map(int, input().split())
War = [[int(i) for i in input().split()] for i in range(M)]
War.sort(key=lambda x: x[1])
cut = 0
ans = 0
for i in range(M):
	if War[i][0] >= cut:
		ans += 1
		cut = War[i][1]
print(ans)


def get_input() -> 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:
	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) = map(int, input().split())
A = [[int(a) for a in input().split()] for _ in range(M)]
A.sort(key=lambda a: a[1])
s = -1
ans = 0
for (a, b) in A:
	if a > s:
		ans += 1
		s = b - 1
print(ans)


from operator import itemgetter
(N, M) = map(int, input().split())
AB = sorted([list(map(int, input().split())) for _ in range(M)], key=itemgetter(1))
(x, ans) = (AB[0][1], 1)
for (a, b) in AB:
	if a >= x:
		x = b
		ans += 1
print(ans)


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


(N, M) = map(int, input().split())
x = [list(map(int, input().split())) for i in range(M)]
x.sort(key=lambda x: x[1])
(ans, m) = (0, 0)
for (a, b) in x:
	if a >= m:
		ans += 1
		m = b
print(ans)


(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:
	if last < l[0]:
		ans += 1
		last = l[1] - 1
print(ans)


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
	if ab[1] > ab[0]:
		heapq.heappush(q, [ab[1], ab[0]])
		cnt += 1
	elif visited <= ab[1]:
		visited = ab[0]
		ans += 1
	else:
		pass
print(ans)


(N, M) = map(int, input().split())
Requests = sorted([list(map(int, input().split())) for i in range(M)], key=lambda x: x[1])
(cut, ans) = (0, 0)
for (l, r) in Requests:
	if l >= cut:
		ans += 1
		cut = r
print(ans)


(n, m) = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab.sort(key=lambda ab: ab[1])
ans = [ab[0]]
for i in range(1, m):
	if ans[-1][1] <= ab[i][0]:
		ans.append(ab[i])
print(len(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)


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) = map(int, input().split())
box = [list(map(int, input().split())) for i in range(m)]
box = sorted(box, key=lambda x: x[1])
(count, cut) = (0, 0)
for (x, y) in box:
	if cut <= x:
		count += 1
		cut = y
print(count)


(n, m) = map(int, input().split())
a = [tuple(map(int, input().split())) for i in range(m)]
a.sort()
(l, r) = (0, n + 1)
x = 1
for (i, j) in a:
	if j <= l or r <= i:
		x += 1
		(l, r) = (i, j)
	else:
		(l, r) = (max(l, i), min(r, j))
print(x)


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


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


(N, M) = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(M)]
AB.sort(key=lambda x: x[1])
num = 0
p = 0
for i in AB:
	if i[0] >= p:
		num += 1
		p = i[1]
print(num)


(n, m) = map(int, input().split())
st = [list(map(int, input().split())) for _ in [0] * m]
st.sort(key=lambda x: (x[1], x[0]))
(now, cnt) = (0, 0)
for (s, t) in st:
	if now <= s:
		cnt += 1
		now = t
print(cnt)


(n, m) = map(int, input().split())
war = [tuple(map(int, input().split())) for _ in range(m)]
war.sort(key=lambda x: x[1])
ans = 0
tmp = -1
for (l, r) in war:
	if tmp <= l:
		ans += 1
		tmp = r
print(ans)


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


(n, m) = map(int, input().split())
l = [list(map(int, input().split())) for i in range(m)]
for i in l:
	(i[0], i[1]) = (i[1], i[0])
ll = sorted(l)
(x, cnt) = (ll[0][0], 1)
for i in ll:
	a = i[1]
	b = i[0]
	if a >= x:
		cnt += 1
		x = b
print(cnt)


(N, M) = map(int, input().split())
B = sorted([list(map(int, input().split())) for k in range(M)], key=lambda x: x[1])
now = -1
ans = 0
for e in B:
	if now <= e[0]:
		ans += 1
		now = e[1]
print(ans)


(n, m) = map(int, input().split())
ab = [[int(i) for i in input().split()] for _ in range(m)]
ab.sort(key=lambda x: x[1])
ans = 0
r = -1
for (a, b) in ab:
	if a >= r:
		ans += 1
		r = b
print(ans)


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


(n, m) = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab.sort()
(l, r) = ab[0]
ans = 1
for (i, j) in ab[1:]:
	if j <= l or r <= i:
		ans += 1
		(l, r) = (i, j)
	l = max(l, i)
	r = min(r, j)
print(ans)


(N, M) = map(int, input().split())
table = []
ans = 1
for i in range(M):
	(a, b) = map(int, input().split())
	table.append((a, b))
table.sort()
r = N
for (a, b) in table:
	if r <= a:
		ans += 1
		r = N
	r = min(b, r)
print(ans)


(N, M) = map(int, input().split())
ls = [tuple(map(int, input().split())) for _ in range(M)]
ls.sort(key=lambda x: x[1])
l = 0
ans = 0
for (a, b) in ls:
	if l <= a:
		l = b
		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])
cnt = 0
end_time = 0
for (a, b) in ab:
	if end_time <= a:
		end_time = b
		cnt += 1
print(cnt)


(N, M) = map(int, input().split())
ab = [tuple(map(int, input().split())) for i in range(M)]
ab.sort()
l = 1
r = N
ans = 1
for (a, b) in ab:
	l = max(a, l)
	r = min(b, r)
	if l >= r:
		ans += 1
		l = a
		r = b
print(ans)


(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
endplace = 0
for (ai, bi) in ab:
	if endplace <= ai:
		endplace = bi
		ans += 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())
ba = []
for i in range(M):
	(a, b) = map(int, input().split())
	ba.append((b, a))
ba.sort()
ans = 0
last = 0
for (b, a) in ba:
	if a >= last:
		ans += 1
		last = b
print(ans)


(n, m) = map(int, input().split())
line = [list(map(int, input().split())) for _ in range(m)]
line.sort(key=lambda x: x[1])
ans = 1
now = line[0][1]
for (s, g) in line[1:]:
	if s >= now:
		ans += 1
		now = g
print(ans)


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


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