Katkat
Back

Minimum Number of Rooms to Host Overlapping Meetings

MicrosoftSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

A scheduling problem that asks for the fewest rooms needed to hold a set of meetings given as half-open time intervals, where a room freed at a given moment can be reused immediately. It tests interval reasoning, correct handling of shared endpoints and duplicates, and an efficient solution for large inputs.

You are given the schedule of n meetings for a single day. Meeting i occupies the half-open time interval [start_i, end_i): it starts at start_i and its room becomes free exactly at end_i. A room can host only one meeting at a time, and meetings cannot be moved, shortened or split. Return the minimum number of rooms needed so that every meeting takes place at its scheduled time.

Function Signature

def min_rooms(meetings: List[List[int]]) -> int:

Rules

  • meetings[i] = [start_i, end_i].
  • A meeting that ends at time t and a meeting that starts at time t do not overlap, so they can use the same room.
  • The input is not sorted and may contain identical meetings; each one needs its own room while it runs.
  • Return 0 when there are no meetings.

Constraints

  • 0 <= n <= 10^5
  • 0 <= start_i < end_i <= 10^9

Examples

Example 1

meetings = [[1, 5], [2, 6], [5, 8], [9, 12]]
output = 2

The first two meetings overlap during [2, 5). The meeting that starts at 5 can take the room freed at 5, and the last meeting starts after every other meeting has ended.

Example 2

meetings = [[3, 7], [3, 7], [3, 7]]
output = 3

Example 3

meetings = [[10, 20]]
output = 1