Intervals with Exactly X Concurrent Meetings
GoogleSoftware Engineer · OnsiteLast updated
Implement an algorithm to identify all maximal time intervals during which exactly X meetings overlap, using a sweep-line technique over half-open intervals.
Problem Statement
You are given a list of meeting intervals, where each interval is represented as a half-open range [start, end) (the meeting is active at start and ends strictly before end), and a non-negative integer x.
Your task is to find all maximal half-open intervals [s, e) within the observation window [min_start, max_end] during which exactly x meetings are concurrently active.
Here, min_start is the earliest start time among all input meetings, and max_end is the latest end time among all input meetings. If the input list is empty, return an empty list.
The returned intervals must be pairwise disjoint, non-empty (`s list[list[int]]: pass
## Input & Output Format
- **Input**:
- `intervals`: A list of lists of two integers `[start, end]`, where `start < end`.
- `x`: A non-negative integer representing the exact count of concurrent meetings.
- **Output**: A list of lists of two integers `[s, e]` representing the time intervals where active meeting count equals `x`.
## Examples
### Example 1
```python
Input: intervals = [[1, 5], [2, 6], [4, 8], [7, 9]], x = 2
Output: [[2, 4], [5, 6], [7, 8]]
Explanation:
[1, 2): 1 meeting active ([1, 5))[2, 4): 2 meetings active ([1, 5),[2, 6))[4, 5): 3 meetings active ([1, 5),[2, 6),[4, 8))[5, 6): 2 meetings active ([2, 6),[4, 8))[6, 7): 1 meeting active ([4, 8))[7, 8): 2 meetings active ([4, 8),[7, 9))[8, 9): 1 meeting active ([7, 9))
Intervals with count = 2 are [2, 4], [5, 6], and [7, 8].
Example 2
Input: intervals = [[1, 4], [6, 10]], x = 0
Output: [[4, 6]]
Explanation:
The observation domain is [min_start, max_end] = [1, 10]. Between time 4 and 6, 0 meetings are active.
Constraints
0 <= len(intervals) <= 10^5intervals[i].length == 2-10^9 <= intervals[i][0] < intervals[i][1] <= 10^90 <= x <= 10^5
Hints
Hint 1
Model the problem as a sweep-line algorithm by creating discrete events for every start (+1) and end (-1) time point.
Hint 2
Sort the distinct time points; between any two consecutive sorted time points t[i] and t[i+1], the number of active meetings is constant.
Hint 3
Aggregate consecutive segments where the active count equals x, ensuring you only consider times within [min_start, max_end].
Follow-up questions
- How would you handle an online stream of meeting intervals where intervals are dynamically added or removed?
- If the query value X is not known in advance and you need to answer multiple queries for different X values efficiently, what data structure would you use?
- How would you adapt your algorithm if meetings had fractional weights instead of unit counts and you needed intervals where total weight is within [W_min, W_max]?
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.