Maximum Non-Overlapping Projects

Jim has a list of projects, each with a start time and an end time. He wants to complete as many projects as possible in one day, but he cannot work on overlapping projects. Two projects overlap if the start time of one is less than the end time of a project already chosen. Using a greedy strategy, determine the maximum number of projects Jim can complete.

Note: The projects are scheduled on a timeline, and if one project ends at time e, then another project starting at time e is considered non-overlapping.

The greedy strategy is based on sorting the projects by their end times to maximize the number of projects Jim can complete.

In mathematical terms, if the projects are represented as intervals \([s_i, e_i]\) for \(i=1,2,...,n\), we wish to select a subset of intervals such that for any two intervals in the subset \([s_i, e_i]\) and \([s_j, e_j]\), we have \(s_j \ge e_i\) (assuming \(e_i \le e_j\)), and the size of the subset is maximized.

inputFormat

The first line of input contains a single integer n \( (1 \leq n \leq 10^5) \), representing the number of projects.

The next n lines each contain two space-separated integers, representing the start time and end time of a project.

It is guaranteed that the start and end times are integers.

outputFormat

Output a single integer, which is the maximum number of non-overlapping projects that can be completed.

5
1 4
2 3
3 5
6 8
7 9

3