Maximizing Non-overlapping Sessions

You are given n sessions, each defined by a start time and an end time. Two sessions are said to be non-overlapping if the start time of one is greater than or equal to the end time of the other. Your task is to select the maximum number of non-overlapping sessions that can fit into a schedule.

Formally, given a list of sessions \( (s_i, e_i) \) for \( i = 1, 2, \dots, n \) where \( 1 \leq s_i < e_i \leq 10^9 \), choose a subset such that if session \(a\) and session \(b\) are both chosen and \( a \neq b \), then either \( s_a \geq e_b \) or \( s_b \geq e_a \). The goal is to maximize the size of this subset.

It is known that a greedy algorithm which sorts sessions by their end times gives an optimal solution.

inputFormat

The input is read from stdin and has the following format:

• The first line contains a single integer \(n\) (\(1 \leq n \leq 10^5\)), representing the number of sessions.
• The following \(n\) lines each contain two space-separated integers \(s_i\) and \(e_i\) (\(1 \leq s_i < e_i \leq 10^9\)) representing the start and end times of a session.

outputFormat

Output a single integer to stdout representing the maximum number of non-overlapping sessions that can be scheduled.

3
1 3
2 5
4 6

2