Meeting Rooms: Multiple Solutions and Complexity Analysis

What is the Meeting Rooms Problem?

The Meeting Rooms problem is one of the most iconic interval scheduling challenges in algorithmic interviews and real-world software engineering. At its core, it asks: given a list of meeting times, how do we efficiently determine scheduling feasibility or resource allocation? The problem comes in two classic flavors:

• Meeting Rooms I — Can one person attend all meetings? (Detecting any overlap)
• Meeting Rooms II — What is the minimum number of conference rooms needed to host all meetings without conflict? (Maximum overlapping intervals)

These problems distill fundamental concepts like interval sorting, greedy algorithms, priority queues, and sweep-line techniques. Mastering them builds intuition for calendar systems, resource scheduling, load balancers, and any system that must handle concurrent time-bounded events.

Meeting Rooms I: Detecting Overlapping Intervals

Problem Statement

You are given an array of meeting intervals intervals where intervals[i] = [start_i, end_i]. Each start_i is the start time and end_i is the end time (exclusive — the meeting ends exactly at end_i, so a meeting ending at time X does not conflict with one starting at X). Determine if a single person can attend every meeting without any overlap. Return true if they can, false otherwise.

Solution: Sort and Linear Scan

The key insight is remarkably simple: if we sort all intervals by their start time, then for any two adjacent meetings in the sorted list, the earlier meeting must end before the later meeting starts. If we find even one pair where intervals[i-1].end > intervals[i].start, we have an overlap and the answer is false. If the entire scan completes without finding such a pair, all meetings are compatible.

Why does sorting by start time work? Because once sorted, the only possible overlap between non-adjacent meetings would already be caught by a chain of adjacent overlaps. The earliest meeting that conflicts with a later one will be adjacent to it in sorted order after we've detected intermediate conflicts.

Complexity Analysis

• Time Complexity: O(n log n) dominated by sorting, plus O(n) for the linear scan. Total: O(n log n).
• Space Complexity: O(1) if sorting in-place, or O(n) if the language's sort creates a copy. No additional data structures needed beyond a few variables.

Code Example (Python)

def canAttendAllMeetings(intervals):
    """
    Given a list of [start, end] intervals, return True if no meetings overlap.
    """
    if not intervals:
        return True
    
    # Sort by start time
    intervals.sort(key=lambda x: x[0])
    
    # Check adjacent pairs for overlap
    for i in range(1, len(intervals)):
        # If previous meeting ends after current meeting starts, conflict!
        if intervals[i-1][1] > intervals[i][0]:
            return False
    
    return True

# Example usage:
meetings = [[0, 30], [5, 10], [15, 20]]
print(canAttendAllMeetings(meetings))  # False (first overlaps with second)

meetings2 = [[7, 10], [2, 4], [15, 18]]
print(canAttendAllMeetings(meetings2))  # True (after sorting: [2,4], [7,10], [15,18] — no overlaps)

Notice the edge case handling: an empty list trivially returns True. The comparison uses strict inequality > because meetings ending exactly when another begins do not conflict.

Meeting Rooms II: Minimum Rooms Required

Problem Statement

Given an array of meeting time intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of conference rooms required so that every meeting can be held without overlap. A meeting that ends at time T frees its room, which can then be used by another meeting starting at exactly T.

This problem is significantly richer than Meeting Rooms I because it asks for a global resource count — the peak number of concurrent meetings at any point in time.

Solution 1: Chronological Ordering (Two Pointers on Split Arrays)

Instead of thinking about individual intervals, we can separate start times and end times into two sorted lists. Then we walk through time chronologically: whenever a meeting starts, we increment a counter (need a new room); whenever a meeting ends, we decrement (a room is freed). The maximum value the counter reaches during this walk is the answer.

This works because the exact pairing of which start belongs to which end doesn't matter for counting concurrent meetings — we just need to know, at each moment, whether more meetings have started than have ended.

Complexity Analysis (Solution 1)

• Time Complexity: O(n log n) for sorting both arrays, plus O(n) for the two-pointer walk. Total: O(n log n).
• Space Complexity: O(n) to store the separated start and end arrays.

Code Example — Chronological Ordering

