There is a special kind of apple tree that grows apples every day for `n`

days. On the `i`

day, the tree grows ^{th}`apples[i]`

apples that will rot after `days[i]`

days, that is on day `i + days[i]`

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`

and `days[i] == 0`

.

You decided to eat **at most** one apple a day (to keep the doctors away). Note that you can keep eating after the first `n`

days.

Given two integer arrays `days`

and `apples`

of length `n`

, return *the maximum number of apples you can eat.*

**Example 1:**

Input:apples = [1,2,3,5,2], days = [3,2,1,4,2]Output:7Explanation:You can eat 7 apples: - On the first day, you eat an apple that grew on the first day. - On the second day, you eat an apple that grew on the second day. - 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. - On the fourth to the seventh days, you eat apples that grew on the fourth day.

**Example 2:**

Input:apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2]Output:5Explanation:You can eat 5 apples: - On the first to the third day you eat apples that grew on the first day. - Do nothing on the fouth and fifth days. - On the sixth and seventh days you eat apples that grew on the sixth day.

**Constraints:**

`apples.length == n`

`days.length == n`

`1 <= n <= 2 * 10`

^{4}`0 <= apples[i], days[i] <= 2 * 10`

^{4}`days[i] = 0`

if and only if`apples[i] = 0`

.

**Solution: PriorityQueue**

Sort by rotten day in ascending order, only push onto the queue when that day has come (be able to grow apples).

Time complexity: O((n+ d)logn)

Space complexity: O(n)

## C++

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua class Solution { public: int eatenApples(vector<int>& apples, vector<int>& days) { const int n = apples.size(); using P = pair<int, int>; priority_queue<P, vector<P>, greater<P>> q; // {rotten_day, index} int ans = 0; for (int d = 0; d < n || !q.empty(); ++d) { if (d < n && apples[d]) q.emplace(d + days[d], d); while (!q.empty() && (q.top().first <= d || apples[q.top().second] == 0)) q.pop(); if (q.empty()) continue; --apples[q.top().second]; ++ans; } return ans; } }; |