Given a set of $n$ intervals, find the size of its largest possible subset of intervals such that no three intervals in the subset share a common point.

Input Format

The first line contains an integer, $\boldsymbol{\mathrm{~S~}}$, denoting the number of interval sets you must find answers for. The $s\cdot(n+1)$ subsequent lines describe each of the $\boldsymbol{\mathrm{~S~}}$ interval sets as follows:

The first line contains an integer, $n$, denoting the number of intervals in the list. 
Each line $\boldsymbol{i}$ of the $n$ subsequent lines contains two space-separated integers describing the respective starting ($a_i$) and ending ($b_i$) boundaries of an interval.

Constraints

$1\leq s\leq100$
$2\leq n\leq1000$  
$1\leq a_i\leq b_i\leq10^9$

Output Format

For each of the $\boldsymbol{\mathrm{~S~}}$ interval sets, print an integer denoting the size of the largest possible subset of intervals in the given set such that no three points in the subset overlap.

Sample Input
4
3
1 2
2 3
2 4
3
1 5
1 5
1 5
4
1 10
1 3
4 6
7 10
4
1 10
1 3
3 6
7 10

Sample Output
2
2
4
3

Explanation

For set $\boldsymbol{s_{0}}$, all three intervals fall on point $2$ so we can only choose any $2$ of the intervals. Thus, we print $2$ on a new line.

For set $\boldsymbol{S_{1}}$, all three intervals span the range from $\mbox{1}$ to $5$ so we can only choose any $2$ of them. Thus, we print $2$ on a new line.

For set $s_2$, we can choose all $\begin{array}{c}4\end{array}$ intervals without having more than two of them overlap at any given point. Thus, we print $\begin{array}{c}4\end{array}$ on a new line.

For set $s_3$, the intervals $[1,10]$, $[1,3]$, and $[3,6]$ all overlap at point $3$, so we must only choose $2$ of these intervals to combine with the last interval, $[7,10]$, for a total of $3$ qualifying intervals. Thus, we print $3$ on a new line.

Source: hackerrank | Difficulty: MEDIUM
Tags: Dynamic programming


Solutions:
import sys

def readnums():
	return [int(x) for x in sys.stdin.readline().strip().split(' ')]
for i in range(readnums()[0]):
	intervals = []
	for j in range(readnums()[0]):
		intervals.append(readnums())
	intervals.sort()
	selected = []
	num_selected = 0
	while intervals:
		selected.append(intervals.pop())
		num_selected += 1
		if num_selected >= 2:
			if selected[-2][0] <= selected[-1][1]:
				overlap_int = [selected[-2][0], selected[-1][1]]
				intervals = list(filter(lambda interval: interval[1] < overlap_int[0], intervals))
	print(num_selected)


t = int(input())
for _ in range(t):
	n = int(input())
	I = []
	for _ in range(n):
		(a, b) = list(map(int, input().split()))
		I.append((a, b))
	I.sort(key=lambda x: (x[1], x[0]))
	temp = -1
	lasta = 0
	lastb = 0
	res = 0
	for (a, b) in I:
		if a > lastb:
			res += 1
			lasta = a
			lastb = b
		elif a > temp:
			res += 1
			temp = lastb
			lasta = a
			lastb = b
	print(res)


t = int(input().strip())
for t_idx in range(t):
	n_events = int(input().strip())
	event_times = []
	for event_idx in range(n_events):
		event_times_parse = [int(a) for a in input().strip().split(' ')]
		event_times.append((event_times_parse[0], event_times_parse[1]))
	event_times.sort()
	I = []
	num_events = 0
	depth_limit = 2
	for (s, f) in event_times:
		I = [(s_i, f_i) for (s_i, f_i) in I if f_i >= s]
		I.append((s, f))
		if len(I) > depth_limit:
			I.sort(key=lambda x: x[1])
			I.pop()
		else:
			num_events = num_events + 1
	print(num_events)


def do(ints):
	ints = sorted(ints)
	over = []
	res = []
	for (i, (s, e)) in enumerate(ints):
		res.append((s, e))
		if i >= 2:
			over = []
			for j in range(len(res)):
				if res[j][1] >= s:
					over.append((res[j][1], j))
			if len(over) >= 3:
				(_, j) = sorted(over)[-1]
				res.pop(j)
	return len(res)
