Maximum Number of Eaten Apples — Medium Problem & Solution

Problem statement

A tree grows apples[i] apples on day i, and those apples rot after days[i] days — so they may be eaten on days i through i + days[i] - 1. Some days it grows nothing, marked by apples[i] == 0 and days[i] == 0.

You eat at most one apple a day, and you may keep eating after day n - 1. 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

Example 2

Input: apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2]
Output: 5

Example 3

Input: apples = [2,1,10], days = [2,10,1]
Output: 4

Constraints

• n == apples.length == days.length
• 1 <= n <= 2 * 10^4
• 0 <= apples[i], days[i] <= 2 * 10^4
• days[i] == 0 if and only if apples[i] == 0.

How to solve Maximum Number of Eaten Apples

Greedy with a min-heap keyed on rot day. Each day, add that day's batch, throw away everything that has already rotted, and eat one apple from the batch that expires soonest.

Approach

1. For day i < n with apples[i] > 0, push (i + days[i], apples[i]).
2. Discard every batch whose rot day is at most the current day.
3. If anything is left, eat one apple from the soonest-rotting batch and drop it when it empties.
4. Continue past day n - 1 while any batch survives.

Why it works

Eating from the soonest-rotting batch is optimal by an exchange argument: choosing any other batch today risks losing the sooner one entirely, while the later batch is still there tomorrow. The loop must run past n - 1, since apples grown on the last day may stay edible for a long time.

Complexity

• Time — O((n + maxDays) log n)
• Space — O(n)

Pitfalls

• A batch rots on day i + days[i], so it is edible up to the day before.
• Stopping the loop at day n - 1 throws away still-edible apples.
• Days with apples[i] == 0 add nothing but still count as a day you may eat on.

Reference solution

Python

from typing import List
import heapq

def eatenApples(apples: List[int], days: List[int]) -> int:
    n = len(apples)
    heap = []
    eaten = 0
    day = 0
    while day < n or heap:
        if day < n and apples[day] > 0:
            heapq.heappush(heap, (day + days[day], apples[day]))
        while heap and heap[0][0] <= day:
            heapq.heappop(heap)
        if heap:
            rot, cnt = heapq.heappop(heap)
            eaten += 1
            if cnt - 1 > 0:
                heapq.heappush(heap, (rot, cnt - 1))
        day += 1
    return eaten

JavaScript

var eatenApples = function(apples, days) {
    var n = apples.length;
    var batch = [];
    var eaten = 0, day = 0, i;
    while (day < n || batch.length > 0) {
        if (day < n && apples[day] > 0) batch.push([day + days[day], apples[day]]);
        for (i = batch.length - 1; i >= 0; i--) {
            if (batch[i][0] <= day) batch.splice(i, 1);
        }
        if (batch.length > 0) {
            var best = 0;
            for (i = 1; i < batch.length; i++) if (batch[i][0] < batch[best][0]) best = i;
            batch[best][1]--;
            eaten++;
            if (batch[best][1] === 0) batch.splice(best, 1);
        }
        day++;
    }
    return eaten;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Minimum Number of Increments on Subarrays to Form a Target Array Medium
• Find the Winner of an Array Game Medium
• Queries on a Permutation With Key Medium
• Corporate Flight Bookings Medium
• Find the Winner of the Circular Game Medium
• Longest Subsequence With Limited Sum Medium