46. Meeting Rooms II

Problem Description

Given an array of meeting time intervals, where each interval consists of a start time and an end time, determine the minimum number of conference rooms required to accommodate all the meetings without any overlaps.

Example:

Input: intervals = [(0,30),(5,10),(15,20)]
Output: 2
Explanation:
We need two meeting rooms:
- Room 1: (0,30)
- Room 2: (5,10),(15,20)

Solution Code

import java.util.*;

/**
 * Definition of Interval:
 * public class Interval {
 *     int start, end;
 *     Interval(int start, int end) {
 *         this.start = start;
 *         this.end = end;
 *     }
 * }
 */

public class Solution {
    /**
     * @param intervals: an array of meeting time intervals
     * @return: the minimum number of conference rooms required
     */
    public int minMeetingRooms(List<Interval> intervals) {
        if (intervals == null || intervals.size() == 0) {
            return 0;
        }

        // Sort intervals based on start time
        intervals.sort((a, b) -> a.start - b.start);

        // Use a min-heap to track the end times of meetings
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // Add the first meeting's end time to the heap
        minHeap.offer(intervals.get(0).end);

        for (int i = 1; i < intervals.size(); i++) {
            Interval current = intervals.get(i);

            // If the current meeting starts after the earliest ending meeting, reuse that room
            if (current.start >= minHeap.peek()) {
                minHeap.poll();
            }

            // Add the current meeting's end time to the heap
            minHeap.offer(current.end);
        }

        // The size of the heap is the number of rooms required
        return minHeap.size();
    }
}

Approach Name

Min-Heap (Priority Queue) Approach

Intuition

The problem can be solved by sorting the intervals based on their start times and then using a min-heap to keep track of the end times of the meetings. The min-heap allows us to efficiently determine if a new meeting can reuse a room that has just been freed up (i.e., the meeting with the earliest end time). If the new meeting starts after the earliest ending meeting, we can reuse that room; otherwise, we need a new room.

Algorithm

1. Sort Intervals:

   • Sort the intervals based on their start times.

2. Initialize Min-Heap:

   • Use a min-heap to store the end times of the meetings.

3. Iterate Through Intervals:

   • For each interval, check if the current meeting starts after the earliest ending meeting in the heap.
   • If it does, reuse that room by removing the earliest ending meeting from the heap.
   • Add the current meeting’s end time to the heap.

4. Determine Number of Rooms:

   • The size of the heap at the end represents the minimum number of rooms required.

Complexity Analysis

• Time Complexity: O(n log n), where n is the number of intervals. Sorting the intervals takes O(n log n), and each heap operation (insertion and deletion) takes O(log n).
• Space Complexity: O(n), in the worst case, the heap can store all the intervals if none of them overlap.

Leetcode Related Problems

1. Easy - 🔒 0252. Meeting Rooms
2. Easy - 2848. Points That Intersect With Cars
3. Hard - 2251. Number of Flowers in Full Bloom
4. Hard - 2402. Meeting Rooms III
5. Medium - 1094. Car Pooling
6. Medium - 2462. Total Cost to Hire K Workers
7. Medium - 0452. Minimum Number of Arrows to Burst Balloons
8. Medium - 0056. Merge Intervals

GeeksForGeeks Related Problems

1. Easy - 705114. Required Rooms Related Articles: Euclidean Algorithms - Basic and Extended
2. Medium - 876431. Meeting Rooms II Related Articles: Euclidean Algorithms - Basic and Extended

LintCode Related Problems

1. Easy - 0156. Merge Intervals
2. Easy - 0920. Meeting Rooms