Formatted question description: https://leetcode.ca/all/1705.html

1705. Maximum Number of Eaten Apples (Medium)

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 if apples[i] = 0.

Related Topics:
Heap, Greedy

Solution 1.

We greedily pick the apples with smallest end time.

// OJ: https://leetcode.com/problems/maximum-number-of-eaten-apples/

// 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/

// 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;
    }
};

Java

class Solution {
    public int eatenApples(int[] apples, int[] days) {
        int maxApples = 0;
        TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
        int length = apples.length;
        for (int i = 0; i < length; i++) {
            int apple = apples[i], day = days[i];
            if (apple != 0) {
                int maxDay = i + day - 1;
                int count = map.getOrDefault(maxDay, 0) + apple;
                map.put(maxDay, count);
            }
            while (!map.isEmpty() && map.firstKey() < i)
                map.remove(map.firstKey());
            if (!map.isEmpty()) {
                Integer firstKey = map.firstKey();
                if (firstKey != null) {
                    maxApples++;
                    int count = map.get(firstKey) - 1;
                    if (count > 0)
                        map.put(firstKey, count);
                    else
                        map.remove(firstKey);
                }
            }
        }
        int index = length;
        while (!map.isEmpty()) {
            while (!map.isEmpty() && map.firstKey() < index)
                map.remove(map.firstKey());
            if (map.isEmpty())
                break;
            int firstKey = map.firstKey();
            if (firstKey >= index) {
                int count = map.get(firstKey);
                map.remove(firstKey);
                int curApples = Math.min(firstKey - index + 1, count);
                maxApples += curApples;
                index += curApples;
            } else
                break;
        }
        return maxApples;
    }
}

All Problems

All Solutions