T = int(input())
for t in range(T):
	N = int(input())
	intervals = [input().split() for n in range(N)]
	intervals = [(int(s), int(e)) for (s, e) in intervals]
	print(do(intervals))


def SolveIt(N, iArr):
	iArr.sort(key=lambda x: (x[1], x[0]))
	fArr = [iArr[i][1] for i in range(N)]
	Flag = [1 for i in range(N)]
	for i in range(N):
		count = 0
		for j in range(N):
			if Flag[j]:
				if iArr[j][0] <= fArr[i] and iArr[j][1] >= fArr[i]:
					count += 1
					if count > 2:
						Flag[j] = 0
	return sum(Flag)
T = int(input())
for _ in range(T):
	N = int(input())
	iArr = [tuple(map(int, input().split())) for i in range(N)]
	print(SolveIt(N, iArr))


def possibleSubsets():
	N = int(input())
	l = []
	max = 0
	current = 0
	count = 0
	for j in range(0, N):
		interval = input()
		(a, b) = [int(x) for x in interval.split(' ')]
		l.append([a, b])
		l = sorted(l, key=lambda s: s[1])
	for (i, j) in l:
		if i > max:
			count += 1
			if i <= current:
				max = current
			current = j
	return count
testCases = int(input())
for i in range(testCases):
	count = possibleSubsets()
	print(count)


def solve():
	n = input()
	nums = []
	for k in range(0, int(n)):
		line = input().split(' ')
		a = int(line[0])
		b = int(line[1])
		nums.append((b, a))
	nums.sort()
	(ans, maxright, nextright) = (0, 0, 0)
	for (right, left) in nums:
		if left > maxright:
			ans += 1
			if left <= nextright:
				maxright = nextright
			nextright = right
	print(ans)
t = input()
for i in range(0, int(t)):
	solve()


import re
import collections
s = int(input())
for s_ in range(s):
	n = int(input())
	endpoints = set()
	intervals = []
	for n_ in range(n):
		(a, b) = [int(x) for x in input().split()]
		endpoints.add(a)
		endpoints.add(b)
		intervals.append((a, b))
	intervals.sort(key=lambda x: (x[1], -x[0]))
	doubleend = -1
	singleend = -1
	num = 0
	for (start, end) in intervals:
		if start <= doubleend:
			continue
		if start <= singleend:
			doubleend = singleend
		singleend = end
		num += 1
	print(num)


Q = int(input().strip())

def intersect(t1, t2):
	if t1 == None or t2 == None:
		return False
	return t1[1] >= t2[0] and t2[1] >= t1[0]
for q in range(Q):
	N = int(input().strip())
	intervals = []
	for n in range(N):
		arr = [int(i) for i in input().strip().split()]
		tup = (arr[0], arr[1])
		intervals.append(tup)
	intervals = sorted(intervals, key=lambda x: x[0])
	intervals = sorted(intervals, key=lambda x: x[1])
	result = [intervals[0]]
	last = None
	i = 1
	while i < len(intervals):
		current_interval = intervals[i]
		last_intersection = result[last] if last != None else None
		if not intersect(last_intersection, current_interval):
			result.append(current_interval)
			start = last if last != None else -1
			for j in range(len(result) - 2, start, -1):
				interval = result[j]
				if intersect(interval, current_interval):
					last = j
					break
		i += 1
	print(len(result))


from operator import itemgetter
for _ in range(int(input())):
	(result, currEnd, intervals) = (0, 0, [])
	for (start, end) in sorted((tuple(map(int, input().split())) for __ in range(int(input())))):
		intervals = [inter for inter in intervals if inter[1] >= start] + [(start, end)]
		if len(intervals) < 3:
			result += 1
		else:
			intervals.remove(max(intervals, key=itemgetter(1)))
	print(result)


import operator

class Set:

	def __init__(self, e):
		self.start = int(e[0])
		self.end = int(e[1])

def find_soln(l):
	max_count = 0
	cur = []
	cur.append(l[0])
	for i in range(1, len(l)):
		c = 0
		rem = l[i]
		for el in cur:
			if l[i].start <= el.end:
				c += 1
				if rem.end <= el.end:
					rem = el
		if c == 2:
			if rem != l[i]:
				cur.remove(rem)
				cur.append(l[i])
		else:
			cur.append(l[i])
		max_count = max(max_count, len(cur))
	return max_count
