Maximum Non-Overlapping Tasks

You are given a list of tasks with their start and end times. Your task is to determine the maximum number of non-overlapping tasks that can be scheduled for a single developer.

Note: Two tasks are considered non-overlapping if the start time of one task is greater than or equal to the end time of the previous task. The goal is to maximize the number of tasks that do not conflict with each other.

The optimal solution is achieved by sorting the tasks by their end time and then selecting tasks greedily.

In mathematical terms, given a list of tasks \( T = \{(s_1, e_1), (s_2, e_2), \dots, (s_n, e_n)\} \), find the maximum \( k \) such that there exists a subsequence \( (s_{i_1}, e_{i_1}), (s_{i_2}, e_{i_2}), \dots, (s_{i_k}, e_{i_k}) \) where \( e_{i_j} \leq s_{i_{j+1}} \) for all \( 1 \leq j

inputFormat

The first line contains a single integer \( n \) representing the number of tasks.

The following \( n \) lines each contain two integers separated by space: the first integer is the start time and the second integer is the end time of a task.

outputFormat

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

6
1 4
3 5
0 6
5 7
8 9
5 9

3