Interval Scheduling - Learning Module

Loading content...

0/276

Meeting Rooms Problems

From Selection to Resource Allocation

Interval covering taught us to minimize resources for complete coverage. Activity selection taught us to maximize non-conflicting intervals. But in the real world, we often face a different constraint: we must accommodate ALL requests, and we need to know how many resources that requires.

The Meeting Rooms problem family asks: given a set of intervals (meetings, flights, processes), how many simultaneous resources (rooms, gates, processors) do we need so that every interval runs without conflict? This isn't about selection—it's about capacity planning.

These problems appear constantly in practice:

How many conference rooms does our floor need?
How many airport gates handle today's flight schedule?
How many servers must run in parallel for peak load?
How many cashiers needed during the lunch rush?

What You Will Learn

By the end of this page, you will solve 'Meeting Rooms I' (can we fit in K rooms?), solve 'Meeting Rooms II' (minimum rooms needed), understand the relationship between overlap and resource requirements, master both the sorting approach and heap-based approach, and recognize this pattern across diverse problem domains.

Meeting Rooms I: Conflict Detection

Before we count rooms, let's solve the simpler detection problem:

Problem Statement (Meeting Rooms I)

Given an array of meeting time intervals where intervals[i] = [startᵢ, endᵢ], determine if a person could attend all meetings.

Translation: Can one room host all meetings? Do any intervals overlap?

This is fundamentally a conflict detection problem. If any two meetings overlap (one starts before another ends), we need more than one room.

The Insight: Sorting Reveals Conflicts

If we sort meetings by start time, any conflict must occur between consecutive meetings (in sorted order). Why? If meeting A ends before meeting B starts, and meeting B ends before meeting C starts, then certainly A doesn't conflict with C. Transitivity of non-overlap means we only need pairwise checks of adjacent elements.

meeting_rooms_i.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def can_attend_all_meetings(intervals: list[list[int]]) -> bool:
    """
    Determine if one person can attend all meetings.
    
    Returns True if no meetings overlap, False otherwise.
    
    Time: O(n log n) for sorting
    Space: O(1) extra (O(n) if we can't sort in-place)
    """
    if len(intervals) <= 1:
        return True  # 0 or 1 meetings, no conflict possible
    
    # Sort by start time
    intervals.sort(key=lambda x: x[0])
    
    # Check consecutive pairs for overlap
    for i in range(1, len(intervals)):
        prev_end = intervals[i - 1][1]
        curr_start = intervals[i][0]
        
        # Overlap: previous meeting ends AFTER current starts
        if prev_end > curr_start:
            return False
    
    return True
 
 
# Example tests
print(can_attend_all_meetings([[0, 30], [5, 10], [15, 20]]))  # False
print(can_attend_all_meetings([[7, 10], [2, 4]]))             # True

Edge Case: Back-to-Back Meetings

What if meeting A ends at time 10 and meeting B starts at time 10? Does this count as overlap? Typically NO—a person can attend both. Our condition 'prevEnd > currStart' correctly handles this: if equal, no conflict. Some problems define overlap differently (≥ instead of >), so always verify problem constraints.

Meeting Rooms II: Minimum Rooms Required

Now the central question: given n meetings, what's the minimum number of rooms needed to host all of them without overlap?

Problem Statement (Meeting Rooms II)

Given an array of meeting time intervals, find the minimum number of conference rooms required.

Key Insight: Maximum Overlap

The answer equals the maximum number of meetings occurring simultaneously at any point in time. If at moment t, there are 5 ongoing meetings, we need at least 5 rooms.

This transforms the problem: instead of scheduling, we're finding the peak concurrent usage—the same problem as finding maximum depth of overlapping intervals.

Meeting Rooms II ExampleFinding minimum rooms needed

Input

Meetings: [0, 30], [5, 10], [15, 20]

Output

Minimum rooms: 2

Explanation

