What is the best way to solve Minimum Interval to Include Each Query?

The optimized O(n) approach using Intervals patterns is generally preferred.

상위 150개 인터뷰쉬움

각 쿼리를 포함하는 최소 간격

'각 쿼리를 포함하는 최소 간격' 문제에 대한 자세한 가이드 및 Python 구현입니다.

문제 설명

쉬움

2D 정수 배열 간격이 제공됩니다. 여기서 간격[i] = [left_i, right_i]는 left_i에서 시작하여 right_i(포함)에서 끝나는 i번째 간격을 나타냅니다. 간격의 크기는 right_i - left_i + 1로 정의됩니다. 정수 배열 쿼리도 제공됩니다. j번째 쿼리에 대한 답은 left_i <= 쿼리[j] <= right_i가 되는 가장 작은 간격 i의 크기입니다. 그러한 간격이 존재하지 않으면 대답은 -1입니다.

쿼리에 대한 답변이 포함된 배열을 반환합니다.

minInterval(intervals: List[List[int]], queries: List[int]) -> List[int] 함수를 작성하세요.

제약

•1 <= len(intervals) <= 10^5
•1 <= len(queries) <= 10^5
•intervals[i].length == 2
•1 <= left_i <= right_i <= 10^7
•1 <= queries[j] <= 10^7

예

Example 1

Input

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

Output

[3,3,1,4]

Explanation

Smallest interval containing 2 is [2,4] (size 3). For 3 is [2,4] (size 3). For 4 is [4,4] (size 1). For 5 is [3,6] (size 4).

Example 2

Input

intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]

Output

[2,-1,4,6]

Explanation

For 2: [2,3] (size 2). For 19: none (-1). For 5: [2,5] (size 4). For 22: [20,25] (size 6).

Need a Hint?

세트나 힙과 같은 간격별 데이터 구조를 사용해 보세요.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

간격 접근 방식의 논리를 설명하십시오.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(n)•Space: O(n)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

import heapq
def min_interval_opt(intervals, queries):
    intervals.sort()
    minHeap = []; res, i = {}, 0
    for q in sorted(queries):
        while i < len(intervals) and intervals[i][0] <= q:
            l, r = intervals[i]
            heapq.heappush(minHeap, (r - l + 1, r))
            i += 1
        while minHeap and minHeap[0][1] < q: heapq.heappop(minHeap)
        res[q] = minHeap[0][0] if minHeap else -1
    return [res[q] for q in queries]

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

def min_interval_brute(intervals, queries):
    res = []
    for q in queries:
        min_len = float("inf")
        for i in intervals:
            if i[0] <= q <= i[1]:
                min_len = min(min_len, i[1] - i[0] + 1)
        res.append(min_len if min_len != float("inf") else -1)
    return res