def minMeetingRooms_v1(intervals):
    """
    Returns the minimum number of meeting rooms required.
    Uses separate sorted arrays for start and end times.
    """
    if not intervals:
        return 0
    
    n = len(intervals)
    starts = sorted([i[0] for i in intervals])
    ends = sorted([i[1] for i in intervals])
    
    rooms_needed = 0
    max_rooms = 0
    s_ptr = 0  # pointer for starts
    e_ptr = 0  # pointer for ends
    
    # Walk through all start times
    while s_ptr < n:
        if starts[s_ptr] < ends[e_ptr]:
            # A meeting starts before the earliest ending meeting finishes
            rooms_needed += 1
            max_rooms = max(max_rooms, rooms_needed)
            s_ptr += 1
        else:
            # A meeting ends, freeing a room before or exactly when another starts
            rooms_needed -= 1
            e_ptr += 1
    
    return max_rooms

# Example usage:
intervals = [[0, 30], [5, 10], [15, 20]]
print(minMeetingRooms_v1(intervals))  # 2

# Walkthrough:
# starts = [0, 5, 15], ends = [10, 20, 30]
# s_ptr=0 (0): 0 < 10? Yes → rooms=1, max=1, s_ptr=1
# s_ptr=1 (5): 5 < 10? Yes → rooms=2, max=2, s_ptr=2
# s_ptr=2 (15): 15 < 10? No → rooms=1, e_ptr=1
# s_ptr=2 (15): 15 < 20? Yes → rooms=2, max=2, s_ptr=3
# Loop ends, return 2

Solution 2: Min-Heap of End Times

This approach maintains a min-heap that tracks the end times of currently ongoing meetings (one entry per occupied room). The algorithm sorts intervals by start time, then processes each meeting in order:

1. Before assigning a room for the current meeting, free all rooms whose meetings have ended (heap top ≤ current start).
2. Push the current meeting's end time onto the heap (allocating a room).
3. The size of the heap at any moment is the number of rooms currently in use. The maximum heap size encountered is the answer.

This method is more intuitive because it directly simulates room allocation and release, matching how a real scheduling system might work.

Complexity Analysis (Solution 2)

• Time Complexity: O(n log n) for sorting intervals, plus O(n log n) for heap operations (each push/pop is O(log n)). Total: O(n log n).
• Space Complexity: O(n) in the worst case for the heap (when all meetings overlap).

Code Example — Min-Heap

import heapq

def minMeetingRooms_v2(intervals):
    """
    Returns minimum rooms using a min-heap of ongoing meeting end times.
    """
    if not intervals:
        return 0
    
    # Sort intervals by start time
    intervals.sort(key=lambda x: x[0])
    
    heap = []  # stores end times of currently allocated rooms
    max_rooms = 0
    
    for meeting in intervals:
        start, end = meeting
        
        # Free rooms whose meetings have ended (end time <= current start)
        while heap and heap[0] <= start:
            heapq.heappop(heap)
        
        # Allocate a room for this meeting
        heapq.heappush(heap, end)
        
        # Update peak room usage
        max_rooms = max(max_rooms, len(heap))
    
    return max_rooms

# Example usage:
intervals = [[0, 30], [5, 10], [15, 20]]
print(minMeetingRooms_v2(intervals))  # 2

# Another example — all non-overlapping:
intervals2 = [[1, 3], [3, 5], [5, 7]]
print(minMeetingRooms_v2(intervals2))  # 1 (meetings can be chained end-to-start)

Solution 3: Sweep Line with Difference Array / Map

The sweep line approach treats every start time as a +1 event (room needed) and every end time as a -1 event (room freed). By aggregating these events in chronological order and maintaining a running sum, the maximum running sum gives the peak concurrent meetings — exactly the minimum rooms required.

This is elegant when time values are manageable or when using an ordered map (like a TreeMap in Java or a sorted dictionary in Python). The technique generalizes beautifully to problems involving many interval types.

Complexity Analysis (Solution 3)

• Time Complexity: O(n log n) if using a sorted map (insertions and sorting keys), or O(n + max_time) if the time range is bounded and we use an array (bucket sort style).
• Space Complexity: O(n) for the map of unique time points, or O(max_time) for an array approach.

Code Example — Sweep Line with Ordered Map

from collections import defaultdict

def minMeetingRooms_v3(intervals):
    """
    Returns minimum rooms using a sweep line / difference map approach.
    """
    if not intervals:
        return 0
    
    # Build a dictionary mapping time -> net change in rooms
    timeline = defaultdict(int)
    
    for start, end in intervals:
        timeline[start] += 1   # room needed at start
        timeline[end] -= 1     # room freed at end
    
    # Process events in chronological order
    rooms_in_use = 0
    max_rooms = 0
    
    for time_point in sorted(timeline.keys()):
        rooms_in_use += timeline[time_point]
        max_rooms = max(max_rooms, rooms_in_use)
    
    return max_rooms