s = int(input())
for i in range(0, s):
	n = int(input())
	h = []
	for j in range(0, n):
		e = input().split()
		h.append(Set(e))
	h.sort(key=operator.attrgetter('start'))
	print(find_soln(h))


t = int(input())
while t != 0:
	n = int(input())
	l = []
	d = dict()
	for i in range(n):
		str = input().split()
		x1 = int(str[0])
		x2 = int(str[1])
		l.append([x1, x2])
	l.sort(key=lambda x: (x[1], x[0]))
	res = 2
	last_index_0 = 0
	last_index_1 = 1
	intersect = 0
	if l[1][0] <= l[0][1]:
		intersect = 1
	v = [[last_index_0, intersect], [last_index_1, 0]]
	for i in range(2, n):
		if l[i][0] > l[v[len(v) - 1][0]][1]:
			res += 1
			v.append([i, 0])
		else:
			include = True
			for j in range(len(v) - 2, -1, -1):
				if l[i][0] <= l[v[j][0]][1] and v[j][1] == 1:
					include = False
					break
				elif l[i][0] > l[v[j][0]][1]:
					break
			if include == True:
				v[len(v) - 1][1] = 1
				v.append([i, 0])
	print(len(v))
	t -= 1


Q = int(input())
for i in range(Q):
	n = int(input())
	A = []
	for i in range(n):
		A += [list(map(int, input().strip().split(' ')))]
	A = sorted(A)
	A.reverse()
	max1 = 10 ** 9 + 1
	max2 = 10 ** 9 + 1
	temp = 0
	for i in range(len(A)):
		[x, y] = A[i]
		if y < max2:
			temp += 1
			if y >= max1:
				max2 = max1
				max1 = x
			else:
				max1 = x
	print(temp)


def remove_non_intersecting_intervals(subset, interval):
	subset[:] = [ele for ele in subset if ele[1] >= interval[0]]

def run():
	num_interval_sets = int(input().strip())
	while num_interval_sets > 0:
		num_intervals = int(input().strip())
		intervals = []
		for i in range(0, num_intervals):
			intervals.append([int(val) for val in input().strip().split(' ')])
		intervals = sorted(intervals, key=lambda point: point[0])
		num_interval_subset = 0
		track_subset = []
		for interval in intervals:
			remove_non_intersecting_intervals(track_subset, interval)
			track_subset.append(interval)
			subset_length = len(track_subset)
			if subset_length <= 2:
				num_interval_subset += 1
			else:
				ctr = 0
				index_longest = 0
				longest = track_subset[0]
				for tracked in track_subset:
					if tracked[1] > longest[1]:
						index_longest = ctr
						longest = tracked
					ctr += 1
				del track_subset[index_longest]
		print(num_interval_subset)
		num_interval_sets -= 1
run()


from operator import itemgetter
LEFT = 0
RIGHT = 1
num_tests = int(input())
for t in range(num_tests):
	intvls = []
	num_intvls = int(input())
	for j in range(num_intvls):
		intvl = input().split()
		intvls.append((int(intvl[LEFT]), int(intvl[RIGHT])))
	intvls.sort(key=itemgetter(1))
	lower_limit_so_far = 0
	range_inc_so_far = 0
	num_included = 0
	for i in intvls:
		if i[LEFT] > lower_limit_so_far:
			num_included = num_included + 1
			if i[LEFT] <= range_inc_so_far:
				lower_limit_so_far = range_inc_so_far
			range_inc_so_far = i[RIGHT]
	print(num_included)


import collections
s = int(input())

def intervals_overlap(i1, i2):
	if i2[0] < i1[0]:
		(i1, i2) = (i2, i1)
	return i2[0] <= i1[1]
for _ in range(s):
	n = int(input())
	I = []
	for _ in range(n):
		I.append(tuple(map(int, input().split())))
	I.sort(key=lambda i: (i[1], -i[0]))
	S = list()
	overlapping_intervals = collections.defaultdict(lambda : [])
	for p in I:
		current_is_bad = False
		current_overlaps = []
		for q in S:
			if intervals_overlap(p, q):
				current_overlaps.append(q)
			if any((intervals_overlap(p, other) for other in overlapping_intervals[q])):
				current_is_bad = True
				break
		if not current_is_bad:
			overlapping_intervals[p] = current_overlaps
			S.append(p)
	print(len(S))


