iT邦幫忙

1

LeetCode Weekly Contest 239的詳解分享

  • 分享至 

  • xImage
  •  

Hard- 1851. Minimum Interval to Include Each Query

題意:給定一個二維陣列表示區間[left, right]\(表示left, right兩個數字),區間的長度定義為right - left + 1
另給定一個陣列表示query,要回答每個query包含該數字的最小長度為何?
Sample Input:intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
Output: [3,3,1,4]
說明: 
- Query = 2: [2,4] 是最小的區間包含 2,故答案為 4 - 2 + 1 = 3
- Query = 3: [2,4] 是最小的區間包含 3,故答案為 4 - 2 + 1 = 3
- Query = 4: [4,4] 是最小的區間包含 4,故答案為 4 - 4 + 1 = 1
- Query = 5: [3,6] 是最小的區間包含 5,故答案為 6 - 3 + 1 = 4.

本題需要事先將queries和intervals排序,
每次進來一個新的query時,將舊的元素踢除(區間右界小於現在的query),
嘗試加入新的可能元素(區間左界小於現在的query),
由於需要一直新增、移除元素,
還要查詢最小值,故想到用「heap」結構

# 1851. Minimum Interval to Include Each Query 題解
from heapq import heappop, heappush
class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        A = sorted(intervals)
        Q = sorted((q, i) for i, q in enumerate(queries))
        heap = []
        res = [-1] * len(Q)
        j = 0
        
        for query, idx in Q:
            while heap and heap[0][1] < query:
                heappop(heap)
            while j < len(A) :
                left, right = A[j]
                if left>query:
                    break
                if right>=query:
                    heappush(heap, (right - left + 1, right))
                j+=1
            if heap:
                res[idx] = heap[0][0]
        return res

圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言