Minimum Interval to Include Each Query

Hard · Intervals

You are given a list of closed intervals and a list of query points. For each query value, find the size (right minus left plus one) of the smallest interval from the list that fully contains that value, counting an interval that starts and ends at the same point as size one. If no interval contains a query, its answer is -1. Return a list of results in the same order as the queries.

Examples

Input:  intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
Output: [3,3,1,4]
Why:    For query 2 the smallest covering interval is [1,4] or [2,4], both size 3; for query 3 similarly size 3; for query 4 the interval [4,4] covers it with size 1; for query 5 only [3,6] covers it, size 4.

Input:  intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]
Output: [2,-1,4,6]
Why:    Query 2 is best covered by [2,3] (size 2); query 19 has no covering interval so answer is -1; query 5 is best covered by [2,5] (size 4); query 22 is covered only by [20,25] (size 6).

Constraints

1 <= intervals.length, queries.length <= 10^5, intervals[i].length == 2, intervals[i][0] <= intervals[i][1] <= 10^7, 1 <= queries[j] <= 10^7

Practise it by voice

Describe the solution out loud and the interviewer writes exactly what you say, asks when you are vague, and runs the tests in your browser.

Practise Minimum Interval to Include Each Query

This statement is written for CodeSpeek. The problem is part of the NeetCode 150 list; Watch NeetCode's explanation of Minimum Interval to Include Each Query. Reference solutions from the NeetCode repository (MIT) are used to verify our tests.