# Example usage:
intervals = [[0, 30], [5, 10], [15, 20]]
print(minMeetingRooms_v3(intervals))  # 2

# Timeline events:
# time 0: +1  → rooms=1
# time 5: +1  → rooms=2  (peak!)
# time 10: -1 → rooms=1
# time 15: +1 → rooms=2  (peak again)
# time 20: -1 → rooms=1
# time 30: -1 → rooms=0
# Max = 2

When Time Range is Bounded (Array-Based Sweep Line)

If the problem guarantees that all start and end times fall within a small, known range (e.g., 0 to 10^5 or 0 to 1440 for minutes in a day), we can use a flat array instead of a map, achieving O(n + range) time:

def minMeetingRooms_array_sweep(intervals, max_time=100000):
    """
    Array-based sweep line for bounded time ranges.
    Assumes times are integers in [0, max_time].
    """
    if not intervals:
        return 0
    
    # Initialize difference array
    timeline = [0] * (max_time + 2)  # +2 to safely handle end time at max_time
    
    for start, end in intervals:
        timeline[start] += 1
        timeline[end] -= 1
    
    rooms_in_use = 0
    max_rooms = 0
    
    # Walk through each time unit
    for change in timeline:
        rooms_in_use += change
        max_rooms = max(max_rooms, rooms_in_use)
    
    return max_rooms

# Example with time range 0-50:
meetings = [[10, 25], [15, 30], [20, 35]]
print(minMeetingRooms_array_sweep(meetings, max_time=50))  # 3 (all overlap at t=20)

Comparing the Solutions Side by Side

Here is a summary comparison of the approaches for Meeting Rooms II:

Why These Problems Matter

The Meeting Rooms problems are not just academic exercises — they model real-world scenarios that engineers encounter daily:

• Calendar Systems: Google Calendar, Outlook, and similar apps must detect conflicts when users schedule events (Meeting Rooms I) and display busy/available time slots (Meeting Rooms II).
• Resource Allocation: Cloud computing schedulers allocate VM instances, database connections, or worker threads to handle concurrent tasks. The peak concurrent task count maps directly to Meeting Rooms II.
• Load Balancers: Determining how many backend servers must be provisioned to handle peak concurrent requests follows the same pattern.
• Hotel Booking / Car Rental: Systems must compute how many units of a resource are needed given overlapping reservation intervals.
• CPU Scheduling: Operating system process schedulers manage overlapping execution windows and context switches using interval logic.

Understanding these solutions equips you with a toolkit of patterns — sorting + greedy, heap-based simulation, and sweep-line difference arrays — that transfer directly to harder interval problems like merging intervals, inserting intervals, finding maximum overlap, and partitioning labels.

Best Practices When Solving Interval Problems

1. Always Clarify Boundary Semantics

Before writing a single line of code, confirm whether intervals are inclusive or exclusive on their endpoints. The classic Meeting Rooms convention is that [start, end) is half-open — a meeting ending at time T does not conflict with one starting at T. Using the wrong comparison operator (>= vs >) can introduce subtle bugs that are hard to spot.

# CORRECT for half-open intervals [start, end):
if prev_end > current_start:  # overlap exists

# CORRECT for closed intervals [start, end]:
if prev_end >= current_start:  # overlap exists

2. Sort Before Processing

Almost every interval problem benefits from sorting intervals by start time (or by end time, depending on the goal). Sorting imposes a chronological order that lets greedy choices be optimal. Never try to process intervals in their raw input order unless the problem explicitly requires it.

3. Choose the Right Data Structure

• Use a min-heap when you need to repeatedly find the earliest ending meeting among a dynamic set.
• Use separate sorted arrays with two pointers when you only need aggregate counts, not specific pairings.
• Use a difference map / sweep line when you need to reconstruct the full timeline of events or handle multiple event types.

4. Handle Edge Cases Explicitly

Always test with:

• Empty input: Should return 0 or true depending on the problem.
• Single meeting: Trivially needs 1 room or is always attendable.
• All non-overlapping: Rooms needed = 1.
• All overlapping at the same time: Rooms needed = n.
• Meetings that chain end-to-start: [0,5], [5,10], [10,15] should need only 1 room.
• Duplicate intervals: [0,10] and [0,10] should count as 2 rooms.

5. Prefer Simplicity in Interview Settings

For Meeting Rooms I, the sort-and-scan approach is optimal and concise. For Meeting Rooms II, the chronological ordering (split arrays) or min-heap approaches are both O(n log n) and easy to explain step by step. The sweep-line with a map is elegant but may require explaining dictionary ordering guarantees. Choose the approach you can code flawlessly and justify clearly.

