Minimum Meeting Room Required

253. Meeting Rooms II – LeetCode

Problem Statement

You are given an array of meeting time intervals intervals[][], where each interval has a start and end time: [start, end].

Your task is to return the minimum number of meeting rooms required so that no two meetings overlap.

Examples

Example 1:

Input: [[0,30],[5,10],[15,20]]
Output: 2
Explanation:
- [0,30] and [5,10] overlap → need 2 rooms
- [15,20] fits after [5,10] ends → still 2 rooms total

Example 2:

Input: [[7,10],[2,4]]
Output: 1
Explanation:
- No overlap → only 1 room needed

Intuition

This is a "maximum number of overlapping intervals" problem.
We must find the time point at which the most meetings are happening simultaneously.

This is a classic case for Line Sweep Algorithm (also known as the "timeline" or "chronological ordering" method).

Line Sweep Technique

Core Idea:

  1. Break each interval into two events:

    • A start event (when a meeting begins)

    • An end event (when a meeting ends)

  2. Sort all events chronologically:

    • If two events happen at the same time, prioritize end before start (to free the room before allocating it again)

  3. Traverse events:

    • Maintain a counter of ongoing meetings

    • Update maxRooms = max(maxRooms, ongoing)

Approach

  1. For each interval [start, end], add:

    • (start, +1) → meeting starts

    • (end, -1) → meeting ends

  2. Sort all events by time:

    • If times are equal, sort by type:

      • end (-1) comes before start (+1)

  3. Initialize ongoing = 0, maxRooms = 0

  4. Traverse the sorted events:

    • Add value (+1 or -1) to ongoing

    • Update maxRooms

Java Code (Line Sweep)

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        List<int[]> events = new ArrayList<>();

        // Step 1: Convert intervals to events
        for (int[] interval : intervals) {
            events.add(new int[]{interval[0], +1}); // start of meeting
            events.add(new int[]{interval[1], -1}); // end of meeting
        }

        // Step 2: Sort events by time, end before start if times equal
        events.sort((a, b) -> 
            a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]
        );

        int ongoing = 0;
        int maxRooms = 0;

        // Step 3: Traverse timeline
        for (int[] event : events) {
            ongoing += event[1]; // +1 or -1
            maxRooms = Math.max(maxRooms, ongoing);
        }

        return maxRooms;
    }
}

Time and Space Complexity

Metric Value
Time Complexity O(n log n)
Space Complexity O(n)

Dry Run

Input:

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

Events After Conversion:

[(0, +1), (30, -1),
 (5, +1), (10, -1),
 (15, +1), (20, -1)]

After Sorting:

[(0, +1), (5, +1), (10, -1), (15, +1), (20, -1), (30, -1)]

Sweep:

time = 0  → ongoing = 1
time = 5  → ongoing = 2
time = 10 → ongoing = 1
time = 15 → ongoing = 2
time = 20 → ongoing = 1
time = 30 → ongoing = 0

→ max ongoing = 2 → 2 rooms required

Conclusion

The Line Sweep method is one of the cleanest and most intuitive ways to solve problems involving interval overlaps. In this case, we: