Skip to main content
Ace Hired
All coding problems

Minimum Interval to Include Each Query

HardintervalsOffline sweep with a min-heap (line sweep + priority queue)intervalsheapsorting

Maintained by Vikas D, software engineer

You are handed a list of closed intervals, each written as [left, right], and a separate list of query points. Every interval covers all integers from its left endpoint to its right endpoint inclusive, and its length is right - left + 1.

For a single query value q, look at every interval whose range includes q (meaning left <= q <= right). Among those covering intervals, pick the one with the smallest length and report that length.

If no interval covers q at all, the answer for that query is -1. You must return one answer per query, in the original order the queries were given.

Examples

Input: intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
Output: [3,3,1,4]

Query 2 sits inside [1,4] (length 4) and [2,4] (length 3); the smaller is 3. Query 3 sits inside [1,4], [2,4], and [3,6], smallest length 3. Query 4 sits inside all four, and [4,4] has length 1. Query 5 sits only inside [3,6], length 4.

Input: intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]
Output: [2,-1,4,6]

Query 2 is covered by [2,3] (length 2), [2,5] (length 4), [1,8] (length 8); smallest is 2. Query 19 falls in no interval, so -1. Query 5 is covered by [2,5] (length 4) and [1,8] (length 8); smallest is 4. Query 22 is covered only by [20,25], length 6.

Input: intervals = [[5,10],[1,3]], queries = [4]
Output: [-1]

The value 4 lands in the gap between [1,3] and [5,10], so nothing covers it and the answer is -1.

Constraints

  • 1 <= intervals.length <= 10^5
  • 1 <= queries.length <= 10^5
  • intervals[i].length == 2
  • 1 <= left_i <= right_i <= 10^9
  • 1 <= queries[j] <= 10^9
  • Answers must be returned in the same order as the input queries.

Visible test cases

  • minIntervalQueries([[1,4],[2,4],[3,6],[4,4]], [2,3,4,5]) == [3,3,1,4]
  • minIntervalQueries([[2,3],[2,5],[1,8],[20,25]], [2,19,5,22]) == [2,-1,4,6]
  • minIntervalQueries([[1,2],[3,4]], [1,2,3,4]) == [2,2,2,2]
  • minIntervalQueries([[1,100]], [50]) == [100]
  • minIntervalQueries([[5,10],[1,3]], [4]) == [-1]

Hints

Hint 1

A naive scan checks every interval for every query. Think about what changes if you process queries in increasing value order so an interval, once it becomes relevant, stays relevant until its right endpoint is passed.

Hint 2

Sort intervals by their left endpoint and sort queries by value. Sweep through queries in order, and as the query value grows, add every interval whose left endpoint has been reached into a structure that lets you grab the smallest length quickly.

Hint 3

A min-heap keyed on interval length works. Before answering a query, lazily discard heap entries whose right endpoint is already less than the current query value, then the heap top is the smallest valid interval. Remember to map answers back to the original query order.

Loading the editor...

Approaches

Brute force

Time O(Q * N) where Q is the number of queries and N the number of intervals · Space O(1) beyond the output array

For each query, scan every interval and keep the smallest length that covers it.

  1. Create an answers array filled with -1.
  2. For each query value q, walk through all intervals.
  3. If left <= q <= right, compute right - left + 1 and track the running minimum.
  4. Store the minimum (or -1 if nothing covered q) at the query's position.

Offline sort plus min-heap (sweep)

Time O((N + Q) log(N + Q)) from the sorts and heap operations · Space O(N) for the heap

Process queries in increasing order; a min-heap keyed on interval length always exposes the smallest currently-valid interval, with stale intervals dropped lazily.

  1. Sort intervals ascending by left endpoint.
  2. Pair each query with its original index and sort these pairs by query value.
  3. Walk the sorted queries with a pointer into the sorted intervals. For the current query q, push every interval whose left endpoint is <= q onto a min-heap keyed by length, storing (length, right).
  4. Pop heap entries whose stored right endpoint is < q, since those intervals end before q and can never cover this or any later query.
  5. If the heap is non-empty, the top length is the answer; write it at the query's original index. Otherwise leave -1.

Common mistakes

  • Reporting the wrong quantity: the answer is the interval length right - left + 1, not the right endpoint or the index of the interval.
  • Forgetting to restore original order. Sorting queries to sweep is fine, but each answer must be written back at the query's original position.
  • Off-by-one on coverage. The interval is closed on both ends, so an interval with right == q still covers q; pop only when right < q, not right <= q.
  • Pushing intervals using a strict comparison on the left endpoint. An interval with left == q does cover q, so admit it with left <= q.
  • Eagerly deleting arbitrary heap entries instead of lazily discarding only the top while it is invalid, which breaks the heap invariant and the time bound.

Follow-up variations

  • What if queries arrive online (you must answer each before seeing the next)? A segment tree or an interval tree over compressed coordinates handles arbitrary query order.
  • What if you must return the actual smallest interval, not just its length? Carry the [left, right] pair through the heap instead of only the length.
  • How would you support adding and removing intervals between queries? A balanced BST or a segment tree keyed by length keeps the minimum updatable under modifications.
  • What changes for open intervals, or when you want the largest covering interval instead of the smallest?

Recommended problems

Build the rest of your prep