Minimum Interval to Include Each Query

Problem

You are given a list of closed intervals intervals, where intervals[i] = [left, right] has size right - left + 1, and a list of integer queries. For each query value q, find the smallest interval (by size) that contains q, i.e. with left <= q <= right, and report its size. If no interval contains q, report -1.

Return the answers in the same order as the queries.

• Up to around a hundred thousand intervals and the same for queries.
• Endpoints and query values are positive and fit comfortably in a normal int.

Examples

• intervals = [[2,5],[3,5],[4,9],[5,5]], queries = [3,4,5,6] → [3,3,1,6]. Query 3 is covered by [2,5] (size 4) and [3,5] (size 3); query 5 is covered by all four and the smallest is [5,5]; query 6 is only inside [4,9].
• intervals = [[3,4],[3,6],[2,9],[21,26]], queries = [3,20,6,23] → [2,-1,4,6]. Query 23 is only inside [21,26] (size 6); nothing covers 20.
• intervals = [[6,6]], queries = [6,7] → [1,-1].

Hints

1. Checking every interval for every query is O(n·q). What if you could answer the queries in a convenient order rather than the given one?
2. Sort the queries. As q grows, intervals become relevant (their left <= q) and later become irrelevant (their right < q). Which structure lets you always see the smallest relevant interval?
3. Sort intervals by left and queries ascending; sweep with a min-heap keyed by size, pushing intervals as their left is reached and lazily popping those whose right has passed.