You are given a 2D integer array `intervals`

, where `intervals[i] = [left`

describes the _{i}, right_{i}]`i`

interval starting at ^{th}`left`

and ending at _{i}`right`

_{i}**(inclusive)**. The **size** of an interval is defined as the number of integers it contains, or more formally `right`

._{i} - left_{i} + 1

You are also given an integer array `queries`

. The answer to the `j`

query is the ^{th}**size of the smallest interval** `i`

such that `left`

. If no such interval exists, the answer is _{i} <= queries[j] <= right_{i}`-1`

.

Return *an array containing the answers to the queries*.

**Example 1:**

Input:intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]Output:[3,3,1,4]Explanation:The queries are processed as follows: - Query = 2: The interval [2,4] is the smallest interval containing 2. The answer is 4 - 2 + 1 = 3. - Query = 3: The interval [2,4] is the smallest interval containing 3. The answer is 4 - 2 + 1 = 3. - Query = 4: The interval [4,4] is the smallest interval containing 4. The answer is 4 - 4 + 1 = 1. - Query = 5: The interval [3,6] is the smallest interval containing 5. The answer is 6 - 3 + 1 = 4.

**Example 2:**

Input:intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]Output:[2,-1,4,6]Explanation:The queries are processed as follows: - Query = 2: The interval [2,3] is the smallest interval containing 2. The answer is 3 - 2 + 1 = 2. - Query = 19: None of the intervals contain 19. The answer is -1. - Query = 5: The interval [2,5] is the smallest interval containing 5. The answer is 5 - 2 + 1 = 4. - Query = 22: The interval [20,25] is the smallest interval containing 22. The answer is 25 - 20 + 1 = 6.

**Constraints:**

`1 <= intervals.length <= 10`

^{5}`1 <= queries.length <= 10`

^{5}`intervals[i].length == 2`

`1 <= left`

_{i}<= right_{i}<= 10^{7}`1 <= queries[j] <= 10`

^{7}

**Solution: Offline Processing** **+ Priority Queue**

Similar to 花花酱 LeetCode 1847. Closest Room

Sort intervals by right in descending order, sort queries in descending. Add valid intervals into the priority queue (or treeset) ordered by size in ascending order. Erase invalid ones. The first one (if any) will be the one with the smallest size that contains the current query.

Time complexity: O(nlogn + mlogm + mlogn)

Space complexity: O(m + n)

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
// Author: Huahua class Solution { public: vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) { const int n = intervals.size(); const int m = queries.size(); sort(begin(intervals), end(intervals), [](const auto& a, const auto& b){ return a[1] > b[1]; }); vector<pair<int, int>> qs(m); // {query, i} for (int i = 0; i < m; ++i) qs[i] = {queries[i], i}; sort(rbegin(qs), rend(qs)); vector<int> ans(m); int j = 0; priority_queue<pair<int, int>> pq; // {-size, left} for (const auto& [query, i] : qs) { while (j < n && intervals[j][1] >= query) { pq.emplace(-(intervals[j][1] - intervals[j][0] + 1), intervals[j][0]); ++j; } while (!pq.empty() && pq.top().second > query) pq.pop(); ans[i] = pq.empty() ? -1 : -pq.top().first; } return ans; } }; |