Maximum Non-Overlapping Reservations

You are given N reservation requests. Each reservation is represented by its start time and end time. Two reservations are considered non-overlapping if the start time of one is greater than or equal to the end time of the other. The goal is to select the maximum number of non-overlapping reservations.

This problem can be solved using a greedy algorithm. First, sort the reservations by their end times. Then, iterate through the sorted list and select a reservation if its start time is not less than the end time of the last selected reservation.

The problem can be formally described as follows:

Given a set of reservations \(R = \{[s_i, e_i]\}_{i=1}^N\), find the maximum \(k\) such that there exists a subset \(R' \subseteq R\) with \(|R'| = k\) and for every two intervals \([s_i, e_i]\) and \([s_j, e_j]\) in \(R'\) (with \(i \neq j\)), the intervals do not overlap (i.e. either \(s_i \ge e_j\) or \(s_j \ge e_i\)).

Your task is to implement a program that reads the input from standard input (stdin) and outputs the result to standard output (stdout).

inputFormat

The input is given via standard input (stdin) with the following format:

• The first line contains an integer N, the number of reservation requests.
• Each of the next N lines contains two integers s and e, representing the start and end times of a reservation.

If N is 0, no further input follows.

outputFormat

Output a single integer representing the maximum number of non-overlapping reservations.

## sample

3
1 4
2 5
3 6

1