1. The Problem
Given a set of `n` class requests as intervals `(start_time, end_time)`, find the minimum number of classrooms required to schedule all classes without any conflicts. This is a classic problem known as Interval Partitioning.
2. The Idea: Greedy Algorithm
The minimum number of rooms needed is determined by the maximum number of classes that are happening at the same time. This is often called the "depth" of the set of intervals.
A greedy approach works perfectly here. We can process the classes in chronological order. Imagine a "sweep-line" moving from the earliest start time to the latest end time.
- When the line encounters the start of a class, we need one more room.
- When it encounters the end of a class, one room becomes free.
By tracking the number of active classes at any point, the maximum number we encounter is our answer. The most effective way to implement this is to create a list of all start and end points, sort them, and iterate through them.
3. The Algorithm
- Create a list of "events". For each interval `(xi, yi)`, add two events: `(xi, 'start')` and `(yi, 'end')`.
- Sort this list of events primarily by time. If times are equal, place 'start' events before 'end' events to correctly handle classes that end exactly when another begins.
- Initialize `rooms_needed = 0` and `max_rooms = 0`.
- Iterate through the sorted list of events:
- If the event is a 'start', increment `rooms_needed`.
- If the event is an 'end', decrement `rooms_needed`.
- After each step, update `max_rooms = max(max_rooms, rooms_needed)`.
- The final value of `max_rooms` is the minimum number of rooms required.
4. Complexity Analysis
- Time Complexity: O(n log n)
- There are `2n` events in total. The dominant operation is sorting this list of events, which takes O(2n log 2n) = O(n log n) time. The single pass through the sorted list takes O(n) time.
- Space Complexity: O(n)
- We need to store the `2n` events in a list, which requires O(n) space.