題目網址：https://leetcode.cn/problems/minimum-interval-to-include-each-query/

題意：給一個二維整數 array intervals, 其中 intervals[i] = [left_i, right_i] 表示第 i 個區間開始於 left_i、結束於 right_i。

定義 intervals[i] 的長度為 right_i - left_i + 1。

再給一整數 array queries, 第 j 個查詢的答案是滿足 left_i ≤ queries[j] ≤ right_i 的最小區間 i 之長度。若不存在這樣的區間, 則答案為 -1。

以 array 的形式返回對應查詢的所有答案。

Solution：

想法：利用 offline 算法 + Min Heap + Greedy, 先將所有滿足 interval.left ≤ query 的區間加到 pq 中, 再判斷 pq 中的這些 interval 是否滿足 interval.right ≥ query

offline 算法：

  • 將 queries 由小到大排序, 並記錄每個 query 原先的 index
  • 將 intervals 根據 left 由小到大排序

遍歷每個 query：

  • Min Heap pq 儲存滿足 interval.left ≤ query 的區間之長度 duration 和 right
  • 對於每個 query：
    • 先將符合 interval.left ≤ query 的所有區間加入到 min heap pq 中, 其中 pq 是根據區間長度 duration 由小到大排序
    • 不斷檢查 pq.top().right 是否 ≥ query。若滿足 pq.top() ≥ query, 則該區間即為符合條件的最小區間
class Solution {
public:
    vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
        using pii = pair<int, int>;

        const int n = queries.size();
        vector<pii> querySet;

        // 先將 query 由小到大排序, 並記錄其 index
        for (int i = 0; i < n; ++i) {
            querySet.emplace_back(pii{queries[i], i});
        }

        // offline 算法
        sort(intervals.begin(), intervals.end());
        sort(querySet.begin(), querySet.end());

        int i = 0;
        vector<int> res(n, -1);
        priority_queue<pii, vector<pii>, greater<>> pq; // min heap

        // 遍歷每個 query
        for (const auto& [query, idx] : querySet) {
            // 把 left ≤ query 的區間加到 pq 中, 讓 pq 根據 duration 由小到大排序
            while (i < intervals.size() && intervals[i][0] <= query) {
                const int duration = intervals[i][1] - intervals[i][0] + 1;
                pq.emplace(pii{duration, intervals[i][1]});
                ++i;
            }

            // 剔除中 right < query 的區間, 讓 pq.top() 為 ≥ query 的區間
            while (!pq.empty() && pq.top().second < query) {
                pq.pop();
            }

            // 若 pq.top() 存在, 即為該 query 的最小區間
            if (!pq.empty()) {
                res[idx] = pq.top().first;
            }
        }

        return res;
    }
};
  • time：$O(m \cdot log(m) + n \cdot log(n))$ ➔ m 為 interval 的個數、n 為 query 的個數
    • $O(m \cdot log(m))$
      • 排序 intervals
      • 每個 intervals[i] 最多被加入到 pq 一次, 而 pq 每 insert / delete 一個元素皆需 $O(log(m))$
    • $O(n \cdot log(n))$：排序 querySet
  • space：$O(m + n)$
    • $O(m)$：pq 中的元素個數不超過 $m$ 個, m 為 intervals 的個數
    • $O(n)$：querySet