Maximum Non-Overlapping Activities

You are given n activities. Each activity has a start time and an end time. Your task is to select the maximum number of non-overlapping activities to attend. Two activities are non-overlapping if the start time of one is not less than the end time of another. This problem can be formulated as selecting the largest subset of intervals such that for any two intervals \( (s_i, e_i) \) and \( (s_j, e_j) \) in the subset (with \( i < j \) after sorting by end times), we have \( s_j \ge e_i \).

Input Format: The first line contains an integer n (the number of activities). The following n lines each contain two integers representing the start and finish times of each activity, separated by spaces.

Output Format: Output a single integer representing the maximum number of non-overlapping activities.

inputFormat

The first line contains an integer ( n ) which is the number of activities. Each of the next ( n ) lines contains two space-separated integers, the start time and end time of an activity.

outputFormat

Print a single integer which is the maximum number of non-overlapping activities that can be attended.## sample

5
1 2
3 4
0 6
5 7
8 9

4