{"id":864,"date":"2017-11-19T18:24:40","date_gmt":"2017-11-20T02:24:40","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=864"},"modified":"2018-04-19T08:36:06","modified_gmt":"2018-04-19T15:36:06","slug":"leetcode-731-my-calendar-ii","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/geometry\/leetcode-731-my-calendar-ii\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 731. My Calendar II &#8211; \u82b1\u82b1\u9171"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 731. My Calendar II - \u5237\u9898\u627e\u5de5\u4f5c EP113\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/rRMdxFA-8G4?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:\u00a0<\/strong><\/p>\n<p>Implement a\u00a0<code>MyCalendarTwo<\/code>\u00a0class to store your events. A new event can be added if adding the event will not cause a\u00a0<b>triple<\/b>\u00a0booking.<\/p>\n<p>Your class will have one method,\u00a0<code>book(int start, int end)<\/code>. Formally, this represents a booking on the half open interval\u00a0<code>[start, end)<\/code>, the range of real numbers\u00a0<code>x<\/code>\u00a0such that\u00a0<code>start &lt;= x &lt; end<\/code>.<\/p>\n<p>A\u00a0<i>triple booking<\/i>\u00a0happens when\u00a0<b>three<\/b>\u00a0events have some non-empty intersection (ie., there is some time that is common to all 3 events.)<\/p>\n<p>For each call to the method\u00a0<code>MyCalendar.book<\/code>, return\u00a0<code>true<\/code>\u00a0if the event can be added to the calendar successfully without causing a\u00a0<b>triple<\/b>\u00a0booking. Otherwise, return\u00a0<code>false<\/code>\u00a0and do not add the event to the calendar.<\/p>\n<p>Your class will be called like this:\u00a0<code>MyCalendar cal = new MyCalendar();<\/code>\u00a0<code>MyCalendar.book(start, end)<\/code><\/p>\n<p><b>Example 1:<\/b><\/p>\n<pre class=\"toolbar:2 wrap:true lang:default decode:true\">MyCalendar();\r\nMyCalendar.book(10, 20); \/\/ returns true\r\nMyCalendar.book(50, 60); \/\/ returns true\r\nMyCalendar.book(10, 40); \/\/ returns true\r\nMyCalendar.book(5, 15); \/\/ returns false\r\nMyCalendar.book(5, 10); \/\/ returns true\r\nMyCalendar.book(25, 55); \/\/ returns true\r\nExplanation&lt;b&gt;:&lt;\/b&gt; \r\nThe first two events can be booked.  The third event can be double booked.\r\nThe fourth event (5, 15) can't be booked, because it would result in a triple booking.\r\nThe fifth event (5, 10) can be booked, as it does not use time 10 which is already double booked.\r\nThe sixth event (25, 55) can be booked, as the time in [25, 40) will be double booked with the third event;\r\nthe time [40, 50) will be single booked, and the time [50, 55) will be double booked with the second event.\r\n<\/pre>\n<p><b>Note:<\/b><\/p>\n<p>&nbsp;<\/p>\n<ul>\n<li>The number of calls to\u00a0<code>MyCalendar.book<\/code>\u00a0per test case will be at most\u00a0<code>1000<\/code>.<\/li>\n<li>In calls to\u00a0<code>MyCalendar.book(start, end)<\/code>,\u00a0<code>start<\/code>\u00a0and\u00a0<code>end<\/code>\u00a0are integers in the range\u00a0<code>[0, 10^9]<\/code>.<\/li>\n<\/ul>\n<p><strong>Idea:<\/strong><\/p>\n<p>Brute Force<\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/11\/731-ep113-1.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-875\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/11\/731-ep113-1.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/11\/731-ep113-1.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/11\/731-ep113-1-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/11\/731-ep113-1-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/11\/731-ep113-1-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/p>\n<p><b style=\"font-size: 1rem;\">Solution1:<\/b><\/p>\n<p>Brute Force<\/p>\n<p>Time Complexity: O(n^2)<\/p>\n<p>Space Complexity: O(n)<\/p>\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahua\r\n\/\/ Runtime: 82 ms\r\nclass MyCalendarTwo {\r\npublic:\r\n    MyCalendarTwo() {}\r\n    \r\n    bool book(int start, int end) {\r\n        for (const auto&amp; kv : overlaps_)\r\n            if (max(start, kv.first) &lt; min(end, kv.second)) return false;\r\n        \r\n        for (const auto&amp; kv : booked_) {\r\n            const int ss = max(start, kv.first);\r\n            const int ee = min(end, kv.second);\r\n            if (ss &lt; ee) overlaps_.emplace_back(ss, ee);\r\n        }\r\n        \r\n        booked_.emplace_back(start, end);\r\n        return true;\r\n    }\r\nprivate:\r\n    vector&lt;pair&lt;int, int&gt;&gt; booked_;\r\n    vector&lt;pair&lt;int, int&gt;&gt; overlaps_;\r\n};<\/pre>\n<p>&nbsp;<\/p>\n<p>Java<\/p>\n<pre class=\"lang:java decode:true\">\/\/ Author: Huahua\r\n\/\/ Runtime: 156 ms\r\nclass MyCalendarTwo {\r\n    \r\n    private List&lt;int[]&gt; booked_;\r\n    private List&lt;int[]&gt; overlaps_;\r\n\r\n    public MyCalendarTwo() {\r\n        booked_ = new ArrayList&lt;&gt;();\r\n        overlaps_ = new ArrayList&lt;&gt;();\r\n    }\r\n    \r\n    public boolean book(int start, int end) {\r\n        for (int[] range : overlaps_)\r\n            if (Math.max(range[0], start) &lt; Math.min(range[1], end)) \r\n                return false;\r\n        \r\n        for (int[] range : booked_) {\r\n            int ss = Math.max(range[0], start);\r\n            int ee = Math.min(range[1], end);\r\n            if (ss &lt; ee) overlaps_.add(new int[]{ss, ee});\r\n        }\r\n        \r\n        booked_.add(new int[]{start, end});\r\n        return true;\r\n    }\r\n\r\n}<\/pre>\n<p>Python<\/p>\n<pre class=\"lang:python decode:true \">\"\"\"\r\nAuthor: Huahua\r\nRuntime: 638 ms\r\n\"\"\"\r\nclass MyCalendarTwo:\r\n\r\n    def __init__(self):\r\n        self.booked_ = []\r\n        self.overlaps_ = []\r\n\r\n    def book(self, start, end):\r\n        for s, e in self.overlaps_:\r\n            if start &lt; e and end &gt; s: return False\r\n        \r\n        for s, e in self.booked_:            \r\n            if start &lt; e and end &gt; s: \r\n                self.overlaps_.append([max(start, s), min(end, e)])\r\n        \r\n        self.booked_.append([start, end])\r\n        return True<\/pre>\n<p>&nbsp;<\/p>\n<p><strong>Solution 2:<\/strong><\/p>\n<p>Counting<\/p>\n<p>Time Complexity: O(n^2logn)<\/p>\n<p>Space Complexity: O(n)<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Runtime: 212 ms\r\nclass MyCalendarTwo {\r\npublic:\r\n    MyCalendarTwo() {}\r\n    \r\n    bool book(int start, int end) {\r\n        ++delta_[start];\r\n        --delta_[end];\r\n        int count = 0;\r\n        for (const auto&amp; kv : delta_) {\r\n            count += kv.second;\r\n            if (count == 3) {\r\n                --delta_[start];\r\n                ++delta_[end];\r\n                return false;\r\n            }\r\n            if (kv.first &gt; end) break;\r\n        }\r\n        return true;\r\n    }\r\nprivate:\r\n    map&lt;int, int&gt; delta_;\r\n};<\/pre>\n<p>&nbsp;<\/p>\n<p><strong>Related Problems:<\/strong><\/p>\n<ul>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/binary-search\/leetcode-729-my-calendar-i\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 729. My Calendar I<\/a><\/li>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/data-structure\/leetcode-715-range-module\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 715. Range Module<\/a><\/li>\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<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/geometry\/leetcode-699-falling-squares\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 699. Falling Squares<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Problem:\u00a0 Implement a\u00a0MyCalendarTwo\u00a0class to store your events. A new event can be added if adding the event will not cause a\u00a0triple\u00a0booking. Your class will have&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[163,127],"tags":[159,139,104],"class_list":["post-864","post","type-post","status-publish","format-standard","hentry","category-easy","category-geometry","tag-overlap","tag-range","tag-sweep-line","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/864","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=864"}],"version-history":[{"count":11,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/864\/revisions"}],"predecessor-version":[{"id":2631,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/864\/revisions\/2631"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=864"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=864"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=864"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}