Maximum Number of Non-overlapping Tasks

You are given a set of tasks, where each task has a start time and a finish time. Two tasks are said to overlap if they share any common time interval. The goal is to determine the maximum number of tasks that can be performed without any overlap.

Formally, given \( n \) tasks with start times \( s_i \) and finish times \( f_i \), select a subset of tasks such that no two tasks overlap and the size of the subset is maximized. A task \( i \) is compatible with task \( j \) if \( s_i \ge f_j \) or vice versa.

This is a classic greedy algorithm problem where the tasks are sorted by their finish times. The greedy choice is to always select the task that finishes earliest, then continue selecting the next task that starts after the finish time of the previously selected task.

inputFormat

Input is read from standard input (stdin). 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 representing the start and finish times of a task.

outputFormat

Output a single integer to standard output (stdout) representing the maximum number of non-overlapping tasks that can be selected.## sample

3
1 3
2 5
3 6

2