#1851

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Minimum Interval to Include Each Query

Find the smallest interval containing each query efficiently using binary search.

array binary search line sweep sorting heap priority queue

Problem Statement

You are given a 2D integer array intervals, where each element represents an interval described by two integers: a starting point and an endpoint. The size of an interval is determined by the number of integers it contains, or more formally, by the difference between the endpoint and the start point plus one.

You are also given an array of integer queries. For each query, find the smallest interval that contains the query. If no interval contains the query, return -1. The task is to return an array containing the answers for all the queries.

Examples

Example 1

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

Output: [3,3,1,4]

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]

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 <= 105
1 <= queries.length <= 105
intervals[i].length == 2
1 <= lefti <= righti <= 107
1 <= queries[j] <= 107

Solution Approach

Sort the Intervals

First, sort the intervals by their starting points. Sorting ensures that we can process the intervals in an ordered manner, allowing us to make efficient queries.

Binary Search for Query

For each query, apply binary search to find the smallest interval that contains it. The binary search minimizes the time it takes to search through the intervals.

Optimize with a Min-Heap

Use a min-heap to efficiently manage the intervals that overlap the current query. The heap helps in finding the smallest interval with the least computation overhead.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the sorting of intervals and the binary search process. Sorting the intervals takes O(n log n), and for each query, binary search can be applied in O(log n). The total complexity is O(n log n + m log n), where n is the number of intervals and m is the number of queries.

What Interviewers Usually Probe

Candidate understands how to use sorting to optimize interval processing.
Candidate demonstrates knowledge of binary search in finding the correct interval.
Candidate correctly applies a heap to minimize computational time during interval queries.

Common Pitfalls or Variants

Common pitfalls

Not sorting the intervals before applying binary search leads to inefficient solutions.
Failing to use the heap structure efficiently could result in higher-than-expected complexity.
Not handling cases where no interval contains the query could lead to incorrect results.

Follow-up variants

What if the intervals are already sorted?
How would you handle queries that are out of bounds of all the intervals?
What if you need to handle a larger range of values, say up to 10^9?

FAQ

What is the core pattern in solving 'Minimum Interval to Include Each Query'?

The core pattern involves binary search to find the smallest interval containing each query, with optimizations like sorting intervals and using a heap.

How does binary search help in solving this problem?

Binary search helps by efficiently narrowing down the search space for each query, minimizing the number of comparisons needed to find the valid interval.

What is the time complexity of this problem?

The time complexity is O(n log n + m log n), where n is the number of intervals and m is the number of queries.

What are common pitfalls when solving this problem?

Common pitfalls include not sorting intervals, not using a heap to manage active intervals, and missing edge cases where no interval contains a query.

Can GhostInterview help with advanced variations of this problem?

Yes, GhostInterview can provide hints and optimizations for handling larger ranges, pre-sorted intervals, and other advanced variations of this problem.

terminal

Solution

Solution 1: Sorting + Offline Query + Priority Queue (Min Heap)

We notice that the order of queries does not affect the answer, and the intervals involved do not change. Therefore, we consider sorting all queries in ascending order, and sorting all intervals in ascending order of the left endpoint.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        n, m = len(intervals), len(queries)
        intervals.sort()
        queries = sorted((x, i) for i, x in enumerate(queries))
        ans = [-1] * m
        pq = []
        i = 0
        for x, j in queries:
            while i < n and intervals[i][0] <= x:
                a, b = intervals[i]
                heappush(pq, (b - a + 1, b))
                i += 1
            while pq and pq[0][1] < x:
                heappop(pq)
            if pq:
                ans[j] = pq[0][0]
        return ans

Continue Practicing

#1648 sell diminishing valued colored balls #2054 two best non overlapping events #2333 minimum sum of squared difference