649/670

649. Minimum Interval to Include Each Query

Hard

You are given a list intervals where intervals[i] = [left, right] covers every integer from left to right inclusive, and a list of integer queries.

The size of an interval is the count of integers it covers: right − left + 1.

For each queries[j], determine the size of the smallest interval that contains the query point (an interval contains q when left <= q <= right). If no interval contains it, that query's answer is -1.

Return one answer per query, in the original query order.

Intervals over the number line (example 1)Example 1. Query 2 is covered by [1,3] and [2,5]; the smaller one has size 3. Query 6 is only covered by [4,8] (size 5), and nothing covers query 9, so it answers −1.

Example 1:

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

Output: [3, 4, 5, -1]

Explanation: Query 2 sits inside [1,3] (size 3) and [2,5] (size 4), so the answer is 3. Query 4 is inside [2,5] (size 4) and [4,8] (size 5) → 4. Query 6 is only inside [4,8] → 5. Nothing covers 9 → -1.

Example 2:

Input: intervals = [[2,3],[3,7],[1,9]], queries = [1,5,3]

Output: [9, 5, 2]

Explanation: Only [1,9] covers 1, so its size 9 is the answer. Query 5 is inside [3,7] (size 5) and [1,9] (size 9) → 5. Query 3 is inside all three; the smallest is [2,3] with size 2.

Constraints:

1 ≤ intervals.length ≤ 10⁵
1 ≤ queries.length ≤ 10⁵
1 ≤ left ≤ right ≤ 10⁷
1 ≤ queries[j] ≤ 10⁷

Hints:

Checking every interval for every query is O(m·k) and too slow at 10^5 each. Both arrays can be sorted — think about what processing queries in increasing order buys you.

Sweep queries from smallest to largest. Once an interval's left end is <= the current query it stays 'opened' for every later query too — only its right end can rule it out. So intervals can be added to a candidate pool exactly once.

Keep the candidate pool in a min-heap ordered by size (store the right end alongside). Before answering a query, pop entries whose right end is behind the query — they can never contain this or any later query. The surviving top is the answer. Record answers by original index.

▶ Run checks these sample cases. Submit also runs hidden edge cases.

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

Expected output: [3, 4, 5, -1]