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 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: 7 Explanation: 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: 5 Explanation: 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 * 104
0 <= apples[i], days[i] <= 2 * 104
days[i] = 0
if and only ifapples[i] = 0
.
We greedily pick the apples with smallest end time.
// OJ: https://leetcode.com/problems/maximum-number-of-eaten-apples/
// Author: github.com/lzl124631x
// Time: O(SUM(A) * logN)
// Space: O(N)
class Solution {
public:
int eatenApples(vector<int>& A, vector<int>& D) {
int N = A.size(), ans = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; // end time, cnt
for (int i = 0; i < N || pq.size(); ++i) {
while (pq.size()) {
auto [end, cnt] = pq.top(); // remove rotten apples
if (end <= i) pq.pop();
else break;
}
if (i < N && A[i] != 0) pq.emplace(i + D[i], A[i]);
if (pq.size()) { // greedily use the one with the smallest end time
auto [end, cnt] = pq.top();
pq.pop();
++ans;
if (cnt - 1 > 0) pq.emplace(end, cnt - 1);
}
}
return ans;
}
};
When i >= N
, we don't need to pick the apples one by one. Instead, we can take all the apples in ascending order of the end time as long as it's not rotten.
// OJ: https://leetcode.com/problems/maximum-number-of-eaten-apples/
// Author: github.com/lzl124631x
// Time: O(SUM(A) * logN)
// Space: O(N)
class Solution {
public:
int eatenApples(vector<int>& A, vector<int>& D) {
int N = A.size(), day = N, ans = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq; // end time, cnt
for (int i = 0; i < N; ++i) {
while (pq.size()) {
auto [end, cnt] = pq.top(); // remove rotten apples
if (end <= i) pq.pop();
else break;
}
if (i < N && A[i] != 0) pq.emplace(i + D[i], A[i]);
if (pq.size()) { // greedily use the one with the smallest end time
auto [end, cnt] = pq.top();
pq.pop();
++ans;
if (cnt - 1 > 0) pq.emplace(end, cnt - 1);
}
}
while (pq.size()) {
auto [end, cnt] = pq.top();
pq.pop();
if (end <= day) continue;
int c = min(cnt, end - day);
ans += c;
day += c;
}
return ans;
}
};