Maximum Number of Non-Overlapping Runners

You are given a set of runner time requests. Each request is represented as an interval [s, f] where s is the start time and f is the finish time. Two runners can participate simultaneously if their intervals do not overlap, i.e., for two intervals [s₁, f₁] and [s₂, f₂], they do not overlap if s₁ \ge f₂ or s₂ \ge f₁.

Your task is to determine the maximum number of runner requests that can be accommodated without any overlap.

Note: The problem follows the classic activity selection (interval scheduling) paradigm where a greedy algorithm sorting by finish times can be applied.

inputFormat

The first line contains a single integer n representing the number of runner requests.

Each of the next n lines contains two space-separated integers s and f representing the start and finish times of a runner's request.

It is guaranteed that 1 ≤ n ≤ 200000 and the times are integers.

outputFormat

Output a single integer, the maximum number of non-overlapping runner requests that can be selected.

3
1 2
2 3
3 4

3