Meeting Rooms II - Practice Coding Problems

Meeting Rooms II - Problem

Array Two Pointers Greedy Sorting Heap (Priority Queue) Prefix Sum Medium

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

You need to determine the maximum number of meetings that are happening at the same time, which equals the minimum number of rooms needed.

For example, if meetings are [[0,30],[5,10],[15,20]], we need 2 rooms because meetings [0,30] and [5,10] overlap.

Input & Output

Example 1 — Basic Overlapping

$ Input: intervals = [[0,30],[5,10],[15,20]]

› Output: 2

💡 Note: Meeting [0,30] overlaps with both [5,10] and [15,20], but [5,10] and [15,20] don't overlap with each other. Maximum concurrent meetings is 2 (at times 5-10 and 15-20).

Example 2 — No Overlap

$ Input: intervals = [[7,10],[2,4]]

› Output: 1

💡 Note: The meetings don't overlap: [2,4] ends before [7,10] starts. Only 1 room needed since they can use the same room sequentially.

Example 3 — Adjacent Meetings

$ Input: intervals = [[1,5],[8,9],[8,9]]

› Output: 2

💡 Note: First meeting [1,5] doesn't overlap with others. The two [8,9] meetings start at exactly the same time, so we need 2 rooms for them.

Constraints

1 ≤ intervals.length ≤ 10⁴
0 ≤ start_i < end_i ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input Meetings

Given meeting time intervals [[0,30],[5,10],[15,20]]

Find Overlaps

Identify which meetings happen simultaneously

Count Rooms

Minimum rooms needed = maximum concurrent meetings

Key Takeaway

🎯 Key Insight: The minimum rooms needed equals the maximum number of meetings happening at any point in time

Asked in

G Google 85 f Facebook 72 a Amazon 68 M Microsoft 45 A Apple 38

The key insight is that we need to track the maximum number of meetings happening simultaneously. The optimal approach uses a min-heap to efficiently track end times of active meetings. Best approach: Min Heap - Time: O(n log n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Overlaps	O(n³)	O(n)	For each time point, count how many meetings are active
Min Heap - Track End Times	O(n log n)	O(n)	Use priority queue to efficiently track when meetings end
Two Pointers - Separate Events	O(n log n)	O(n)	Track start and end events separately, count active meetings

Brute Force - Check All Overlaps — Algorithm Steps

Find all unique start and end times
For each time point, count active meetings
Return the maximum count

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Times

Extract all start and end times

Count Active

For each time, count overlapping meetings

Maximum

Return highest count found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int intervals[][2], int n) {
    if (n == 0) return 0;
    
    // Get all unique time points
    int times[2000]; // Assuming reasonable bounds
    int timeCount = 0;
    
    for (int i = 0; i < n; i++) {
        // Add start time if not already present
        int found = 0;
        for (int j = 0; j < timeCount; j++) {
            if (times[j] == intervals[i][0]) {
                found = 1;
                break;
            }
        }
        if (!found) times[timeCount++] = intervals[i][0];
        
        // Add end time if not already present
        found = 0;
        for (int j = 0; j < timeCount; j++) {
            if (times[j] == intervals[i][1]) {
                found = 1;
                break;
            }
        }
        if (!found) times[timeCount++] = intervals[i][1];
    }
    
    int maxRooms = 0;
    // Check each time point
    for (int i = 0; i < timeCount; i++) {
        int activeMeetings = 0;
        for (int j = 0; j < n; j++) {
            if (intervals[j][0] <= times[i] && times[i] < intervals[j][1]) {
                activeMeetings++;
            }
        }
        if (activeMeetings > maxRooms) {
            maxRooms = activeMeetings;
        }
    }
    
    return maxRooms;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int intervals[1000][2];
    int n = 0;
    
    // Simple parsing for [[a,b],[c,d]] format
    char* ptr = line + 1; // Skip first [
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            intervals[n][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++; // Skip comma
            intervals[n][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            ptr++; // Skip ]
            n++;
        } else {
            ptr++;
        }
    }
    
    int result = solution(intervals, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

For each of O(n) time points, we check all O(n) intervals, and finding time points takes O(n²)

⚠ Quadratic Growth

Space Complexity

O(n)

Store all unique time points in a set

⚡ Linearithmic Space

285.0K Views

High Frequency

~25 min Avg. Time

4.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Overlaps — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler