Maximum Number of Non-Overlapping Activities

Given a list of activities with their start and end times, your task is to determine the maximum number of non-overlapping activities that can be attended. Two activities are non-overlapping if the start time of one is not less than the end time of the previously selected activity.

You may use a greedy algorithm to solve this problem. In particular, by sorting the activities by their end times, one can select the activity that finishes first and then continue selecting the next activity whose start time is not earlier than the previous selected activity's finish time.

For illustration, consider the following formula which explains the optimal substructure of the problem: $$ \text{Let } f(i) = \min\{ j \;|\; s_j \geq f(i-1) \}, $$ where s_j is the start time of activity j. This formula is for understanding and is not required to be implemented directly.

inputFormat

The input is read from stdin and is formatted as follows:

• The first line contains an integer n representing the number of activities.
• Each of the next n lines contains two space-separated integers s and e which represent the start and end times of an activity.

outputFormat

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

4
1 3
2 4
3 5
7 8

3