Maximum Non-Overlapping Tasks Scheduling

You are given a set of tasks where each task is represented as an interval with a start time and an end time. Your goal is to select the maximum number of tasks such that no two tasks overlap. A task defined by the interval \( [s,e] \) is said to overlap with another task \( [s',e'] \) if \( s < e' \) and \( s' < e \). This problem can be optimally solved using a greedy algorithm. The optimal strategy is to always pick the task that finishes the earliest, thereby maximizing the remaining time for future tasks. This approach is based on the principle that if tasks are sorted by their ending times, the locally optimal choice leads to a globally optimal solution.

Input Constraints: The number of tasks \( n \) can be as high as \( 10^5 \). Each task is represented by two integers \( s \) and \( e \) where \( 0 \leq s \leq e \).

inputFormat

The first line of input contains an integer \( n \) representing the number of tasks. Each of the following \( n \) lines contains two space-separated integers \( s \) and \( e \), representing the start time and end time of a task, respectively.

outputFormat

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

3
1 3
2 5
4 6

2