Maximum Non-Overlapping Performances

You are given a list of performances, where each performance has a start time and an end time. Your task is to determine the maximum number of performances that can be scheduled on the main stage without any overlapping. Two performances are considered non-overlapping if the start time of the later performance is not earlier than the end time of the previous one.

Note: The performances must be selected such that no two performances overlap in time. The optimal solution is to always select the performance that finishes the earliest, which is a classic greedy algorithm approach.

Input: The first line of input contains a single integer n denoting the number of performances. The following n lines each contain two integers representing the start and end times of a performance.

Output: The output is a single integer representing the maximum number of non-overlapping performances that can be scheduled.

inputFormat

The input is given via stdin and is formatted as follows:

• The first line contains an integer n, the number of performances.
• Each of the next n lines contains two space-separated integers, where the first integer is the start time and the second integer is the end time of a performance.

outputFormat

Print a single integer to stdout representing the maximum number of non-overlapping performances that can be scheduled.

5
1 4
3 5
0 6
5 7
8 9

3