Compute minimum meeting rooms on circular day
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Onsite
## Problem
You are given a list of meetings scheduled within a 24-hour day. Time is **cyclic**: after `23:59` the next minute is `00:00`.
Each meeting is represented as `(start, end)` where `start` and `end` are times within the day (e.g., minutes from `0` to `1439`, or strings `HH:MM` you can convert to minutes).
- A meeting occupies the half-open interval **[start, end)**.
- If `end > start`, the meeting occurs within the same day.
- If `end <= start`, the meeting **wraps past midnight** (e.g., `23:00 -> 01:00`).
Two meetings overlap if their occupied time intervals intersect (considering wrap-around).
### Task
Return the **minimum number of conference rooms** required so that no overlapping meetings share a room.
### Examples
- Meetings: `[(60, 120), (90, 150)]` → overlaps → answer `2`.
- Meetings: `[(1380, 60), (30, 90)]` where `(1380, 60)` wraps midnight → overlaps with `(30, 90)` → answer `2`.
### Constraints
- `1 <= n <= 2 * 10^5`
- Times are within one day (0..1439) or equivalent.
### Follow-up
If the number of meetings is extremely large, how would you optimize the approach (time and/or space), given the timeline is only one day and thus bounded?
Quick Answer: This question evaluates a candidate's ability to reason about interval scheduling, circular time wrap-around, and resource allocation for overlapping events.
Meetings are half-open intervals on a cyclic 24-hour day. Return the maximum overlap, treating end <= start as wrapping past midnight and end == start as occupying the full day.
Constraints
- Times are minutes 0..1439 or HH:MM strings
Examples
Input: ([(60, 120), (90, 150)],)
Expected Output: 2
Input: ([(1380, 60), (30, 90)],)
Expected Output: 2
Input: ([('23:00', '01:00'), ('01:00', '02:00')],)
Expected Output: 1
Input: ([],)
Expected Output: 0
Hints
- Split wrapping intervals into two normal intervals on [0,1440).