Maximum Non-Overlapping Tasks

You are given a list of tasks, each defined by a start time and an end time. The objective is to select a maximum set of tasks that do not overlap. Two tasks are considered non-overlapping if the start time of a task is not less than the end time of the previously selected task.

This is a classic greedy algorithm problem. One common approach is to sort the tasks by their finish times. Once sorted, iterate through the tasks and select a task if its start time is not less than the finish time of the last selected task. The overall time complexity of this approach is \(O(n \log n)\) due to sorting.

inputFormat

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

• The first line contains an integer (n) representing the number of tasks.
• Each of the following (n) lines contains two space-separated integers representing the start and end times of a task.

outputFormat

Output a single integer to standard output, representing the maximum number of non-overlapping tasks that can be performed.## sample

5
1 3
2 5
4 6
6 7
5 8

3