Skip to main content

K-Interval Overlap Mapper

hard
ArrayHash TableSortingPrefix SumIntervalsPrefix SumDifference Array
Asked atGoogleAmazonMetaMicrosoftBloomberg

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.