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)

Reading material

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

Reference solution (spoiler · python)

# Time:  O(nlogn + klogk + klogn)
# space: O(n + k)

import heapq


class Solution(object):
    def minInterval(self, intervals, queries):
        """
        :type intervals: List[List[int]]
        :type queries: List[int]
        :rtype: List[int]
        """
        intervals.sort()
        queries = [(q, i) for i, q in enumerate(queries)]
        queries.sort()
        min_heap = []
        i = 0
        result =[-1]*len(queries)
        for q, idx in queries:
            while i != len(intervals) and intervals[i][0] <= q:
                heapq.heappush(min_heap, [intervals[i][1]-intervals[i][0]+1, i])
                i += 1
            while min_heap and intervals[min_heap[0][1]][1] < q:
                heapq.heappop(min_heap)
            result[idx] = min_heap[0][0] if min_heap else -1
        return result

Solution from kamyu104/LeetCode-Solutions · MIT