{"id":6333,"date":"2020-02-16T16:54:11","date_gmt":"2020-02-17T00:54:11","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6333"},"modified":"2020-02-18T09:04:11","modified_gmt":"2020-02-18T17:04:11","slug":"leetcode-1353-maximum-number-of-events-that-can-be-attended","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-1353-maximum-number-of-events-that-can-be-attended\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1353. Maximum Number of Events That Can Be Attended"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 1353. Maximum Number of Events That Can Be Attended - \u5237\u9898\u627e\u5de5\u4f5c EP308\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/NjF9JGDGxg8?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>\n<\/div><\/figure>\n\n\n\n<p>Given an array of&nbsp;<code>events<\/code>&nbsp;where&nbsp;<code>events[i] = [startDay<sub>i<\/sub>, endDay<sub>i<\/sub>]<\/code>. Every event&nbsp;<code>i<\/code>&nbsp;starts at&nbsp;<code>startDay<sub>i<\/sub><\/code>and ends at&nbsp;<code>endDay<sub>i<\/sub><\/code>.<\/p>\n\n\n\n<p>You can attend an event&nbsp;<code>i<\/code>&nbsp;at any day&nbsp;<code>d<\/code>&nbsp;where&nbsp;<code>startTime<sub>i<\/sub>&nbsp;&lt;= d &lt;= endTime<sub>i<\/sub><\/code>. Notice that you can only attend one event at any time&nbsp;<code>d<\/code>.<\/p>\n\n\n\n<p>Return&nbsp;<em>the maximum number of events&nbsp;<\/em>you can attend.<\/p>\n\n\n\n<p><strong>Example 1:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/assets.leetcode.com\/uploads\/2020\/02\/05\/e1.png\" alt=\"\"\/><\/figure>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> events = [[1,2],[2,3],[3,4]]\n<strong>Output:<\/strong> 3\n<strong>Explanation:<\/strong> You can attend all the three events.\nOne way to attend them all is as shown.\nAttend the first event on day 1.\nAttend the second event on day 2.\nAttend the third event on day 3.\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> events= [[1,2],[2,3],[3,4],[1,2]]\n<strong>Output:<\/strong> 4\n<\/pre>\n\n\n\n<p><strong>Example 3:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> events = [[1,4],[4,4],[2,2],[3,4],[1,1]]\n<strong>Output:<\/strong> 4\n<\/pre>\n\n\n\n<p><strong>Example 4:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> events = [[1,100000]]\n<strong>Output:<\/strong> 1\n<\/pre>\n\n\n\n<p><strong>Example 5:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-preformatted;crayon:false\"><strong>Input:<\/strong> events = [[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7]]\n<strong>Output:<\/strong> 7\n<\/pre>\n\n\n\n<p><strong>Constraints:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\"><li><code>1 &lt;= events.length &lt;= 10^5<\/code><\/li><li><code>events[i].length == 2<\/code><\/li><li><code>1 &lt;= events[i][0] &lt;= events[i][1] &lt;= 10^5<\/code><\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Solution: Greedy<\/strong><\/h2>\n\n\n\n<p>Sort events by end time, for each event find the first available day to attend.<\/p>\n\n\n\n<p>Time complexity: O(sum(endtime &#8211; starttime)) = O(10^10)<br>Space complexity: O(max(endtime &#8211; starttime) = O(10^5)<\/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, 216 ms, 45.7 MB\nclass Solution {\npublic:\n  int maxEvents(vector<vector<int>>& events) {\n    sort(begin(events), end(events), [](const auto& a, const auto& b){      \n      return a[1] < b[1];      \n    });\n    int ans = 0;\n    int seen[100001] = {0};\n    for (const auto&#038; e : events) {\n      for (int i = e[0]; i <= e[1]; ++i) {\n        if (seen[i]) continue;\n        ++seen[i];\n        ++ans;\n        break;\n      }\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\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, 216 ms, 45.6 MB\nclass Solution {\npublic:\n  int maxEvents(vector<vector<int>>& events) {\n    sort(begin(events), end(events), [](const auto& a, const auto& b){      \n      return a[1] < b[1];      \n    });\n    int ans = 0;\n    unsigned char seen[100000 \/ 8 + 1] = {0};\n    for (const auto&#038; e : events) {\n      for (int i = e[0]; i <= e[1]; ++i) {\n        if (seen[i >> 3] & (1 << (i % 8))) continue;\n        seen[i >> 3] |= 1 << (i % 8);\n        ++ans;\n        break;\n      }\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">Python<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"Python\">\/\/ Author: Huahua, 824 ms\nclass Solution:\n  def maxEvents(self, events: List[List[int]]) -&gt; int:\n    lo = min(e[0] for e in events)\n    hi = max(e[1] for e in events)\n    seen = [0] * (hi - lo + 1)\n    for s, t in sorted(events, key=lambda e:e[1]):\n      for i in range(s, t + 1):\n        if seen[i - lo]: continue\n        seen[i - lo] = 1\n        break\n    return sum(seen)\n<\/pre>\n<\/div><\/div>\n\n\n\n<p>We can use a TreeSet to maintain the open days and do a binary search to find the first available day. <\/p>\n\n\n\n<p>Time complexity: O(nlogd)<br>Space complexity: O(d)<\/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, 416 ms, 46.1MB\nclass Solution {\npublic:\n  int maxEvents(vector<vector<int>>& events) {    \n    sort(begin(events), end(events), [](const auto& a, const auto& b){      \n      return a[1] < b[1];\n    });    \n    int min_d = INT_MAX;\n    int max_d = INT_MIN;\n    for (const auto&#038; e : events) {\n      min_d = min(min_d, e[0]);\n      max_d = max(max_d, e[1]);\n    }\n    vector<int> days(max_d - min_d + 1);\n    iota(begin(days), end(days), min_d);\n    set<int> s(begin(days), end(days)); \/\/ O(n)\n    \n    int ans = 0;\n    for (const auto& e : events) {\n      auto it = s.lower_bound(e[0]);\n      if (it == end(s) || *it > e[1]) continue;\n      s.erase(it);\n      ++ans;\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Given an array of&nbsp;events&nbsp;where&nbsp;events[i] = [startDayi, endDayi]. Every event&nbsp;i&nbsp;starts at&nbsp;startDayiand ends at&nbsp;endDayi. You can attend an event&nbsp;i&nbsp;at any day&nbsp;d&nbsp;where&nbsp;startTimei&nbsp;&lt;= d &lt;= endTimei. Notice that you&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[51],"tags":[88,177,243],"class_list":["post-6333","post","type-post","status-publish","format-standard","hentry","category-greedy","tag-greedy","tag-medium","tag-set","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6333","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=6333"}],"version-history":[{"count":8,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6333\/revisions"}],"predecessor-version":[{"id":6345,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6333\/revisions\/6345"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6333"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6333"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6333"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}