Analyze Overlap in Closed Intervals
Company: Netflix
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Implement `closed_interval_overlap(intervals, query_points)`.
Each interval `[start, end]` is closed, so it contains both endpoints. Return `[[maximum_overlap], query_counts]`, a uniform list of integer lists. `maximum_overlap` is the largest number of intervals covering any point and `query_counts[i]` is the number covering `query_points[i]`.
### Constraints
- `0 <= len(intervals), len(query_points) <= 200000`
- `-10^9 <= start <= end <= 10^9`
- Intervals and query points may be unsorted and may contain duplicates.
- Return `0` as the maximum for an empty interval list.
### Example
For `intervals = [[1,3], [3,5], [3,3]]` and `query_points = [0,3,4]`, return `[[3], [0,3,1]]` because all three closed intervals include point `3`.
```hint Probe equality cases
Test a zero-length interval and queries placed exactly at both endpoints of another interval.
```
```hint Keep duplicates visible
Repeated intervals and repeated query points still contribute independently under the stated contract.
```
Quick Answer: Implement `closed_interval_overlap(intervals, query_points)`. Work through the function contract, boundary cases, correctness argument, and time and space complexity expected in a production-quality solution.
Given closed integer intervals and query points, return `[[maximum_overlap], query_counts]`. The first record contains the largest number of intervals covering any point. `query_counts[i]` is the number covering `query_points[i]`, preserving query order and duplicates. Empty intervals have maximum zero.
Constraints
- 0 <= len(intervals), len(query_points) <= 200000.
- Each interval is [start, end] with -10^9 <= start <= end <= 10^9.
- Intervals are closed; intervals and queries may be unsorted and contain duplicates.
- Return [[maximum_overlap], query_counts] and use zero maximum for an empty interval list.
Examples
Input: ([], [])
Expected Output: [[0], []]
Explanation: Empty intervals and queries return maximum zero and an empty count list.
Input: ([], [0, 0, -1])
Expected Output: [[0], [0, 0, 0]]
Explanation: Queries remain distinct outputs even when repeated, with zero coverage.
Hints
- Test empty inputs, no queries, and a zero-length interval.
- Place queries exactly at both endpoints and at an endpoint shared by several intervals.
- Include duplicate intervals, repeated queries, negative values, and both coordinate limits.