At time 5, both [0, 30] and [5, 10] are active → 2 meetings overlap. This is the peak, so 2 rooms suffice. Room 1 hosts [0, 30]. Room 2 hosts [5, 10], then [15, 20] (no conflict between these two).

There are two elegant approaches to solve this:

Approach 1: Two-Pointer / Chronological Sweep

Separate starts and ends into two sorted arrays. Walk through time, incrementing a counter at each start and decrementing at each end. Track the maximum.

Approach 2: Min-Heap (Priority Queue)

Sort meetings by start time. Maintain a min-heap of end times (one per room). For each new meeting, if it starts after the earliest-ending room, reuse that room (pop and push); otherwise, allocate a new room (push). Heap size = rooms used.

Both approaches have the same time complexity: O(n log n).

Approach 1: Chronological Event Sweep

The sweep approach treats starts and ends as events along a timeline. Imagine walking left to right along the time axis:

At each start event, a new meeting begins → increment room count
At each end event, a meeting releases a room → decrement room count

The maximum room count observed during this sweep is our answer.

Why It Works:

At any time t, the number of active meetings equals: (# of starts before or at t) - (# of ends before t). By processing events in chronological order, we compute this count incrementally.

Tie-Breaking: End Before Start

When a start and end occur at the same time, process the end first. Why? If meeting A ends at 10 and meeting B starts at 10, the room from A becomes free just as B needs it—no extra room required. Processing end first reflects this correctly.

meeting_rooms_ii_sweep.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
def min_meeting_rooms_sweep(intervals: list[list[int]]) -> int:
    """
    Find minimum meeting rooms using chronological sweep.
    
    Strategy: Separate start and end times, sort both, 
    sweep with two pointers tracking concurrent meetings.
    
    Time: O(n log n) for sorting
    Space: O(n) for the two arrays
    """
    if not intervals:
        return 0
    
    # Extract and sort start and end times separately
    starts = sorted([interval[0] for interval in intervals])
    ends = sorted([interval[1] for interval in intervals])
    
    rooms_needed = 0
    max_rooms = 0
    
    start_ptr = 0
    end_ptr = 0
    n = len(intervals)
    
    # Sweep through all start events
    while start_ptr < n:
        # If next event is a start (happens before next end)
        if starts[start_ptr] < ends[end_ptr]:
            # Meeting starts: need a room
            rooms_needed += 1
            max_rooms = max(max_rooms, rooms_needed)
            start_ptr += 1
        else:
            # Meeting ends: release a room
            rooms_needed -= 1
            end_ptr += 1
    
    return max_rooms
 
 
# Alternative: explicit event list
def min_meeting_rooms_event_list(intervals: list[list[int]]) -> int:
    """
    Alternative using explicit event list.
    More intuitive, same complexity.
    """
    if not intervals:
        return 0
    
    events = []
    
    for start, end in intervals:
        events.append((start, 1))   # 1 = start event (add room)
        events.append((end, -1))    # -1 = end event (free room)
    
    # Sort by time; ties broken by type (-1 before 1, i.e., end before start)
    events.sort(key=lambda x: (x[0], x[1]))
    
    current_rooms = 0
    max_rooms = 0
    
    for time, delta in events:
        current_rooms += delta
        max_rooms = max(max_rooms, current_rooms)
    
    return max_rooms
 
 
# Example
meetings = [[0, 30], [5, 10], [15, 20]]
print(f"Rooms needed (sweep): {min_meeting_rooms_sweep(meetings)}")      # 2
print(f"Rooms needed (events): {min_meeting_rooms_event_list(meetings)}")  # 2

Two-Pointer vs Event List

The two-pointer approach separates starts and ends into different arrays, using less memory than an event list. The event list is more intuitive and generalizes to problems with more event types (e.g., start, pause, resume, end). Choose based on clarity needs.

Approach 2: Min-Heap for Room Tracking

The heap approach simulates actual room assignment. We process meetings in order of start time and maintain a min-heap of room "release times" (when each room becomes free).

Algorithm:

Sort meetings by start time
Initialize an empty min-heap (will store end times of rooms)
For each meeting [start, end]:
- If heap is non-empty AND heap's minimum ≤ start:
  - A room is free! Pop it and reuse (push new end time)
- Else:
  - No room free, allocate new one (push end time)
Answer = heap size (number of rooms allocated)

Why Min-Heap?

We need to quickly find the earliest-ending room—the one most likely to be free for the next meeting. A min-heap gives O(log n) access to the minimum.

meeting_rooms_ii_heap.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import heapq
 
def min_meeting_rooms_heap(intervals: list[list[int]]) -> int:
    """
    Find minimum meeting rooms using a min-heap.
    
    The heap stores end times of rooms currently in use.
    Heap size = number of rooms needed.
    
    Time: O(n log n) for sorting and heap operations
    Space: O(n) for the heap in worst case
    """
    if not intervals:
        return 0
    
    # Sort meetings by start time
    intervals.sort(key=lambda x: x[0])
    
    # Min-heap of room end times
    # Each entry = when a room becomes free
    rooms = []  # heap
    
    for start, end in intervals:
        # Check if earliest-ending room is free
        if rooms and rooms[0] <= start:
            # Reuse this room: pop old end time, push new end time
            heapq.heapreplace(rooms, end)
        else:
            # Allocate new room: push end time
            heapq.heappush(rooms, end)
    
    return len(rooms)
 
 
def min_meeting_rooms_heap_verbose(intervals: list[list[int]]) -> tuple[int, list]:
    """
    Verbose version that also shows room assignments.
    Returns (room count, list of room assignments).
    """
    if not intervals:
        return 0, []
    
    # Add original index for tracking
    indexed = [(i, start, end) for i, (start, end) in enumerate(intervals)]
    indexed.sort(key=lambda x: x[1])  # Sort by start
    
    rooms = []  # heap entries: (end_time, room_id)
    assignments = [None] * len(intervals)  # meeting i -> room number
    next_room_id = 0
    
    for orig_idx, start, end in indexed:
        if rooms and rooms[0][0] <= start:
            # Reuse existing room
            _, room_id = heapq.heappop(rooms)
            heapq.heappush(rooms, (end, room_id))
            assignments[orig_idx] = room_id
        else:
            # Allocate new room
            heapq.heappush(rooms, (end, next_room_id))
            assignments[orig_idx] = next_room_id
            next_room_id += 1
    
    return next_room_id, assignments
 
 
# Example
meetings = [[0, 30], [5, 10], [15, 20]]
print(f"Rooms needed: {min_meeting_rooms_heap(meetings)}")  # 2
 
rooms, assign = min_meeting_rooms_heap_verbose(meetings)
print(f"Assignments: {assign}")  # [0, 1, 1] - meeting 0 in room 0, meetings 1,2 in room 1

Comparison: Sweep vs Heap Approach
Aspect	Chronological Sweep	Min-Heap
Time Complexity	O(n log n)	O(n log n)
Space Complexity	O(n)	O(n)
Returns	Just the count	Can track actual assignments
Intuition	Count overlaps at each moment	Simulate room reuse
Implementation	Simpler, two sorted arrays	Requires heap structure
Extension-friendly	Good for "at time t" queries	Good for assignment problems

Understanding Maximum Overlap

Both approaches ultimately compute the maximum overlap—the most intervals active at any single point. Let's visualize why this equals minimum rooms.

The Pigeonhole Principle

If at time t there are k meetings happening simultaneously, we need at least k rooms (one meeting per room). This is a lower bound.

Achievability of the Lower Bound

The greedy assignment (heap approach) never uses more than the maximum overlap. Why? When we need a new room, it's because ALL current rooms are occupied—we're at a peak overlap moment. Thus, final room count = max overlap ever seen.

Visualizing with a Timeline:

Time:    0    5    10   15   20   25   30
         |----|----|----|----|----|----|----|

Meeting A: [====================================]  (0-30)
Meeting B:      [=====]                          (5-10)
Meeting C:                   [=====]             (15-20)

Overlap count:
         1    2    1    1    2    1    1
              ^              ^
            peaks at 2

At time 5-10, both A and B are active (overlap = 2). At time 15-20, both A and C are active (overlap = 2). Peak overlap = 2, so minimum rooms = 2.

The Interval Graph Connection

This problem relates to graph coloring. Create a graph where each interval is a node, and edges connect overlapping intervals. The minimum rooms needed equals the graph's chromatic number. For interval graphs, this equals the maximum clique size (max overlap), and greedy coloring achieves it optimally.

Variations and Extensions

The meeting rooms pattern extends to many practical scenarios:

1. Meeting Rooms with Capacity

Each room has a capacity, and each meeting has an attendance count. Match meetings to rooms based on capacity requirements. This becomes a more complex assignment problem.

2. Weighted Meeting Scheduling

Each meeting has a value. Maximize total value of meetings attended, given K rooms. This is NP-hard in general but may admit approximations.

3. Minimize Total Idle Time

Given N rooms and M meetings, assign meetings to minimize total time rooms sit empty. Requires balancing load across rooms.

4. Online Meeting Scheduling

Meetings arrive one by one (you don't see the full list upfront). Make irrevocable decisions. Competitive analysis applies here.

Real-World Variations

•CPU Scheduling — Each interval = process execution window. 'Rooms' = CPU cores. How many cores for concurrent execution?
•Airport Gates — Each interval = flight turnaround time. 'Rooms' = gates. Minimum gates for a day's schedule?
•Parking Lot — Each interval = car arrival to departure. 'Rooms' = parking spaces. How many spaces needed?
•Operating Rooms — Each interval = surgery duration. 'Rooms' = ORs. Minimum ORs for surgery schedule?
•Bandwidth Allocation — Each interval = video stream duration. 'Rooms' = bandwidth units. Peak bandwidth required?

variations.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
def max_overlapping_at_time(intervals: list[list[int]], t: int) -> int:
    """
    Find number of intervals active at a specific time t.
    Useful for point queries.
    """
    count = 0
    for start, end in intervals:
        if start <= t < end:  # Active at time t
            count += 1
    return count
 
 
def rooms_needed_with_buffer(intervals: list[list[int]], buffer: int) -> int:
    """
    Meetings need buffer time between them in the same room.
    E.g., 10-minute cleanup between meetings.
    
    Solution: Extend each meeting's end by buffer duration.
    """
    extended = [[start, end + buffer] for start, end in intervals]
    return min_meeting_rooms_heap(extended)
 
 
def meetings_in_room(intervals: list[list[int]], room_count: int) -> bool:
    """
    Can all meetings fit in exactly 'room_count' rooms?
    (Meeting Rooms I generalized to K rooms)
    """
    return min_meeting_rooms_heap(intervals) <= room_count
 
 
def min_meeting_rooms_heap(intervals):
    """Helper from previous implementation."""
    import heapq
    if not intervals:
        return 0
    intervals = sorted(intervals, key=lambda x: x[0])
    rooms = []
    for start, end in intervals:
        if rooms and rooms[0] <= start:
            heapq.heapreplace(rooms, end)
        else:
            heapq.heappush(rooms, end)
    return len(rooms)
 
 
# Example: meetings with 5-minute buffer
meetings = [[0, 30], [35, 50], [40, 60]]
print(f"Without buffer: {min_meeting_rooms_heap(meetings)} rooms")      # 2
print(f"With 5-min buffer: {rooms_needed_with_buffer(meetings, 5)} rooms")  # 2 (still)
print(f"With 10-min buffer: {rooms_needed_with_buffer(meetings, 10)} rooms")  # might need more

Common Mistakes and Edge Cases

When implementing meeting rooms solutions, watch for these pitfalls:

Mistake 1: Wrong Tie-Breaking

If a meeting ends at time 10 and another starts at time 10, they can share a room. Process ends before starts at equal times. In the event list approach, use -1 for ends and +1 for starts so ends sort first.

Mistake 2: Off-by-One with Heap

When checking if a room is free (rooms[0] <= start), use <= not <. If room frees at time 10 and meeting starts at 10, the room IS available.

Mistake 3: Forgetting to Sort

Both approaches require sorted input. The sweep needs sorted starts and ends. The heap needs meetings sorted by start time.

Mistake 4: Empty Input

Always handle the empty array case—return 0 rooms needed.

Edge Cases to Test

•Empty input — [] → 0 rooms
•Single meeting — [[0, 10]] → 1 room
•No overlaps — [[0, 5], [5, 10], [10, 15]] → 1 room (sequential)
•All overlap — [[0, 10], [0, 10], [0, 10]] → 3 rooms
•Nested intervals — [[0, 100], [10, 20], [30, 40]] → 2 rooms
•Back-to-back — [[0, 5], [5, 10]] → 1 room (ends and starts at same time)

edge_case_tests.py
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def test_meeting_rooms():
    """Comprehensive edge case tests."""
    from meeting_rooms import min_meeting_rooms_heap, min_meeting_rooms_sweep
    
    # Test both implementations
    for fn_name, fn in [("heap", min_meeting_rooms_heap), 
                        ("sweep", min_meeting_rooms_sweep)]:
        # Empty
        assert fn([]) == 0, f"{fn_name}: empty failed"
        
        # Single
        assert fn([[0, 10]]) == 1, f"{fn_name}: single failed"
        
        # No overlap (sequential)
        assert fn([[0, 5], [5, 10], [10, 15]]) == 1, f"{fn_name}: sequential failed"
        
        # All overlap (concurrent)
        assert fn([[0, 10], [0, 10], [0, 10]]) == 3, f"{fn_name}: concurrent failed"
        
        # Nested
        assert fn([[0, 100], [10, 20], [30, 40]]) == 2, f"{fn_name}: nested failed"
        
        # Back-to-back (boundary)
        assert fn([[0, 5], [5, 10]]) == 1, f"{fn_name}: back-to-back failed"
        
        # Complex example
        intervals = [[0, 30], [5, 10], [15, 20], [25, 35]]
        result = fn(intervals)
        assert result == 2, f"{fn_name}: complex failed, got {result}"
        
        print(f"{fn_name}: All tests passed!")
 
 
if __name__ == "__main__":
    test_meeting_rooms()

Summary: Meeting Rooms Mastery

Meeting rooms problems transform interval scheduling from selection to resource allocation. We've moved from "how many can I fit?" to "how many resources do I need to fit all?"

Key Takeaways

•Meeting Rooms I — Conflict detection: sort by start, check consecutive pairs for overlap. O(n log n).
•Meeting Rooms II — Resource counting: find maximum simultaneous overlap. O(n log n).
•Sweep approach — Treat starts/ends as events, walk timeline tracking room count.
•Heap approach — Simulate room assignment, track earliest-ending room for reuse.
•Maximum overlap = minimum rooms — The peak concurrent count determines resource needs.
•Tie-breaking matters — End events before start events at same time (room becomes free before next uses it).

Coming Up Next:

Meeting rooms ask "how many resources in total?" But some problems flip this: given a fixed number of resources, can we serve all requests? Or: what's the minimum resources to guarantee we can always serve requests (worst-case analysis)? The Minimum Platforms problem explores this angle—same core logic, different phrasing, new insights.

Page Complete

You've mastered meeting rooms problems—both the conflict detection (Meeting Rooms I) and resource counting (Meeting Rooms II) variants. You understand two algorithmic approaches (sweep and heap) and can recognize this pattern across domains. Next, we explore the minimum platforms problem—a railway-station classic that's structurally identical.