Maximum Non-overlapping Sessions

You are given n sessions, each with a start time and an end time. Your task is to determine the maximum number of sessions you can schedule such that no two sessions overlap.

Note: Two sessions do not overlap if the start time of one is greater than or equal to the end time of the previously selected session. The solution can be achieved by sorting the sessions by their end times and then selecting sessions greedily.

Formula: Let \(\{(s_i, e_i)\}_{i=1}^n\) be the sessions sorted by \(e_i\). Then the maximum number of non-overlapping sessions is obtained by selecting session \(i\) if \(s_i \geq e_{last}\), where \(e_{last}\) is the end time of the last selected session.

inputFormat

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

n
s1 e1
s2 e2
... 
sn en

Here, n is the number of sessions, and each of the next n lines contains two integers s and e representing the start and end times of a session.

outputFormat

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

5
1 2
2 3
3 4
1 3
2 5

3