Watch 10 video solutions for Minimum Interval to Include Each Query, a hard level problem involving Array, Binary Search, Line Sweep. This walkthrough by NeetCode has 63,310 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a 2D integer array intervals, where intervals[i] = [lefti, righti] describes the ith interval starting at lefti and ending at righti (inclusive). The size of an interval is defined as the number of integers it contains, or more formally righti - lefti + 1.
You are also given an integer array queries. The answer to the jth query is the size of the smallest interval i such that lefti <= queries[j] <= righti. If no such interval exists, the answer is -1.
Return an array containing the answers to the queries.
Example 1:
Input: intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5] Output: [3,3,1,4] Explanation: The queries are processed as follows: - Query = 2: The interval [2,4] is the smallest interval containing 2. The answer is 4 - 2 + 1 = 3. - Query = 3: The interval [2,4] is the smallest interval containing 3. The answer is 4 - 2 + 1 = 3. - Query = 4: The interval [4,4] is the smallest interval containing 4. The answer is 4 - 4 + 1 = 1. - Query = 5: The interval [3,6] is the smallest interval containing 5. The answer is 6 - 3 + 1 = 4.
Example 2:
Input: intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22] Output: [2,-1,4,6] Explanation: The queries are processed as follows: - Query = 2: The interval [2,3] is the smallest interval containing 2. The answer is 3 - 2 + 1 = 2. - Query = 19: None of the intervals contain 19. The answer is -1. - Query = 5: The interval [2,5] is the smallest interval containing 5. The answer is 5 - 2 + 1 = 4. - Query = 22: The interval [20,25] is the smallest interval containing 22. The answer is 25 - 20 + 1 = 6.
Constraints:
1 <= intervals.length <= 1051 <= queries.length <= 105intervals[i].length == 21 <= lefti <= righti <= 1071 <= queries[j] <= 107Problem Overview: You get a list of intervals [start, end] and a list of query values. For each query, return the length of the smallest interval that contains that value. If no interval covers the query, return -1. The challenge is answering many queries efficiently without scanning every interval each time.
Approach 1: Sorting with Two Pointers Approach (O((n + q) log n) time, O(n) space)
Sort intervals by start time and sort queries while keeping their original indices. Use two pointers to iterate through intervals as queries increase. When the interval start becomes <= current query, add that interval to a structure tracking candidate intervals. Remove intervals whose end is smaller than the query. The smallest valid interval length is tracked dynamically. This approach relies heavily on sorting and pointer movement across both arrays.
Approach 2: Binary Search with Interval Indexing (O((n + q) log n) time, O(n) space)
Sort intervals by start value and build indexed structures for fast lookups. For each query, use binary search to locate the first interval whose start could contain the query. From that position, evaluate candidate intervals that still satisfy start ≤ query ≤ end. Track the minimum interval length while scanning valid ranges. Binary search reduces the search window for each query instead of checking all intervals.
Approach 3: Priority Queue with Sorting (O((n + q) log n) time, O(n) space)
Sort intervals by start and queries by value. As you process each query from smallest to largest, push intervals whose start ≤ query into a min heap keyed by interval length. Remove heap entries where end < query because they no longer cover the query. The top of the heap always gives the smallest interval that currently contains the query. This combination of priority queue, sorting, and a sweep over queries behaves like a classic line sweep technique.
Approach 4: Sorting and Binary Search (O((n + q) log n) time, O(n) space)
Sort intervals and preprocess useful metadata such as interval lengths and endpoints. For each query, use binary search to locate candidate intervals and evaluate which ones cover the query. Maintain the smallest length among valid matches. This method is straightforward to implement when binary search utilities are readily available and avoids maintaining a dynamic heap.
Recommended for interviews: The priority queue with sorting approach is the one most interviewers expect. It demonstrates control of offline query processing, heap operations, and efficient interval filtering. Showing the brute-force idea first (checking every interval per query) proves you understand the problem, but moving to the heap-based sweep with O((n + q) log n) complexity shows strong algorithmic thinking.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting with Two Pointers | O((n + q) log n) | O(n) | When processing queries offline with sorted intervals |
| Binary Search with Interval Indexing | O((n + q) log n) | O(n) | When you want direct lookup of candidate intervals using binary search |
| Priority Queue with Sorting | O((n + q) log n) | O(n) | Best general solution; dynamically tracks smallest valid interval |
| Sorting and Binary Search | O((n + q) log n) | O(n) | When intervals are preprocessed and heap usage is unnecessary |