Maximum Non-overlapping Performances

You are given a list of performance slots, where each slot is represented by its start and end times. Your task is to determine the maximum number of performances you can attend without any overlap. Two performances are said to be non-overlapping if the start time of one is not less than the end time of the other.

This is a classic interval scheduling optimization problem that can be solved with a greedy algorithm. In mathematical terms, given a set of intervals \( \{(s_i, e_i)\}_{i=1}^{n} \), you need to select a maximum-size subset \( S \) such that for every two intervals \( (s_i, e_i) \) and \( (s_j, e_j) \) in \( S \) with \( i \neq j \), either \( e_i \leq s_j \) or \( e_j \leq s_i \) holds.

Input/Output Format: The input will be provided via stdin and the output should be printed to stdout.

inputFormat

The first line contains a single integer \( n \) representing the number of performances. Each of the following \( n \) lines contains two integers \( s \) and \( e \) separated by a space, representing the start and end times of a performance slot.

outputFormat

Output a single integer representing the maximum number of non-overlapping performances that can be attended.

6
1 4
3 5
0 6
5 7
8 9
5 9

3