{"id":8439,"date":"2021-05-08T23:05:19","date_gmt":"2021-05-09T06:05:19","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8439"},"modified":"2021-05-08T23:12:51","modified_gmt":"2021-05-09T06:12:51","slug":"leetcode-1851-minimum-interval-to-include-each-query","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/priority-queue\/leetcode-1851-minimum-interval-to-include-each-query\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1851. Minimum Interval to Include Each Query"},"content":{"rendered":"\n<p>You are given a 2D integer array&nbsp;<code>intervals<\/code>, where&nbsp;<code>intervals[i] = [left<sub>i<\/sub>, right<sub>i<\/sub>]<\/code>&nbsp;describes the&nbsp;<code>i<sup>th<\/sup><\/code>&nbsp;interval starting at&nbsp;<code>left<sub>i<\/sub><\/code>&nbsp;and ending at&nbsp;<code>right<sub>i<\/sub><\/code>&nbsp;<strong>(inclusive)<\/strong>. The&nbsp;<strong>size<\/strong>&nbsp;of an interval is defined as the number of integers it contains, or more formally&nbsp;<code>right<sub>i<\/sub>&nbsp;- left<sub>i<\/sub>&nbsp;+ 1<\/code>.<\/p>\n\n\n\n<p>You are also given an integer array&nbsp;<code>queries<\/code>. The answer to the&nbsp;<code>j<sup>th<\/sup><\/code>&nbsp;query is the&nbsp;<strong>size of the smallest interval<\/strong>&nbsp;<code>i<\/code>&nbsp;such that&nbsp;<code>left<sub>i<\/sub>&nbsp;&lt;= queries[j] &lt;= right<sub>i<\/sub><\/code>. If no such interval exists, the answer is&nbsp;<code>-1<\/code>.<\/p>\n\n\n\n<p>Return&nbsp;<em>an array containing the answers to the queries<\/em>.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]\n<strong>Output:<\/strong> [3,3,1,4]\n<strong>Explanation:<\/strong> The queries are processed as follows:\n- Query = 2: The interval [2,4] is the smallest interval containing 2. The answer is 4 - 2 + 1 = 3.\n- Query = 3: The interval [2,4] is the smallest interval containing 3. The answer is 4 - 2 + 1 = 3.\n- Query = 4: The interval [4,4] is the smallest interval containing 4. The answer is 4 - 4 + 1 = 1.\n- Query = 5: The interval [3,6] is the smallest interval containing 5. The answer is 6 - 3 + 1 = 4.\n<\/pre>\n\n\n\n<p><strong>Example 2:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]\n<strong>Output:<\/strong> [2,-1,4,6]\n<strong>Explanation:<\/strong> The queries are processed as follows:\n- Query = 2: The interval [2,3] is the smallest interval containing 2. The answer is 3 - 2 + 1 = 2.\n- Query = 19: None of the intervals contain 19. The answer is -1.\n- Query = 5: The interval [2,5] is the smallest interval containing 5. The answer is 5 - 2 + 1 = 4.\n- Query = 22: The interval [20,25] is the smallest interval containing 22. The answer is 25 - 20 + 1 = 6.\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= intervals.length &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>1 &lt;= queries.length &lt;= 10<sup>5<\/sup><\/code><\/li><li><code>intervals[i].length == 2<\/code><\/li><li><code>1 &lt;= left<sub>i<\/sub>&nbsp;&lt;= right<sub>i<\/sub>&nbsp;&lt;= 10<sup>7<\/sup><\/code><\/li><li><code>1 &lt;= queries[j] &lt;= 10<sup>7<\/sup><\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Offline Processing<\/strong> <strong>+ Priority Queue<\/strong><\/h2>\n\n\n\n<p>Similar to <a href=\"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/binary-search\/leetcode-1847-closest-room\/\" data-type=\"post\" data-id=\"8419\">\u82b1\u82b1\u9171 LeetCode 1847. Closest Room<\/a><\/p>\n\n\n\n<p>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.<\/p>\n\n\n\n<p>Time complexity: O(nlogn + mlogm + mlogn)<br>Space complexity: O(m + n)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"c++\">\n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {\n    const int n = intervals.size();\n    const int m = queries.size();    \n    sort(begin(intervals), end(intervals), [](const auto& a, const auto& b){\n      return a[1] > b[1];\n    });\n    vector<pair<int, int>> qs(m); \/\/ {query, i}\n    for (int i = 0; i < m; ++i)\n      qs[i] = {queries[i], i};\n    sort(rbegin(qs), rend(qs));\n\n    vector<int> ans(m);\n    int j = 0;\n    priority_queue<pair<int, int>> pq; \/\/ {-size, left}\n    for (const auto& [query, i] : qs) {\n      while (j < n &#038;&#038; intervals[j][1] >= query) {\n        pq.emplace(-(intervals[j][1] - intervals[j][0] + 1),\n                   intervals[j][0]);\n        ++j;\n      }\n      while (!pq.empty() && pq.top().second > query) \n        pq.pop();      \n      ans[i] = pq.empty() ? -1 : -pq.top().first;         \n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>You are given a 2D integer array&nbsp;intervals, where&nbsp;intervals[i] = [lefti, righti]&nbsp;describes the&nbsp;ith&nbsp;interval starting at&nbsp;lefti&nbsp;and ending at&nbsp;righti&nbsp;(inclusive). The&nbsp;size&nbsp;of an interval is defined as the number of&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[674],"tags":[217,72],"class_list":["post-8439","post","type-post","status-publish","format-standard","hentry","category-priority-queue","tag-hard","tag-priority-queue","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8439","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=8439"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8439\/revisions"}],"predecessor-version":[{"id":8443,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8439\/revisions\/8443"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8439"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8439"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8439"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}