Minimum Interval to Include Each Query
Part of Practice: Rooms & Queries
You are given a list of intervals, each a pair [left, right] whose size is right - left + 1, and a list of integer queries. For each query q, find the SMALLEST interval that contains q (meaning left <= q <= right) and report its size, or -1 if no interval contains q. Return the answers in the original query order.
Constraints that matter: up to 100,000 intervals and 100,000 queries, so answering each query by scanning all intervals (O(n · q)) is roughly 10 billion operations — far too slow. Sorting both sides and sharing work across queries is the way in.
Examples
- Input:
- intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
- Output:
- [3, 3, 1, 4]
Query 2 fits in [1,4] (size 4) and [2,4] (size 3): answer 3. Query 4 fits in all four; the smallest is [4,4] with size 1. Query 5 fits only in [3,6]: size 4.
- Input:
- intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]
- Output:
- [2, -1, 4, 6]
No interval contains 19, so that query answers -1.
- Input:
- intervals = [[1,1]], queries = [1, 2]
- Output:
- [1, -1]
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.