{"id":679,"date":"2017-10-22T16:29:45","date_gmt":"2017-10-22T23:29:45","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=679"},"modified":"2018-04-19T08:27:29","modified_gmt":"2018-04-19T15:27:29","slug":"leetcode-715-range-module","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/data-structure\/leetcode-715-range-module\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 715. Range Module"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode. 715 Range Module - \u5237\u9898\u627e\u5de5\u4f5c EP96\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/pcpB9ux3RrQ?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<p><strong>Problem:<\/strong><\/p>\n<p>A Range Module is a module that tracks ranges of numbers. Your task is to design and implement the following interfaces in an efficient manner.<\/p>\n<p>&nbsp;<\/p>\n<ul>\n<li><code>addRange(int left, int right)<\/code>\u00a0Adds the half-open interval\u00a0<code>[left, right)<\/code>, tracking every real number in that interval. Adding an interval that partially overlaps with currently tracked numbers should add any numbers in the interval\u00a0<code>[left, right)<\/code>\u00a0that are not already tracked.<\/li>\n<li><code>queryRange(int left, int right)<\/code>\u00a0Returns true if and only if every real number in the interval\u00a0<code>[left, right)<\/code>\u00a0is currently being tracked.<\/li>\n<li><code>removeRange(int left, int right)<\/code>\u00a0Stops tracking every real number currently being tracked in the interval\u00a0<code>[left, right)<\/code>.<\/li>\n<\/ul>\n<p><b>Example 1:<\/b><\/p>\n<pre class=\"\">addRange(10, 20): null\r\nremoveRange(14, 16): null\r\nqueryRange(10, 14): true (Every number in [10, 14) is being tracked)\r\nqueryRange(13, 15): false (Numbers like 14, 14.03, 14.17 in [13, 15) are not being tracked)\r\nqueryRange(16, 17): true (The number 16 in [16, 17) is still being tracked, despite the remove operation)\r\n<\/pre>\n<p><b>Note:<\/b><\/p>\n<ul>\n<li>A half open interval\u00a0<code>[left, right)<\/code>\u00a0denotes all real numbers\u00a0<code>left &lt;= x &lt; right<\/code>.<\/li>\n<li><code>0 &lt; left &lt; right &lt; 10^9<\/code>\u00a0in all calls to\u00a0<code>addRange, queryRange, removeRange<\/code>.<\/li>\n<li>The total number of calls to\u00a0<code>addRange<\/code>\u00a0in a single test case is at most\u00a0<code>1000<\/code>.<\/li>\n<li>The total number of calls to\u00a0<code>queryRange<\/code>\u00a0in a single test case is at most\u00a0<code>5000<\/code>.<\/li>\n<li>The total number of calls to\u00a0<code>removeRange<\/code>\u00a0in a single test case is at most\u00a0<code>1000<\/code>.<\/li>\n<\/ul>\n<p><script async src=\"\/\/pagead2.googlesyndication.com\/pagead\/js\/adsbygoogle.js\"><\/script><br \/>\n<ins class=\"adsbygoogle\" style=\"display: block; text-align: center;\" data-ad-layout=\"in-article\" data-ad-format=\"fluid\" data-ad-client=\"ca-pub-2404451723245401\" data-ad-slot=\"7983117522\"><\/ins><br \/>\n<script>\n     (adsbygoogle = window.adsbygoogle || []).push({});\n<\/script><\/p>\n<p><strong>Idea:<\/strong><\/p>\n<p>map \/ ordered ranges<\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/715-ep96-1.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-689\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/715-ep96-1.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/715-ep96-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/715-ep96-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/715-ep96-1-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/715-ep96-1-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a>\u00a0\u00a0<a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/715-ep96-2.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-688\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/715-ep96-2.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/715-ep96-2.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/715-ep96-2-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/715-ep96-2-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/715-ep96-2-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/715-ep96-3.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-687\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/715-ep96-3.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/715-ep96-3.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/715-ep96-3-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/715-ep96-3-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/715-ep96-3-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/715-ep96-4.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-686\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/715-ep96-4.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/715-ep96-4.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/715-ep96-4-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/715-ep96-4-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/715-ep96-4-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/p>\n<p>&nbsp;<\/p>\n<p><strong>Solution:<\/strong><\/p>\n<p>C++ \/ vector<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Runtime: 276 ms\r\nclass RangeModule {\r\npublic:\r\n    RangeModule() {}\r\n    \r\n    void addRange(int left, int right) {\r\n        vector&lt;pair&lt;int, int&gt;&gt; new_ranges;\r\n        bool inserted = false;\r\n        for (const auto&amp; kv : ranges_) {            \r\n            if (kv.first &gt; right &amp;&amp; !inserted) {\r\n                new_ranges.emplace_back(left, right);\r\n                inserted = true;\r\n            }\r\n            if (kv.second &lt; left || kv.first &gt; right) { \r\n                new_ranges.push_back(kv);\r\n            } else {\r\n                left = min(left, kv.first);\r\n                right = max(right, kv.second);\r\n            }\r\n        }       \r\n        if (!inserted) new_ranges.emplace_back(left, right);       \r\n        ranges_.swap(new_ranges);\r\n    }\r\n    \r\n    bool queryRange(int left, int right) {\r\n        const int n = ranges_.size();\r\n        int l = 0;\r\n        int r = n - 1;\r\n        \/\/ Binary search\r\n        while (l &lt;= r) {\r\n            int m = l + (r - l) \/ 2;\r\n            if (ranges_[m].second &lt; left)\r\n                l = m + 1;\r\n            else if (ranges_[m].first &gt; right)\r\n                r = m - 1;\r\n            else\r\n                return ranges_[m].first &lt;= left &amp;&amp; ranges_[m].second &gt;= right;\r\n        }\r\n        return false;\r\n    }\r\n    \r\n    void removeRange(int left, int right) {\r\n        vector&lt;pair&lt;int, int&gt;&gt; new_ranges;        \r\n        for (const auto&amp; kv : ranges_) {\r\n            if (kv.second &lt;= left || kv.first &gt;= right) {\r\n                new_ranges.push_back(kv);\r\n            } else {\r\n                if (kv.first &lt; left)\r\n                    new_ranges.emplace_back(kv.first, left);\r\n                if (kv.second &gt; right)\r\n                    new_ranges.emplace_back(right, kv.second);\r\n            }        \r\n        }\r\n        ranges_.swap(new_ranges);\r\n    }\r\n    vector&lt;pair&lt;int, int&gt;&gt; ranges_;\r\n};<\/pre>\n<p>C++ \/ map<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Runtime: 199 ms\r\nclass RangeModule {\r\npublic:\r\n    RangeModule() {}\r\n    \r\n    void addRange(int left, int right) {\r\n        IT l, r;\r\n        getOverlapRanges(left, right, l, r);\r\n        \/\/ At least one range overlapping with [left, right)\r\n        if (l != r) {\r\n            \/\/ Merge intervals into [left, right)\r\n            auto last = r; --last;\r\n            left = min(left, l-&gt;first);            \r\n            right = max(right, last-&gt;second);\r\n            \/\/ Remove all overlapped ranges\r\n            ranges_.erase(l, r);\r\n        }\r\n        \/\/ Add a new\/merged range\r\n        ranges_[left] = right;\r\n    }\r\n    \r\n    bool queryRange(int left, int right) {\r\n        IT l, r;\r\n        getOverlapRanges(left, right, l, r);\r\n        \/\/ No overlapping range\r\n        if (l == r) return false;\r\n        return l-&gt;first &lt;= left &amp;&amp; l-&gt;second &gt;= right;\r\n    }\r\n    \r\n    void removeRange(int left, int right) {\r\n        IT l, r;\r\n        getOverlapRanges(left, right, l, r);\r\n        \/\/ No overlapping range\r\n        if (l == r) return;\r\n        auto last = r; --last;\r\n        int start = min(left, l-&gt;first);        \r\n        int end = max(right, last-&gt;second);\r\n        \/\/ Delete overlapping ranges        \r\n        ranges_.erase(l, r);\r\n        if (start &lt; left) ranges_[start] = left;\r\n        if (end &gt; right) ranges_[right] = end;\r\n    }\r\nprivate:\r\n    typedef map&lt;int, int&gt;::iterator IT;\r\n    map&lt;int, int&gt; ranges_;\r\n    void getOverlapRanges(int left, int right, IT&amp; l, IT&amp; r) {\r\n        l = ranges_.upper_bound(left);\r\n        r = ranges_.upper_bound(right);\r\n        if (l != ranges_.begin())\r\n            if ((--l)-&gt;second &lt; left) l++;\r\n    }\r\n};<\/pre>\n<p><strong>Related Problems:<\/strong><\/p>\n<ul>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/geometry\/leetcode-57-insert-interval\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 57. Insert Interval<\/a><\/li>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/geometry\/leetcode-56-merge-intervals\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 56. Merge Intervals<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Problem: A Range Module is a module that tracks ranges of numbers. Your task is to design and implement the following interfaces in an efficient&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[89,127,165],"tags":[140,139],"class_list":["post-679","post","type-post","status-publish","format-standard","hentry","category-data-structure","category-geometry","category-hard","tag-query","tag-range","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/679","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=679"}],"version-history":[{"count":10,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/679\/revisions"}],"predecessor-version":[{"id":2548,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/679\/revisions\/2548"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=679"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=679"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=679"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}