TIC
The Interns Company

Meeting Rooms II

MediumAcceptance: 46.8%
ArraySortingHeapGreedy

Problem Statement

Given an array of meeting time intervals where intervals[i] = [starti, endi], find the minimum number of conference rooms required to hold all meetings.

Constraints:

  • 1 <= intervals.length <= 10^4
  • 0 <= starti < endi <= 10^6

Input Format:

  • An array of intervals representing meeting times

Output Format:

  • Return the minimum number of conference rooms required

Examples:

Example 1:

Input:

intervals = [[0,30],[5,10],[15,20]]

Output:

2

Explanation:

We need two conference rooms. One room for the meeting from [0,30], and another room for the meetings [5,10] and then [15,20].

Example 2:

Input:

intervals = [[7,10],[2,4]]

Output:

1

Explanation:

We only need one conference room. The meeting [2,4] ends before the meeting [7,10] starts.

Example 3:

Input:

intervals = [[1,5],[8,9],[8,15]]

Output:

2

Explanation:

We need two conference rooms. One for [1,5] and then [8,15], and another for [8,9].

Solutions

Min Heap Approach

Time: O(n log n) due to sorting and heap operations
Space: O(n) for the heap

Sort the intervals by start time. Use a min-heap to keep track of end times of meetings in progress. The size of the heap represents the number of rooms needed at any time.

Chronological Ordering

Time: O(n log n) due to sorting
Space: O(n) for storing separate start and end arrays

Separate start and end times, sort them, then simulate the timeline chronologically, incrementing room count at each start time and decrementing at each end time.

Algorithm Walkthrough

Example input: nums = []

Step-by-step execution:

  1. Sort intervals by start time: [[0, 30], [5, 10], [15, 20]]
  2. Start with one room for the first meeting [0, 30], min heap = [30]
  3. For [5, 10]: 5 < 30, need new room, min heap = [10, 30]
  4. For [15, 20]: 15 > 10, can reuse a room, min heap = [20, 30]
  5. Final number of rooms needed: 2

Hints

Hint 1
Think about the problem in terms of room allocation and deallocation.
Hint 2
What if you sort the intervals by start time?
Hint 3
You need to keep track of when meetings end to know if a room becomes available.
Hint 4
Consider using a min-heap to track the earliest ending meeting.

Video Tutorial

Meeting Rooms II - Heap Solution

YouTube•Learn the Meeting Rooms II solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the meeting intervals on a timeline to see overlaps and room allocations.

Key visualization elements:

  • active meetings
  • room allocation
  • room reuse

Similar Questions

Meeting Rooms

Easy

Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings. In other words, check if there are any overlapping intervals.

Merge Intervals

Medium

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Asked By

AmazonFacebookMicrosoftGoogleBloombergAppleUberTwitter

Implementation Notes

This is an important interview problem that tests understanding of interval scheduling and efficient data structures. The heap solution is elegant, keeping track of the earliest ending meeting to optimize room allocation.