Classroom Scheduling

Your task is to determine the minimum number of classrooms required to schedule all classes such that no two classes overlap. Each class is represented by its start time and end time. You must design an algorithm that efficiently calculates the maximum number of classes occurring at the same time.

The key idea is to use a sweep-line algorithm where we sort the start and end times separately. In mathematical notation, we are essentially finding \( \max_{t} (\text{number of overlapping classes at time } t) \).

inputFormat

The first line contains an integer \( n \) representing the number of classes. Each of the following \( n \) lines contains two space-separated integers \( s \) and \( e \), denoting the start and end times of a class.

outputFormat

Output a single integer that is the minimum number of classrooms required to schedule all the classes without any overlaps.

3
30 75
0 50
60 150

2