Maximum Non-Overlapping Actions

This problem is a variant of the classic activity selection problem. You are given N actions, where each action is defined by a starting time and an ending time. Your task is to determine the maximum number of actions that can be executed without overlapping. Two actions do not overlap if the start time of an action is greater than or equal to the end time of the previously selected action.

You may recall the greedy strategy used to solve the activity selection problem. In mathematical terms, after sorting the actions by their end times, you choose the first action and then select the next action which satisfies:

where \( \text{end}_{prev} \) is the end time of the last chosen action.

inputFormat

The input is given via standard input (stdin) with the following format:

• The first line contains an integer N, representing the number of actions.
• The following N lines each contain two integers separated by a space, representing the start time and end time of an action.

outputFormat

Output a single integer to standard output (stdout) — the maximum number of non-overlapping actions.

4
1 3
2 5
4 6
7 9

3