Maximum Non-Overlapping Exhibits

You are given a list of exhibits, each with a start and end time. The goal is to select the maximum number of exhibits such that no two selected exhibits overlap. Formally, for each exhibit represented as an interval \( (s_i, e_i) \), if the exhibit is selected, then the start time \( s_j \) of the next selected exhibit must satisfy \( s_j \geq e_i \). This problem is a classic interval scheduling problem.

Input Format: The first line of input contains an integer \( n \) representing the number of exhibits. Each of the following \( n \) lines contains two integers, the start and end times of an exhibit.

Output Format: Output a single integer representing the maximum number of non-overlapping exhibits that can be scheduled.

inputFormat

The input consists of multiple lines:

1. The first line contains a single integer \( n \) (\( 0 \leq n \leq 10^5 \)), the number of exhibits.
2. Each of the next \( n \) lines contains two space-separated integers \( s_i \) and \( e_i \) (\( 0 \leq s_i < e_i \leq 10^9 \)), representing the start and end times of an exhibit.

outputFormat

Output a single integer: the maximum number of exhibits that can be scheduled without any overlap.

3
1 4
2 3
3 5

2