Skip to main content

Minimum Interval Covering All Targets

hard
IntervalsArraySortingHeapLine SweepIntervals Sweep LineTop K HeapGreedy Interval
Asked atGoogleMetaAmazonCitadelBloomberg

Problem Description

You are given a 2-D array `ranges` of intervals `[leftI, rightI]` and an array of integer query points `targets`. For each target, find the length of the **smallest** interval (measured as `rightI - leftI + 1`) that contains the target. If no interval covers the target, return `-1` for that query.

**Example 1:**
```
Input: ranges = [[1,4],[2,4],[3,6],[4,4]], targets = [2,3,4,5]
Output: [3,3,1,4]
Explanation:
target 2: covered by [1,4](len 4) and [2,4](len 3) -> smallest is 3
target 3: covered by [1,4](len 4), [2,4](len 3), [3,6](len 4) -> smallest is 3
target 4: covered by [1,4],[2,4],[3,6],[4,4](len 1) -> smallest is 1
target 5: covered by [3,6](len 4) -> 4
```

**Example 2:**
```
Input: ranges = [[2,3],[2,5],[1,8],[20,25]], targets = [1,2,3,10,22]
Output: [8,2,2,-1,6]
```

Constraints

  • 1 <= ranges.length <= 10^5
  • 1 <= targets.length <= 10^5
  • 1 <= leftI <= rightI <= 10^7
  • 1 <= targets[i] <= 10^7

Follow-up

Can you solve this problem online (one query at a time) without presorting the queries, while still achieving O(log n) per query?

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.