#1851

Minimum Interval to Include Each Query

hard· Intervalsruns: 0

You are given a 2D integer array intervals where intervals[i] = [left_i, right_i] describes the inclusive interval [left_i, right_i] of length right_i - left_i + 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 left_i <= queries[j] <= right_i. If no such interval exists, the answer is -1. Return an array containing the answers to all queries.

wpm 0acc 100%time 0:000 / 667

import heapq

class Solution:
    def minInterval(
        self,
        intervals: list[list[int]],
        queries: list[int],
    ) -> list[int]:
        intervals.sort()
        sorted_queries = sorted(queries)
        result = {}
        heap = []
        i = 0
        for q in sorted_queries:
            while i < len(intervals) and intervals[i][0] <= q:
                left, right = intervals[i]
                heapq.heappush(heap, (right - left + 1, right))
                i += 1
            while heap and heap[0][1] < q:
                heapq.heappop(heap)
            result[q] = heap[0][0] if heap else -1
        return [result[q] for q in queries]

click the box to focus · tab inserts 4 spaces · backspace to correct · esc to pause

desktop only

codedrill is a typing game and needs a real keyboard. open this on a laptop or desktop to practice.

you can still browse problems and sections from your phone.