Katkat

Intervals with Exactly X Concurrent Meetings

GoogleSoftware Engineer · Onsite

Last 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^5
  • intervals[i].length == 2
  • -10^9 <= intervals[i][0] < intervals[i][1] <= 10^9
  • 0 <= 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]?