Maximum Number of Non-Overlapping Challenges

You are given $n$ challenges, each with a start time $s$ and an end time $e$. Your task is to select the maximum number of challenges such that no two selected challenges overlap. This problem can be modeled with intervals where each interval is represented by its start and end times. A challenge $i$ is represented as an interval $[s_i, e_i]$. Two challenges are non-overlapping if $s_j \geq e_i$ when challenge $i$ finishes. Use a greedy algorithm that sorts the intervals by their ending times to achieve an optimal solution.

For example, given the intervals: $(1, 3)$, $(2, 5)$, $(4, 6)$, and $(5, 7)$, the maximum number of non-overlapping challenges is $2$.

inputFormat

The input is read from standard input (stdin). The first line contains an integer $n$, the number of challenges. Each of the next $n$ lines contains two space-separated integers representing the start time and the end time of a challenge.

outputFormat

Output a single integer to standard output (stdout), the maximum number of non-overlapping challenges.## sample

4
1 3
2 5
4 6
5 7

2