Meeting Rooms Problem: Greedy Interval Scheduling Explained with Examples

The Meeting Rooms Problem is a classic interval scheduling problem in algorithms. It deals with the question of whether a person can attend all meetings, or alternatively, the minimum number of meeting rooms required to accommodate all meetings. This problem is widely used in technical interviews and real-world scheduling systems, making it a must-know for programmers.

The problem can be framed in two major variations:

• Meeting Rooms I: Given a set of intervals, can one person attend all the meetings without overlaps?
• Meeting Rooms II: Find the minimum number of rooms required to schedule all meetings such that no overlaps occur in the same room.

Understanding the Meeting Rooms Problem

We are given an array of intervals, where each interval has a start time and an end time. For example, let’s say:

Meetings = [(0,30), (5,10), (15,20)]

Graphically, these meetings look like this:

From the diagram, (0,30) conflicts with both (5,10) and (15,20). Clearly, one meeting room is not enough.

Approach 1: Greedy Algorithm for Meeting Rooms I

To check if a person can attend all meetings without conflict:

1. Sort the intervals by start times.
2. Check if any meeting overlaps with the next one (i.e., if start[i] < end[i-1]).
3. If overlap is found, attending all meetings is not possible.

Python Implementation

def can_attend_meetings(intervals):
    intervals.sort(key=lambda x: x[0])  # Sort by start times
    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i-1][1]:
            return False
    return True

# Example
meetings = [(0,30),(5,10),(15,20)]
print(can_attend_meetings(meetings))  # Output: False

This approach runs in O(n log n) due to sorting.

Approach 2: Greedy Algorithm for Meeting Rooms II

Now, we want to find the minimum number of rooms required. The greedy idea:

1. Sort meetings by start time.
2. Use a min-heap (priority queue) to track current meeting end times.
3. For each meeting:
   • If the earliest ending meeting is finished (end_time <= current start), we can reuse that room.
   • Otherwise, we need a new room.

Python Implementation

import heapq

def min_meeting_rooms(intervals):
    if not intervals: return 0
    
    intervals.sort(key=lambda x: x[0])
    heap = []
    heapq.heappush(heap, intervals[0][1])  # End time of first meeting
    
    for i in range(1, len(intervals)):
        if heap[0] <= intervals[i][0]:  # Room can be reused
            heapq.heappop(heap)
        heapq.heappush(heap, intervals[i][1])
    
    return len(heap)

# Example
meetings = [(0,30),(5,10),(15,20)]
print(min_meeting_rooms(meetings))  # Output: 2

This solution also runs in O(n log n), where n is the number of meetings. The heap ensures optimal room allocation.

Visual Example of Greedy Allocation

Let’s consider another input: [(0,5), (6,10), (5,7), (8,9)].

The greedy algorithm efficiently assigns 2 rooms, ensuring no overlaps within the same room.

Complexity Analysis

• Time Complexity: Both solutions sort intervals first → O(n log n).
• Space Complexity:
  • Meeting Rooms I: O(1)
  • Meeting Rooms II: O(n) due to heap.

Interactive Example (Try Yourself)

You can experiment with different meeting intervals using Python:

meetings = [(1,4),(2,5),(7,9),(3,6)]
print("Can attend all meetings:", can_attend_meetings(meetings))
print("Minimum rooms required:", min_meeting_rooms(meetings))

Key Takeaways

• The Meeting Rooms Problem demonstrates the power of greedy algorithms.
• Sorting by start times is the critical first step in both variations.
• Heap-based scheduling ensures optimal room allocation for multiple meetings.
• This problem maps directly to real-world scenarios like conference scheduling, CPU task execution, and booking systems.

By mastering the Meeting Rooms Problem, you strengthen your foundation in interval scheduling, heap data structures, and greedy algorithm design, preparing yourself for complex scheduling and optimization problems.