Maximum Non-Overlapping Tasks

You are given ( N ) tasks. Each task is represented by a time interval ( (s_i, e_i) ), where ( s_i ) is the start time and ( e_i ) is the end time of the task. Your goal is to select as many tasks as possible such that no two selected tasks overlap. Two tasks ( (s_i, e_i) ) and ( (s_j, e_j) ) are said to be non-overlapping if ( s_j \geq e_i ) when ( e_i ) occurs before ( e_j ) or vice versa.

A well-known greedy approach to solve this problem is to sort the tasks by their ending times and then choose tasks one by one, selecting the next task that starts after or exactly when the previous task ended.

Formally, find the maximum number of tasks you can schedule such that for any two selected tasks ( (s_i, e_i) ) and ( (s_j, e_j) ), the condition ( s_j \ge e_i ) holds if task ( i ) is scheduled before task ( j ).

inputFormat

The first line contains an integer ( N ) (the number of tasks). Each of the following ( N ) lines contains two space-separated integers ( s_i ) and ( e_i ) representing the start and end times of the ( i )-th task.

Input is read from standard input.

outputFormat

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

Output is written to standard output.## sample

3
1 4
2 3
3 5

2