def addInterval(lst, interval):
	increment = 0
	for tupl in lst:
		if tupl[1] < interval[0]:
			lst.remove(tupl)
			increment += 1
	lst.append(interval)
	return (increment, lst)

def removeLatest(lst):
	latest = -1
	interval = (0, 0)
	for tupl in lst[::-1]:
		if tupl[1] > latest:
			latest = tupl[1]
			interval = tupl
	lst.remove(interval)

def solve(lst):
	if len(lst) < 3:
		return len(lst)
	cur_lst = []
	counter = 0
	index = 0
	while index < len(lst):
		interval = lst[index]
		(increment, cur_lst) = addInterval(cur_lst, interval)
		counter += increment
		if len(cur_lst) > 2:
			removeLatest(cur_lst)
		index += 1
	if len(cur_lst) <= 2:
		counter += len(cur_lst)
	return counter
cases = int(input())
for i in range(cases):
	n = int(input())
	intervals = []
	for j in range(n):
		(s, f) = input().split(' ')
		intervals.append((int(s), int(f)))
	intervals.sort(key=lambda x: x[0])
	print(solve(intervals))


from operator import itemgetter
s = int(input().strip())
for _ in range(s):
	n = int(input().strip())
	intervals = []
	for _ in range(n):
		(a, b) = [int(x) for x in input().split()]
		intervals.append((a, b))
	if n <= 2:
		print(n)
		continue
	intervals.sort(key=itemgetter(1))
	current = (intervals[0], intervals[1])
	next_possible_start = 0 if current[1][0] > current[0][1] else current[0][1] + 1
	nb_max = 2
	for (a, b) in intervals[2:]:
		if a >= next_possible_start:
			(p, s) = current
			current = (s, (a, b))
			nb_max += 1
			next_possible_start = next_possible_start if current[1][0] > current[0][1] else current[0][1] + 1
	print(nb_max)


def solve():
	nums = []
	n = int(input())
	for x in range(n):
		(a, b) = map(int, input().split())
		nums.append((b, a))
	nums.sort()
	(ans, maxright, nextright) = (0, 0, 0)
	for (right, left) in nums:
		if left > maxright:
			ans += 1
			if left <= nextright:
				maxright = nextright
			nextright = right
	print(ans)
t = int(input())
for x in range(t):
	solve()


S = int(input())
for s in range(S):
	n = int(input())
	intervals = []
	for i in range(n):
		(a, b) = map(int, input().split())
		intervals.append((a, b))
	intervals.sort(key=lambda a: a[1])
	intervals_chosen = []
	rightmost_overlap = None
	for interval in intervals:
		if rightmost_overlap is None or interval[0] > rightmost_overlap:
			intervals_chosen.append(interval)
			if len(intervals_chosen) > 1 and intervals_chosen[-2][1] >= intervals_chosen[-1][0]:
				rightmost_overlap = intervals_chosen[-2][1]
	print(len(intervals_chosen))


def can_add(line, pair):
	if len(line) == 0:
		return True
	else:
		return line[-1][1] < pair[0]
s = int(input())
for a in range(s):
	n = int(input())
	line1 = []
	pairs = []
	result = n
	for b in range(n):
		(l, r) = map(int, input().split())
		pairs.append((l, r))
	pairs.sort(key=lambda x: x[1])
	overlaps = []
	for pair in pairs:
		if can_add(line1, pair):
			line1.append(pair)
		elif overlaps == [] or overlaps[-1] < pair[0]:
			overlaps.append(line1[-1][1])
			line1.append(pair)
		else:
			result -= 1
	print(result)


class Interval:

	def __init__(self, x, y):
		self.start = x
		self.end = y
loop = int(input())
for i in range(loop):
	nodes = int(input())
	lst = []
	count = 1
	for i in range(nodes):
		x = [int(x) for x in input().split()]
		lst.append(Interval(x[0], x[1]))
	lst = sorted(lst, key=lambda x: x.end)
	mySet = []
	end = None
	for item in lst:
		if end is None or item.start > end:
			mySet.append(item)
			if len(mySet) > 1 and mySet[-2].end >= mySet[-1].start:
				end = mySet[-2].end
	print(len(mySet))


