Maximum Non-Overlapping Tasks

You are given a set of tasks, each defined by a start time and an end time. The goal is to select the maximum number of tasks such that no two tasks overlap. Two tasks are considered non-overlapping if the start time of the current task is greater than or equal to the end time of the previously selected task.

In other words, if each task is represented as \( (s_i, e_i) \) for \( i=1,2,\dots,n \), you need to choose the maximum size subset of tasks satisfying: \[ s_{i_j} \ge e_{i_{j-1}} \quad \text{for all } j=2,3,\dots, k \]

This is a classic greedy algorithm problem where sorting by the task's ending time leads to an optimal solution.

inputFormat

The first line contains an integer \( n \) representing the number of tasks. Each of the next \( n \) lines contains two integers, \( s \) and \( e \), which represent the start and end times of a task.

Example:

5
1 3
2 5
4 6
7 8
5 9

outputFormat

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

Example:

3

## sample

5
1 3
2 5
4 6
7 8
5 9

3

</p>