253. Meeting Rooms II

Meeting Rooms II (LeetCode 253) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Heap (Priority Queue) Patterns pattern, in the Scheduling / Minimum Cost (Greedy with Priority Queue) subpattern.

• Blind 75 · #67 of 75 · Intervals
• NeetCode 150 · #134 of 150 · Intervals
• NeetCode 250 · #225 of 250 · Intervals

How to solve Meeting Rooms II

Meeting Rooms II is a Scheduling and Minimum Cost problem, part of Heap (Priority Queue) Patterns. Solve scheduling and optimization problems using priority queue with greedy approach.

Work towards the solution in these steps:

1. Think about how we would approach this problem in a very simplistic way. We will allocate rooms to meetings that occur earlier in the day v/s the ones that occur later on, right?
2. If you've figured out that we have to <b>sort</b> the meetings by their start time, the next thing to think about is how do we do the allocation? <br>There are two scenarios possible here for any meeting. Either there is no meeting room available and a new one has to be allocated, or a meeting room has freed up and this meeting can take place there.
3. An important thing to note is that we don't really care <b>which</b> room gets freed up while allocating a room for the current meeting. As long as a room is free, our job is done. <br><br>We already know the rooms we have allocated till now and we also know when are they due to get free because of the end times of the meetings going on in those rooms. We can simply check the room which is due to get vacated the earliest amongst all the allocated rooms.

The reference solution runs in O(n log n) time and O(1) space.

The Meeting Rooms II solution and editorial walks through the full approach with reference code.

Problem statement

You are given an array of meeting time intervals intervals where intervals[i] = [starti, endi] represents the start and end times of the ith meeting. All meetings are scheduled in the same building, and a meeting can use any available conference room.

Your task is to determine the minimum number of conference rooms required so that all meetings can take place without any overlaps (i.e., no two meetings are scheduled in the same room at the same time).

Return the minimum number of conference rooms required.

Constraints: - 1 <= intervals.length <= 10^4 - 0 <= starti < endi <= 10^6

Examples

Topics and companies

Topics: Array, Two Pointers, Greedy, Sorting, Heap (Priority Queue), Prefix Sum.

Reported in interviews at Amazon, Bloomberg, Facebook, Google, Microsoft, Oracle, Uber, Yandex, ByteDance, Twitter, Apple, Walmart Labs and others.

How to practise Meeting Rooms II on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n log n) time and O(1) space.

Open Meeting Rooms II in the code editor, or read the Meeting Rooms II editorial for a worked solution with its approach and complexity analysis.

Where Meeting Rooms II sits in the DSA pattern sheet

• Heap (Priority Queue) Patterns pattern guide
• Scheduling / Minimum Cost (Greedy with Priority Queue) subpattern
• The full DSA patterns sheet

Problems related to Meeting Rooms II

Other problems that use the same Scheduling / Minimum Cost (Greedy with Priority Queue) and Heap (Priority Queue) Patterns techniques:

• Furthest Building You Can Reach — Medium, same subpattern
• IPO — Hard, same subpattern
• Longest Happy String — Medium, same subpattern
• Maximum Average Pass Ratio — Medium, same subpattern
• Meeting Rooms III — Hard, same subpattern
• Minimum Cost to Hire K Workers — Hard, same subpattern

Meeting Rooms II FAQ