answers = []
for _ in range(int(input())):
	intervals = []
	for interval in range(int(input())):
		intervals.append([int(i) for i in input().split()])
	intervals = sorted(intervals, key=lambda list: list[1])
	answer = 0
	overlap1 = []
	overlap2 = []
	point1 = 0
	point2 = 0
	for pair in intervals:
		if not overlap1:
			overlap1.append(pair[:])
			answer += 1
			continue
		if overlap1[point1][1] < pair[0]:
			overlap1.append(pair[:])
			point1 += 1
		elif overlap1[point1][1] >= pair[0]:
			ov2pair = [pair[0], min(overlap1[point1][1], pair[1])]
			if overlap2 and overlap2[point2][1] >= ov2pair[0]:
				continue
			if overlap1[point1][1] < pair[1]:
				overlap1[point1][1] = pair[1]
			if not overlap2:
				overlap2.append(ov2pair)
				answer += 1
				continue
			if overlap2[point2][1] < ov2pair[0]:
				overlap2.append(ov2pair)
				point2 += 1
		answer += 1
	answers.append(answer)
[print(answ) for answ in answers]


def intersect(l1, l2, l3):
	c1 = 0
	c2 = 0
	if l2[1] < l3[0]:
		return False
	elif l2[1] == l3[0]:
		c1 = l3[0]
		if c1 > l1[1]:
			return False
	else:
		c2 = l2[1]
		if l2[0] > l3[0]:
			c1 = l2[0]
		else:
			c1 = l3[0]
		if c1 > l1[1]:
			return False
	return True
s = int(input())
for i in range(0, s):
	n = int(input())
	lol = []
	for j in range(0, n):
		(a, b) = input().split()
		lol += [[int(a), int(b)]]
	lol.sort(key=lambda x: x[1])
	ans = 2
	c1 = 0
	c2 = 0
	final_list = [[-1, -1]]
	final_list += lol[0:2]
	for k in range(2, n):
		prev1 = final_list[-1]
		prev2 = final_list[-2]
		cntr = 0
		while lol[k][0] <= final_list[cntr - 1][1]:
			inter = intersect(final_list[cntr - 2], final_list[cntr - 1], lol[k])
			if inter:
				break
			else:
				cntr -= 1
		if lol[k][0] > final_list[cntr - 1][1]:
			ans += 1
			final_list += [lol[k]]
	print(ans)


for _ in range(int(input())):
	(n, rs, p1, p2) = (int(input()), 0, (0, 0), (0, 0))
	for t in sorted(map(lambda li: (int(li[1]), int(li[0])), [input().split(' ') for _ in range(n)])):
		if t[1] > p2[0]:
			(rs, p2) = (rs + 1, t)
		elif t[1] > p1[0]:
			(p1, p2, rs) = (p2, t, rs + 1)
	print(rs)


s = int(input().strip())
for _ in range(s):
	n = int(input().strip())
	a = []
	b = []
	for i in range(n):
		(ai, bi) = [int(x) for x in input().strip().split()]
		a.append(ai)
		b.append(bi)
	(a, b) = zip(*sorted(zip(a, b), key=lambda x: x[0]))
	(a, b) = (list(a), list(b))
	(res1, res2) = ((a[0], b[0]), (a[1], b[1]))
	if b[1] < b[0]:
		(res1, res2) = (res2, res1)
	count = 2
	for i in range(2, n):
		if a[i] > res1[1]:
			count += 1
			res1 = (a[i], b[i])
		elif b[i] < res2[1]:
			res2 = (a[i], b[i])
		if res2[1] < res1[1]:
			(res1, res2) = (res2, res1)
	print(count)


for _ in range(int(input())):
	N = int(input())
	L = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: x[1])
	(R, X) = (0, [[0] * 2 for _ in range(2)])
	for T in L:
		if T[0] > X[1][1]:
			(R, X[1]) = (R + 1, list(T))
		elif T[0] > X[0][1]:
			(R, X[0]) = (R + 1, list(T))
			if T[1] > X[1][1]:
				(X[0], X[1]) = (list(X[1]), list(X[0]))
	print(R)


def possibleSubsets():
	N = int(input())
	l = []
	max = 0
	current = 0
	count = 0
	for j in range(0, N):
		interval = input()
		(a, b) = [int(x) for x in interval.split(' ')]
		l.append([a, b])
		l = sorted(l, key=lambda s: s[1])
	for (i, j) in l:
		if i > max:
			count += 1
			if i <= current:
				max = current
			current = j
	return count
