Tightest Covering Range
HardIntervals
Problem
A radio network has transmitters with coverage ranges, each [left, right] covering every integer kilometre marker from left to right inclusive. The size of a range is right - left + 1.
For each marker in queries, return the size of the smallest range that covers it, or -1 if none does. Answers must follow the order of queries.
Example 1
- Input:
- ranges = [[1, 4], [2, 4], [3, 6], [4, 4]], queries = [2, 3, 4, 5]
- Output:
- [3, 3, 1, 4]
Marker 2: [2, 4] (size 3) beats [1, 4] (size 4). Marker 4: [4, 4] has size 1. Marker 5: only [3, 6] covers it.
Example 2
- Input:
- ranges = [[2, 3], [2, 5], [1, 8], [20, 25]], queries = [2, 19, 5, 22]
- Output:
- [2, -1, 4, 6]
Constraints
- 1 ≤ ranges.length ≤ 10^5
- 0 ≤ queries.length ≤ 10^5
- 1 ≤ left ≤ right ≤ 10^9
- 1 ≤ queries[j] ≤ 10^9
Hint
Show the first hint
Checking every range for every query is n · q. Could the queries be answered in a convenient order instead?
Walkthrough
How to approach it
01Clarify before coding
- Is the size inclusive? Yes, right - left + 1, so [4, 4] has size 1.
- Can queries repeat or be unsorted? Yes, both; answers go back in input order.
- Can ranges repeat? Yes, harmless.
02Brute force
For each query, scan all ranges and keep the smallest one containing it.
Cost: O(n · q) time: 10^10 for 10^5 of each.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.