[DSA][Intervals] 04. Minimum Interval to Include Each Query

LeetCode 1851

 

04. Minimum Interval to Include Each Query

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.

You are also given an integer array queries.
The answer to the jth query is the size of the smallest interval i such that lefti <= queries[j] <= righti. If no such interval exists, the answer is -1.

Return an array containing the answers to the queries.

 

 

[질문하기]

- intervals 배열과 queries 배열 내 값들의 범위와 최대 길이는 어떻게 되나요?

- intervals 배열 안의 구간들은 겹칠 수 있나요?

 

[아이디어]

- intervals과 queries 배열을 오름차순으로 정렬한 후, 시작점 기준으로 query를 포함할 수 있는 구간을 minHeap에 넣고, 끝점 기준으로 query를 포함하지 않는 구간들을 minHeap에서 제외한다.

 

 

[풀이 1] Min Heap (Sort By Start)

class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        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]

쿼리와 intervals를 시작점 기준으로 정렬해서 비교하면, 각 쿼리에 대해 매번 intervals를 순회할 필요가 없어진다.

이전 쿼리에서 시작점 기준으로 heap에 포함된 구간은 지금 쿼리 때에도 포함될 것이기 때문이다.

(q1 <= q2이므로 start <= q1이었다면 start <= q2)

 

intervals를 시작점 기준으로 정렬하고, minHeap에는 현재 쿼리에 대해 유효한 interval들을 저장한다. (길이 기준 최소 힙 구성)

쿼리가 구간의 시작 값보다 커야 포함될 수 있으므로 시작 값 intervals[i][0]이 쿼리 q보다 작은 값을 전부 heap에 넣는다.

넣을 때 길이가 가장 작은 값을 구해야 하고 끝 값으로 유효한 구간인지 체크해야하기 때문에 (길이, 끝 값)을 넣는다.

 

그 다음, 힙에 있는 구간들의 끝점과 쿼리 q를 비교해서, 실제로 쿼리 q가 해당 구간의 끝점 이내에 있는지를 확인한다.

 

 

⏱️ 시간복잡도

intervals와 queries를 각각 정렬하는 데 O(n log n)과 O(m log m)이 걸리고, 정렬된 상태에서 한 번씩 순회하며 처리하므로 전체 시간 복잡도는 O(n log n + m log m)이다.

🧠 공간복잡도

intervals와 queries 배열을 저장하는 공간 외에 최소 힙을 사용하므로, 공간 복잡도는 O(n + m)이다.