Meeting Rooms II

Meeting Rooms II 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.

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

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), where n is the number of meetings. Both start and end arrays are sorted, which dominates the runtime. time and O(1) (excluding input storage), as only a few integer variables are used after sorting. 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
• All coding practice problems

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
• Maximum Average Pass Ratio — Medium, same subpattern
• Meeting Rooms III — Hard, same subpattern
• Minimum Cost to Hire K Workers — Hard, same subpattern
• Reorganize String — Medium, same subpattern
• Single-Threaded CPU — Medium, same subpattern