Maintained by Vikas Dulgunde, 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.
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.
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.
The value 4 lands in the gap between [1,3] and [5,10], so nothing covers it and the answer is -1.
Visible test cases
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.
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.
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.
For each query, scan every interval and keep the smallest length that covers it.
Process queries in increasing order; a min-heap keyed on interval length always exposes the smallest currently-valid interval, with stale intervals dropped lazily.