Minimum Interval to Include Each Query

Minimum Interval to Include Each Query is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Heap (Priority Queue) Patterns pattern, in the Scheduling / Minimum Cost (Greedy with Priority Queue) subpattern.

Problem statement

Implement Solution.minInterval, whose method receives intervals and queries. Each element of intervals is an interval represented by two integers [l, r], including every integer from l through r. An interval's size is r - l + 1.

For every integer in queries, find the smallest interval whose range contains that query, meaning l <= query <= r. Return an array in the same order as queries, where each entry is the size of the smallest qualifying interval. If no interval contains a query, return -1 for that position.

The result must preserve duplicate queries and must contain one answer for every element of queries. The input arrays and their elements must not be interpreted as a set; each query is answered independently.

Example 1:

Input: intervals = [[4,9],[1,3],[7,12]], queries = [2,5,10,13] Output: [3,6,6,-1] Explanation: Query 2 is covered by [1,3], whose size is 3. Queries 5 and 10 are each covered by an interval of size 6, while no interval contains 13.

Example 2:

Input: intervals = [[2,2],[1,8],[5,6],[8,10]], queries = [2,6,8,11] Output: [1,2,3,-1] Explanation: The single-point interval [2,2] is best for 2, and [5,6] is best for 6. Query 8 is covered by [8,10] with size 3, and 11 is uncovered.

Example 3:

Input: intervals = [[10,20],[12,12],[15,18]], queries = [12,12,17] Output: [1,1,4] Explanation: Both occurrences of 12 use the one-point interval [12,12]. For 17, [15,18] is smaller than [10,20].

Constraints:

- 1 <= intervals.length <= 10^5 - 1 <= queries.length <= 10^5 - Each element of intervals contains exactly two integers [l, r]. - 1 <= l <= r <= 10^7 for every interval [l, r] in intervals. - 1 <= query <= 10^7 for every query in queries. - The integers in queries may repeat, and intervals may overlap.

Topics and companies

Topics: Array, Heap, Sorting, Greedy.

How to practise Minimum Interval to Include Each Query on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O((intervals.size() + queries.size()) log intervals.size() + queries.size() log queries.size()) time and O(intervals.size() + queries.size()) space.

Open Minimum Interval to Include Each Query in the code editor, or read the Minimum Interval to Include Each Query editorial for a worked solution with its approach and complexity analysis.

Where Minimum Interval to Include Each Query sits in the DSA pattern sheet

Problems related to Minimum Interval to Include Each Query

Other problems that use the same Scheduling / Minimum Cost (Greedy with Priority Queue) and Heap (Priority Queue) Patterns techniques:

Preparing this workspace.