Minimum Guards to Cover Entrance Points

You are given a set of time intervals representing the periods during which various entrances are available. A guard can cover an interval if he is stationed at the end of that interval, and one guard can cover multiple intervals as long as the intervals overlap. Your task is to determine the minimum number of guards required to cover all the intervals.

The optimal strategy is to sort the intervals by their end times and then greedily select guards by choosing the earliest finishing interval that is not yet covered. This approach ensures that each guard covers as many intervals as possible.

Mathematically, if the intervals are \(I_1, I_2, \ldots, I_n\) with start and end times \((s_i, e_i)\), sort them so that \(e_1 \le e_2 \le \ldots \le e_n\). Then, iterate through the intervals and select an interval \(I_k\) if its start time \(s_k\) is greater than the end time of the last chosen interval. The total number of selections is the minimum number of guards needed.

inputFormat

The input is given via stdin in the following format:

• The first line contains an integer \(n\) (where \(0 \le n \le 10^5\)), representing the number of intervals.
• The following \(n\) lines each contain two space-separated integers \(s\) and \(e\) (with \(1 \le s < e \le 10^9\)), denoting the start and end times of an interval.

outputFormat

Output a single integer to stdout: the minimum number of guards required to cover all intervals.

## sample

1
1 4

1

</p>