Skip to content

Approach Using Priority Queue

Intution

To determine the minimum number of conference rooms required, we need to track how many meetings are happening at the same time. If a meeting starts after or when another ends, we can reuse the same room.\

A min-heap (priority queue) is perfect for tracking the earliest meeting to end, so we can efficiently check and reuse rooms.

  • We sort all meetings by start time.
  • Then we use a min-heap (priority queue) to track the earliest ending meeting.
  • If a meeting can reuse a room (i.e., its start time is after or equal to the earliest end time), we pop that meeting from the heap.
  • Otherwise, we need a new room.

The size of the heap at any point gives us the number of rooms needed at that time. The maximum size reached is our answer

Complexity

Space Complexity Time Complexity
$\(\text{O}(N)\)$ $\(\text{O}(N*\log{N})\)$

Code

public int minMeetingRooms(int[][] meetingIntervals) {
    // Sort the meetings by start time
    Arrays.sort(meetingIntervals, (a, b) -> Integer.compare(a[0], b[0]));

    // Min-heap to track end times of ongoing meetings
    PriorityQueue<Integer> ongoingMeetingsEndTimes = new PriorityQueue<>();

    int maxRoomsRequired = 0;

    for (int i = 0; i < meetingIntervals.length; ++i) {
        int currentStart = meetingIntervals[i][0];
        int currentEnd = meetingIntervals[i][1];

        // Free up rooms that have ended before the current meeting starts
        while (!ongoingMeetingsEndTimes.isEmpty() && ongoingMeetingsEndTimes.peek() <= currentStart) {
            ongoingMeetingsEndTimes.poll(); // Room becomes available
        }

        // Allocate room for the current meeting
        ongoingMeetingsEndTimes.add(currentEnd);

        // Track the max number of rooms used simultaneously
        maxRoomsRequired = Math.max(maxRoomsRequired, ongoingMeetingsEndTimes.size());
    }

    return maxRoomsRequired;
}

Comments