testCases = int(input())
for i in range(testCases):
	count = possibleSubsets()
	print(count)


class Interval:

	def __init__(self, s, e):
		self.start = s
		self.end = e

def intervalSelection(intervals):
	occupiedInterval = [Interval(0, 0), Interval(0, 0)]
	numOfInterval = 0
	intervals.sort(key=lambda x: x[1])
	for (s, e) in intervals:
		currentInterval = Interval(s, e)
		if currentInterval.start > occupiedInterval[1].end:
			numOfInterval += 1
			occupiedInterval[1] = currentInterval
		elif currentInterval.start > occupiedInterval[0].end:
			numOfInterval += 1
			occupiedInterval[0] = currentInterval
			if e > occupiedInterval[1].end:
				(occupiedInterval[0], occupiedInterval[1]) = (occupiedInterval[1], occupiedInterval[0])
	return numOfInterval
s = int(input())
for s_itr in range(s):
	n = int(input())
	intervals = []
	for _ in range(n):
		intervals.append(list(map(int, input().rstrip().split())))
	result = intervalSelection(intervals)
	print(result)


def greedy(I):
	I.sort(key=lambda lr: lr[1])
	C = []
	for (l, r) in I:
		c = 0
		S = []
		for (l0, r0) in C:
			if l <= r0:
				S.append((l0, r0))
		good = True
		for i in range(len(S) - 1):
			if S[i][1] >= S[i + 1][0]:
				good = False
		if good:
			C.append((l, r))
	return len(C)

def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		I = [tuple(map(int, input().split())) for _ in range(N)]
		print(greedy(I))
main()


t = int(input())
for _ in range(t):
	n = int(input())
	I = []
	for _ in range(n):
		(a, b) = list(map(int, input().split()))
		I.append((a, b))
	I.sort(key=lambda x: (x[1], x[0]))
	temp = -1
	lasta = 0
	lastb = 0
	res = 0
	for (a, b) in I:
		if a > lastb:
			res += 1
			lasta = a
			lastb = b
		elif a > temp:
			res += 1
			temp = lastb
			lasta = a
			lastb = b
	print(res)


allInputs = []
for i in range(int(input())):
	currentInput = []
	for j in range(int(input())):
		currentInput.append([int(i) for i in input().split()])
	allInputs.append(currentInput)
currentInput = []

def getMax(arr):
	arr.sort(key=lambda x: x[1])
	overlaps = [0, 0]
	count = 0
	for i in arr:
		if i[0] > overlaps[1]:
			count += 1
			overlaps[1] = i[1]
		elif i[0] > overlaps[0]:
			count += 1
			overlaps[0] = overlaps[1]
			overlaps[1] = i[1]
	return count
for i in allInputs:
	print(getMax(i))


t = int(input())
for _ in range(t):
	n = int(input())
	I = []
	for _ in range(n):
		(a, b) = list(map(int, input().split()))
		I.append((a, b))
	I.sort(key=lambda x: (x[1], x[0]))
	temp = -1
	lasta = 0
	lastb = 0
	res = 0
	for (a, b) in I:
		if a > lastb:
			res += 1
			lasta = a
			lastb = b
		elif a > temp:
			res += 1
			temp = lastb
			lasta = a
			lastb = b
	print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	I = []
	for _ in range(n):
		(a, b) = list(map(int, input().split()))
		I.append((a, b))
	I.sort(key=lambda x: (x[1], x[0]))
	temp = -1
	lasta = 0
	lastb = 0
	res = 0
	for (a, b) in I:
		if a > lastb:
			res += 1
			lasta = a
			lastb = b
		elif a > temp:
			res += 1
			temp = lastb
			lasta = a
			lastb = b
	print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	I = []
	for _ in range(n):
		(a, b) = list(map(int, input().split()))
		I.append((a, b))
	I.sort(key=lambda x: (x[1], x[0]))
	temp = -1
	lasta = 0
	lastb = 0
	res = 0
	for (a, b) in I:
		if a > lastb:
			res += 1
			lasta = a
			lastb = b
		elif a > temp:
			res += 1
			temp = lastb
			lasta = a
			lastb = b
	print(res)