LC-1851 Hard LeetCode

1851. Minimum Interval to Include Each Query

Array Binary Search Line Sweep Sorting Heap (Priority Queue)

Read the full problem statement on LeetCode.

Difficulty: hard Acceptance: 52% Topics: Array, Binary Search, Line Sweep, Sorting, Heap (Priority Queue)

View full problem on LeetCode

Also on leetcode.ca (community mirror)

Reading material

Arrays & Hashing 12 min Binary Search 12 min Intervals 10 min

Reference solution (spoiler · python)

import heapq


class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        intervals.sort(key=lambda x: x[0])
        queries_sorted = sorted(enumerate(queries), key=lambda x: x[1])

        min_heap = []
        ans = [-1] * len(queries)
        i = 0

        for query_index, query in queries_sorted:
            while i < len(intervals) and intervals[i][0] <= query:
                start, end = intervals[i]
                heapq.heappush(min_heap, (end - start + 1, end))
                i += 1

            while min_heap and min_heap[0][1] < query:
                heapq.heappop(min_heap)

            if min_heap:
                ans[query_index] = min_heap[0][0]

        return ans

Solution from kamyu104/LeetCode-Solutions · MIT