LeetCode 253: Meeting Rooms II Solution

Master LeetCode problem 253 (Meeting Rooms II), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

253. Meeting Rooms II

Medium

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

Problem Explanation

Explanation

The Meeting Rooms II problem is a classic scheduling problem where we are given a list of meeting intervals and we need to find the minimum number of meeting rooms required to accommodate all meetings. We can solve this problem by using a priority queue to keep track of the end times of meetings currently happening. We iterate through the meetings sorted by start time and update the priority queue with the end times. If a meeting can be accommodated using an existing meeting room, we update the end time, otherwise, we add a new meeting room to the priority queue. The answer would be the size of the priority queue at the end.

Algorithm:

Sort the meeting intervals by start time.
Initialize a priority queue to keep track of the end times of meetings currently happening.
Iterate through the sorted meetings:
- If the start time of the meeting is greater than or equal to the end time of the earliest meeting in the priority queue, remove that meeting from the queue.
- Add the end time of the current meeting to the priority queue.
The size of the priority queue at the end is the minimum number of meeting rooms required.

Time Complexity: O(n log n) - for sorting the meetings by start time
Space Complexity: O(n) - for the priority queue to store the end times of meetings

Solution Code

import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return 0;
        }

        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> endTimes = new PriorityQueue<>();
        
        endTimes.offer(intervals[0][1]);
        
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= endTimes.peek()) {
                endTimes.poll();
            }
            endTimes.offer(intervals[i][1]);
        }
        
        return endTimes.size();
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 253 (Meeting Rooms II)?

This page provides optimized solutions for LeetCode problem 253 (Meeting Rooms II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 253 (Meeting Rooms II)?

The time complexity for LeetCode 253 (Meeting Rooms II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 253 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 253 in Java, C++, or Python.

Back to LeetCode Solutions