Maximum Non-overlapping Appointments

In this problem, you are given a list of appointments, each represented by a start time and an end time. Your task is to determine the maximum number of appointments that can be scheduled without overlapping. Two appointments do not overlap if their times satisfy the inequality (a_{end} \le b_{start}), where (a_{end}) is the end time of the current appointment and (b_{start}) is the start time of the next appointment. This problem is a classic example of interval scheduling and can be optimally solved by a greedy algorithm that sorts the appointments by their end times.

inputFormat

The input is given via standard input (stdin). The first line contains an integer (n), representing the number of appointments. Each of the following (n) lines contains two space-separated integers denoting the start time and the end time of an appointment.

outputFormat

Output a single integer to standard output (stdout) representing the maximum number of non-overlapping appointments that can be scheduled.## sample

5
1 3
2 5
4 6
6 7
5 9

3