HardNo. 1851

Minimum Interval to Include Each Query — LeetCode 1851 Python Solution

Topics
Array, Binary Search, Sorting, Line Sweep, Heap (Priority Queue)
On a study list
NeetCode 150
Reading time
4 min

The problem

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.

Example

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:

Python solution

PythonSolution
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

Complexity

Time
O(n × log n + m × log m)
Space · auxiliary
O(n + m)

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 1851. Minimum Interval to Include Each Query is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Related problems

Frequently asked questions

How hard is LeetCode 1851. Minimum Interval to Include Each Query?

LeetCode 1851. Minimum Interval to Include Each Query is rated Hard on LeetCode.

What is the time complexity of LeetCode 1851. Minimum Interval to Include Each Query?

The Python solution on this page runs in O(n × log n + m × log m).

What is the space complexity of LeetCode 1851. Minimum Interval to Include Each Query?

The Python solution on this page uses O(n + m) auxiliary space.

What topics does LeetCode 1851. Minimum Interval to Include Each Query cover?

LeetCode 1851. Minimum Interval to Include Each Query is tagged Array, Binary Search, Sorting, Line Sweep and Heap (Priority Queue) on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.