6. Watch Out for Large Input Sizes

When n is large (e.g., 10^5 or 10^6), O(n log n) is fine, but O(n + range) with an array sweep can be faster if the time range is small. If the time range is huge (e.g., timestamps spanning years), avoid the array approach — it will exhaust memory. Use the map-based sweep line or min-heap instead.

Extended Example: Putting It All Together

Below is a complete, production-style function that chooses the best strategy based on input characteristics. It demonstrates how to combine multiple approaches in real code:

import heapq
from collections import defaultdict

def min_meeting_rooms(intervals, strategy='auto', max_time=None):
    """
    Compute minimum meeting rooms required.
    
    Args:
        intervals: List of [start, end] pairs (integers).
        strategy: 'heap', 'two_pointer', 'sweep_map', 'sweep_array', or 'auto'.
        max_time: Maximum possible time value (required for 'sweep_array').
    
    Returns:
        Minimum number of rooms needed.
    """
    if not intervals:
        return 0
    
    n = len(intervals)
    
    # Auto-select strategy based on input characteristics
    if strategy == 'auto':
        if max_time is not None and max_time <= 100000 and n > 1000:
            strategy = 'sweep_array'
        else:
            strategy = 'heap'
    
    if strategy == 'two_pointer':
        starts = sorted(i[0] for i in intervals)
        ends = sorted(i[1] for i in intervals)
        rooms = 0
        max_rooms = 0
        s, e = 0, 0
        while s < n:
            if starts[s] < ends[e]:
                rooms += 1
                max_rooms = max(max_rooms, rooms)
                s += 1
            else:
                rooms -= 1
                e += 1
        return max_rooms
    
    elif strategy == 'heap':
        intervals.sort(key=lambda x: x[0])
        heap = []
        max_rooms = 0
        for start, end in intervals:
            while heap and heap[0] <= start:
                heapq.heappop(heap)
            heapq.heappush(heap, end)
            max_rooms = max(max_rooms, len(heap))
        return max_rooms
    
    elif strategy == 'sweep_map':
        timeline = defaultdict(int)
        for start, end in intervals:
            timeline[start] += 1
            timeline[end] -= 1
        rooms = 0
        max_rooms = 0
        for point in sorted(timeline.keys()):
            rooms += timeline[point]
            max_rooms = max(max_rooms, rooms)
        return max_rooms
    
    elif strategy == 'sweep_array':
        if max_time is None:
            raise ValueError("max_time required for sweep_array strategy")
        timeline = [0] * (max_time + 2)
        for start, end in intervals:
            timeline[start] += 1
            timeline[end] -= 1
        rooms = 0
        max_rooms = 0
        for delta in timeline:
            rooms += delta
            max_rooms = max(max_rooms, rooms)
        return max_rooms
    
    else:
        raise ValueError(f"Unknown strategy: {strategy}")

# Comprehensive test cases
test_cases = [
    ([], 0),
    ([[5, 10]], 1),
    ([[0, 30], [5, 10], [15, 20]], 2),
    ([[7, 10], [2, 4], [15, 18]], 1),
    ([[0, 5], [5, 10], [10, 15]], 1),
    ([[0, 10], [0, 10], [0, 10]], 3),
    ([[1, 5], [2, 6], [3, 7], [4, 8]], 4),
]

for intervals, expected in test_cases:
    result = min_meeting_rooms(intervals, strategy='heap')
    assert result == expected, f"Failed: {intervals} → got {result}, expected {expected}"
    print(f"✓ intervals={intervals}, rooms={result}")

print("\nAll tests passed!")

Conclusion

The Meeting Rooms problems are deceptively simple yet profoundly instructive. Meeting Rooms I teaches the foundational pattern of sort-then-scan that underpins virtually all interval algorithms. Meeting Rooms II escalates the challenge, opening up multiple valid solution paths — chronological two-pointer traversal, min-heap simulation, and sweep-line difference aggregation — each with identical asymptotic complexity but different practical trade-offs.

Mastering these approaches means you've internalized three powerful algorithmic patterns that recur across scheduling, resource allocation, and event-processing domains. When you next encounter a problem involving overlapping intervals, you'll recognize it as a variation on a theme and reach confidently for sorting, heaps, or sweep lines. The best solution is not just the one with optimal big-O notation, but the one you can implement correctly, explain clearly, and adapt as requirements evolve. Practice each variant, understand the boundary conditions deeply, and you'll transform interval anxiety into interval fluency.