Measure Meeting Coverage and Required Rooms
Company: Flexport
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
# Measure Meeting Coverage and Required Rooms
Given meeting intervals, compute both the total amount of time spent in at least one meeting and the minimum number of rooms needed to hold every meeting.
~~~python
def meeting_metrics(intervals: list[list[int]]) -> list[int]:
...
~~~
Each interval is [start, end] and represents the half-open range [start, end). Return [covered_time, minimum_rooms].
## Exact Semantics
- Intervals may be unsorted and may be duplicated.
- Every interval must contain two integers with start < end.
- Meetings that only touch, such as [1, 3) and [3, 5), do not overlap and may use the same room.
- Covered time counts overlapping portions once.
- Duplicate meetings are distinct meetings for the room calculation.
- For an empty input, return [0, 0].
- Malformed intervals or boolean endpoints must raise ValueError.
- The output contains exact integers and is compared exactly.
## Constraints
- 0 <= len(intervals) <= 200000
- -10**12 <= start < end <= 10**12
- Target O(n log n) time or better and O(n) auxiliary space or better.
## Examples
~~~text
Input: [[0, 30], [5, 10], [15, 20], [30, 40]]
Output: [40, 2]
Input: [[1, 2], [1, 2], [2, 3]]
Output: [2, 2]
Input: []
Output: [0, 0]
~~~
## Hints
- The two requested metrics use related interval events but have different aggregation rules.
- Decide how an end event and a start event at the same timestamp should be ordered.
Quick Answer: Compute the union length of meeting intervals and the minimum number of rooms needed. Respect half-open boundaries, duplicate meetings, touching endpoints, malformed inputs, and exact integer results in O(n log n) time.
For half-open meeting intervals, return total time covered by at least one meeting and the minimum rooms required to host all meetings. Touching intervals share a room; duplicate intervals count separately for rooms.
Constraints
- Each interval is a two-integer list with start < end.
- Boolean endpoints are invalid.
- Intervals may be unsorted and duplicated.
- Touching intervals do not overlap for room usage.
- Malformed intervals raise ValueError.
Examples
Input: ([[0, 30], [5, 10], [15, 20], [30, 40]],)
Expected Output: [40, 2]
Explanation: Overlaps count once for coverage and require two rooms.
Input: ([[1, 2], [1, 2], [2, 3]],)
Expected Output: [2, 2]
Explanation: Duplicate meetings need separate rooms while a touching meeting reuses one.
Hints
- Merge sorted intervals to measure union length.
- For rooms, sweep start and end events.
- At the same timestamp, process an end before a start.