Maximum Non-overlapping Tasks

You are given a list of tasks, where each task is represented by a start time and an end time. Your goal is to determine the maximum number of tasks that can be scheduled without any overlap. Two tasks are considered non-overlapping if the start time of a task is not less than the end time of the previously scheduled task.

This problem can be optimally solved using a greedy algorithm by first sorting the tasks by their end times. After sorting, iterate over the tasks and select a task if its start time is greater than or equal to the end time of the last selected task.

Formally, if the tasks are represented as intervals \( (s_i, e_i) \), the algorithm is as follows:

\[ \text{sort}(\{(s_i, e_i)\}) \text{ by } e_i \] \[ \text{current\_end} = -\infty,\quad \text{count} = 0 \] \[ \text{for each } (s, e) \text{ in the sorted list:} \] \[ \quad \text{if } s \geq \text{current\_end}: \quad \text{count}++ \quad \text{and} \quad \text{current\_end} = e \]

Output the computed maximum count.

inputFormat

The first line of the input contains an integer N representing the number of tasks. The following N lines each contain two space-separated integers representing the start time and end time of a task.

outputFormat

Output a single integer representing the maximum number of non-overlapping tasks that can be scheduled.

## sample

5
1 3
2 5
4 6
6 8
5 7

3

</p>