Minimum Interval to Include Each Query

Hard· Sorting· Heap· Offline Queries

Problem

You are given intervals [left, right], where an interval's size is right - left + 1, and a list of query points. For each query, return the size of the smallest interval that contains it, or -1 if no interval does.

Examples

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

Output: [3,3,1,4]

Query 4 is covered by [4,4] of size 1; query 5 only by [3,6] of size 4.

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

Output: [2,-1,4,6]

Constraints

• 1 <= intervals.length, queries.length <= 10^5
• 1 <= left <= right <= 10^7
• 1 <= queries[j] <= 10^7

Hints & approach

Hint 1

Answering queries in sorted order lets you reuse work between them.

Hint 2

Sort intervals by left; as the query value grows, add every interval that has started.

Hint 3

Keep candidates in a min-heap keyed by size, and lazily drop ones whose right end is below the query.

Approachtry the hints first

Sort intervals by left and process queries in increasing order, remembering their original positions. For each query q, push every interval with left <= q onto a min-heap as (size, right). Then pop from the heap while the top's right < q, since those intervals ended before q and can never help later queries. The heap top, if any, is the smallest interval covering q; otherwise the answer is -1. Write each answer back to its original index.

Time O(n log n + q log q) · Space O(n + q)

← PreviousMinimum Number of Arrows to Burst Balloons DoneBack to Intervals