K-Interval Overlap Mapper
Problem Description
You are given `n` intervals, each represented as `[start, end]` (inclusive), and an integer `queryCount`. For each query `q` (an integer), determine **how many of the given intervals contain `q`** (i.e., `start <= q <= end`).
Return an array of length `queryCount` where the `i`-th element is the count of intervals containing `queries[i]`.
Use a **difference-array / sweep-line** approach for efficient batch processing.
**Example 1:**
```
Input: intervals = [[1,4],[2,6],[3,5]], queries = [2, 3, 6, 7]
Output: [2, 3, 1, 0]
Explanation:
query=2: covered by [1,4] and [2,6] → 2
query=3: covered by [1,4],[2,6],[3,5] → 3
query=6: covered by [2,6] → 1
query=7: no interval → 0
```
**Example 2:**
```
Input: intervals = [[5,10],[1,3],[8,12]], queries = [5, 1, 11, 4]
Output: [1, 1, 1, 0]
Explanation:
query=5: [5,10] → 1
query=1: [1,3] → 1
query=11: [8,12] → 1
query=4: none → 0
```
Constraints
- 1 <= intervals.length <= 10^5
- 1 <= queries.length <= 10^5
- 0 <= intervals[i][0] <= intervals[i][1] <= 10^6
- 0 <= queries[i] <= 10^6
Follow-up
If the interval endpoints can be up to 10^18, the difference-array approach is infeasible. How would you adapt the solution using coordinate compression?
Hints
Try the problem first. If you get stuck, you can reveal hints one at a time.
Solution
Leaderboard
No entries yet for python.
Be the first — submit an accepted solution.