Katkat
Back

Compute the Minimum Number of Meeting Rooms

AmazonSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manage overlapping time intervals efficiently, requiring an understanding of sorting or priority queues to track resource utilization.

Problem Statement

Given an array of meeting time intervals where each interval consists of a start time and an end time [start, end], determine the minimum number of conference rooms required to accommodate all meetings. A meeting occurs in the half-open interval [start, end), meaning that if one meeting ends at time t, another meeting can begin at exactly time t in the same room.

Function Signature

def min_meeting_rooms(intervals: List[List[int]]) -> int:

Constraints

  • 1 <= intervals.length <= 10^4
  • 0 <= start < end <= 10^6

Examples

Example 1: Input: [[0, 30], [5, 10], [15, 20]] Output: 2 Explanation: One room is used for [0, 30]. Another room is needed for [5, 10] and [15, 20], as they overlap or share the same timeline.

Example 2: Input: [[7, 10], [2, 4]] Output: 1 Explanation: These meetings do not overlap.

Edge Cases

  • Empty list of intervals (should return 0).
  • Meetings where one starts exactly when another ends.
  • Multiple identical time intervals.

Hints

Hint 1

Consider processing the start and end times separately to track the flow of meetings entering and leaving rooms.

Hint 2

If you sort both start times and end times, you can use two pointers to iterate through them and determine how many rooms are occupied at any given time.

Hint 3

Alternatively, a min-priority queue can keep track of the end times of meetings currently occupying rooms.

Follow-up questions

  • What is the time and space complexity of your solution, and can it be optimized further?
  • How would your approach change if you were asked to return the actual schedule (which meeting is in which room) instead of just the count?
  • If the meetings were not half-open intervals but fully closed intervals (e.g., [start, end] where [2, 3] and [3, 4] conflict), how would that change your implementation?