Maximum Non-Overlapping Activities

Given a set of activities, each with a start time and an end time, your task is to determine the maximum number of non-overlapping activities that can be scheduled. Two activities are considered non-overlapping if the start time of one is greater than or equal to the end time of the previously scheduled activity.

This problem can be modeled as an activity selection problem. The optimal strategy is to sort the activities by their end times and then greedily select as many activities as possible.

Note: All formulas or mathematical notations should be written in LaTeX format if needed (e.g. \( \sum_{i=1}^n a_i \)). In this problem, the algorithm is based on a simple greedy approach.

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\), representing the start time and end time of an activity.

outputFormat

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

3
1 2
2 3
3 4

3