{"id":7861,"date":"2020-12-27T01:17:12","date_gmt":"2020-12-27T09:17:12","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7861"},"modified":"2020-12-27T01:20:55","modified_gmt":"2020-12-27T09:20:55","slug":"leetcode-1705-maximum-number-of-eaten-apples","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/priority-queue\/leetcode-1705-maximum-number-of-eaten-apples\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1705. Maximum Number of Eaten Apples"},"content":{"rendered":"\n

There is a special kind of apple tree that grows apples every day for n<\/code> days. On the ith<\/sup><\/code> day, the tree grows apples[i]<\/code> apples that will rot after days[i]<\/code> days, that is on day i + days[i]<\/code> the apples will be rotten and cannot be eaten. On some days, the apple tree does not grow any apples, which are denoted by apples[i] == 0<\/code> and days[i] == 0<\/code>.<\/p>\n\n\n\n

You decided to eat at most<\/strong> one apple a day (to keep the doctors away). Note that you can keep eating after the first n<\/code> days.<\/p>\n\n\n\n

Given two integer arrays days<\/code> and apples<\/code> of length n<\/code>, return the maximum number of apples you can eat.<\/em><\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input:<\/strong> apples = [1,2,3,5,2], days = [3,2,1,4,2]\nOutput:<\/strong> 7\nExplanation:<\/strong> You can eat 7 apples:\n- On the first day, you eat an apple that grew on the first day.\n- On the second day, you eat an apple that grew on the second day.\n- On the third day, you eat an apple that grew on the second day. After this day, the apples that grew on the third day rot.\n- On the fourth to the seventh days, you eat apples that grew on the fourth day.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2]\nOutput:<\/strong> 5\nExplanation:<\/strong> You can eat 5 apples:\n- On the first to the third day you eat apples that grew on the first day.\n- Do nothing on the fouth and fifth days.\n- On the sixth and seventh days you eat apples that grew on the sixth day.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • apples.length == n<\/code><\/li>
  • days.length == n<\/code><\/li>
  • 1 <= n <= 2 * 104<\/sup><\/code><\/li>
  • 0 <= apples[i], days[i] <= 2 * 104<\/sup><\/code><\/li>
  • days[i] = 0<\/code> if and only if apples[i] = 0<\/code>.<\/li><\/ul>\n\n\n\n
    Solution: PriorityQueue<\/strong><\/h2>\n\n\n\n
    Sort by rotten day in ascending order, only push onto the queue when that day has come (be able to grow apples).<\/p>\n\n\n\n
    Time complexity: O((n+ d)logn)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int eatenApples(vector& apples, vector& days) {\n    const int n = apples.size();\n    using P = pair;    \n    priority_queue, greater
    > q; \/\/ {rotten_day, index}    \n    int ans = 0;\n    for (int d = 0; d < n || !q.empty(); ++d) {\n      if (d < n && apples[d]) q.emplace(d + days[d], d);\n      while (!q.empty() \n             && (q.top().first <= d || apples[q.top().second] == 0)) q.pop();\n      if (q.empty()) continue;\n      --apples[q.top().second];      \n      ++ans;\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    There is a special kind of apple tree that grows apples every day for n days. On the ith day, the tree grows apples[i] apples that will rot after days[i] days, that is…<\/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":[73,177,72,15],"class_list":["post-7861","post","type-post","status-publish","format-standard","hentry","category-priority-queue","tag-heap","tag-medium","tag-priority-queue","tag-sorting","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7861","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=7861"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7861\/revisions"}],"predecessor-version":[{"id":7863,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7861\/revisions\/7863"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7861"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7861"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7861"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}