Maximum Non-Overlapping Reservations

You are given n reservations, each represented by a time interval. Your task is to determine the maximum number of reservations that can be scheduled without any overlaps. Two reservations are considered overlapping if they intersect; otherwise, they are non-overlapping.

More formally, you are provided with n pairs \((s_i, e_i)\) where \(s_i\) is the start time and \(e_i\) is the end time of the i-th reservation. Find the maximum size subset of reservations such that no two intervals in the subset overlap. The standard greedy technique which selects intervals by increasing order of finish times is applicable to this problem.

Input Format: The first line contains a single integer n \( (1 \leq n \leq 10^5)\). Each of the next n lines contains two integers \(s_i\) and \(e_i\) representing a reservation's start and end times.

Output Format: Output one integer denoting the maximum number of non-overlapping reservations you can schedule.

inputFormat

The input is read from stdin. The first line contains an integer n, the number of reservations. Each of the following n lines contains two space-separated integers, representing the start and end times of a reservation.

outputFormat

Print a single integer representing the maximum number of non-overlapping reservations that can be scheduled.## sample

5
1 3
2 5
4 6
7 8
5 9

3