Activity Selection: Maximum Non-Overlapping Sessions

You are given n sessions, each represented by its start and end times. Your task is to select the maximum number of sessions such that no two selected sessions overlap. This is a classic activity selection problem which can be solved using a greedy algorithm. In this problem, after sorting the sessions by their end times, you should iteratively choose the session that finishes first and eliminate all sessions that begin before the selected session ends.

The mathematical formulation is as follows: Given a set of sessions \(\{(s_i, e_i)\}_{i=1}^n\), you are to find the largest subset \(S\) such that for any two sessions \((s_j,e_j)\) and \((s_k,e_k)\) in \(S\) with \(j \neq k\), either \(e_j \leq s_k\) or \(e_k \leq s_j\) holds.

inputFormat

The first line contains an integer n denoting the number of sessions.

The following n lines each contain two integers separated by a space, representing the start time and end time of a session.

Note: The sessions may not be in sorted order.

outputFormat

Output a single integer which is the maximum number of non-overlapping sessions that can be selected.

## sample

5
1 3
2 5
4 7
6 9
8 10

3

</p>