Intervals with Exactly X Concurrent Meetings
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Intervals with Exactly X Concurrent Meetings
Given half-open meeting intervals and an integer X, return every maximal half-open time interval during which exactly X meetings are active, restricted to the finite observation domain from the minimum meeting start through the maximum meeting end. A meeting ending at time t is not active at t, while a meeting starting at t is active. Return intervals sorted by start time and merge adjacent output intervals when the active count remains X across their boundary. If there are no meetings, return an empty list for every X.
## Function Contract
Implement `intervals_with_concurrency(starts, ends, x) -> list[list[int]]`.
## Constraints
- 0 <= number of meetings <= 200000.
- 0 <= start < end <= 10^9 for every meeting.
- 0 <= x <= number of meetings.
- Zero-length output intervals must not be returned.
- Spans before the minimum start and at or after the maximum end are outside the observation domain.
## Examples
```text
starts = [1, 2, 4], ends = [5, 6, 7], x = 2
output = [[2, 4], [5, 6]]
```
```text
starts = [1, 5], ends = [2, 7], x = 0
output = [[2, 5]]
```
```hint Test a shared boundary
Include one meeting ending exactly when another starts and verify the half-open convention at that timestamp.
```
```hint Exercise zero concurrency
Use two separated meetings and check that only the finite gap inside the observation domain is returned when X is zero.
```
Quick Answer: Given half-open meeting intervals and an integer X, return every maximal half-open time interval during which exactly X meetings are active, restricted to the finite observation domain from the minimum meeting start through the maximum meeting end. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
Given half-open meeting intervals `[start, end)` and an integer `x`, return every maximal half-open interval during which exactly `x` meetings are active. Restrict the result to the observation domain from the minimum meeting start through the maximum meeting end. Process all starts and ends at a timestamp as one boundary, and merge adjacent output spans when the active count remains `x`. Return spans in ascending start order, without zero-length intervals.
Constraints
- 0 <= len(starts) = len(ends) <= 200000.
- 0 <= starts[i] < ends[i] <= 10^9 for every meeting.
- 0 <= x <= len(starts); intervals are half-open and output spans must have positive length.
Examples
Input: ([], [], 0)
Expected Output: []
Explanation: An empty meeting set always returns an empty result.
Input: ([1, 2, 4], [5, 6, 7], 2)
Expected Output: [[2, 4], [5, 6]]
Explanation: The active count is exactly two on two disjoint maximal spans.
Hints
- Test a shared timestamp where one meeting ends and another begins.
- For x = 0, use separated meetings and check only the finite gap inside the observation domain.
- Include adjacent spans where the exact active count stays x across their common boundary.