Appointment Scheduling

Problem Statement:

The Supreme Hon’ble head of state of the Democratic People’s Republic of Mars has a very busy schedule. He has N appointments on his calendar. However since some of them overlap, it is impossible for him to attend all these appointments. Therefore, he wants to select a subset of these N appointments. The ith event begins at time S_i and ends at time T_i. Your task is to find the maximum number of appointments that the head of state can attend without any overlapping appointments.

Constraints:

• 1 ≤ S_i, B_i ≤ 10⁹
• 1 ≤ N ≤ 10⁵

Subtask 1: 20 points

• 1 ≤ N ≤ 15

Subtask 2: 10 points

• S_i = T_i

Subtask 3:

• No additional constraints

Input Format:

• The first line contains a single integer N
• The next N lines contain two integers S_i and T_i

Output Format:

• Print a single line containing the maximum number of events the head of state can attend

Sample input:

4
1 3
2 5
3 9
6 8

Sample output:

2

Explanation:

If we select the first appointment, it gets over at time 3. Then we cannot select either the second or third appointment as they overlap with the first one. The only appointment we can select is the fourth one.

It can be shown that there is no way to select 3 or more appointments without overlap.

Solution:

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

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

c = 0
res = 0
for i in a:
	if c < i[0]:
		res += 1
		c = i[1]

print(res)