# Maximum Number of Eaten Apples
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximum-number-of-eaten-apples)
Canonical: https://scaleengineer.com/dsa/problems/maximum-number-of-eaten-apples
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Heap (Priority Queue)
---
## Problem
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:**

* `n == apples.length == days.length`
* `1 <= n <= 2 * 104`
* `0 <= apples[i], days[i] <= 2 * 104`
* `days[i] = 0` if and only if `apples[i] = 0`.

# Approaches
## Brute-Force Simulation with Linear Scan
This approach simulates the process day by day in a straightforward manner. It maintains a simple list of all available apple batches, where a batch consists of apples that grew on the same day and share the same expiry date. For each day, it first adds any new apples that have grown. Then, to decide which apple to eat, it performs a linear scan through the entire list of available batches to find a non-rotten apple that will expire the soonest. After eating one, it moves to the next day. This process continues until no more apples can be grown or eaten.
**Time:** O(D * n), where `D` is the last day an apple can be eaten (roughly `n + max(days)`) and `n` is the length of the input arrays. The outer loop runs up to `D` times, and inside it, we scan a list of size up to `n`. This quadratic-like complexity is too slow for the given constraints. · **Space:** O(n), where n is the length of the input arrays. In the worst case, we might store a batch of apples for each of the n days.
**Pros:** Conceptually simple and easy to follow.; Directly translates the problem statement into code without complex data structures.
**Cons:** Extremely inefficient due to the nested loop structure (simulating days and scanning the list of apples).; The time complexity makes it too slow for the given constraints, leading to a 'Time Limit Exceeded' error on most platforms.
### Explanation
We use a simple list, for instance, an `ArrayList` in Java, to store pairs of `[expiryDate, count]` for each batch of apples. We then loop through time, day by day, starting from day 0.

In each iteration for day `d`:
1.  **Add New Apples**: If `d` is within the `n` days of growth (`d < n`) and `apples[d]` is positive, we calculate the expiry date `d + days[d]` and add a new entry `[expiryDate, apples[d]]` to our list.
2.  **Find Best Apple**: We search for the best apple to eat. We initialize a variable `bestAppleIndex` to -1 and `earliestExpiry` to infinity. We then iterate through our list of apple batches. For each batch, we check if it's not rotten (i.e., `expiryDate > d`) and if its `expiryDate` is earlier than the current `earliestExpiry`. If both conditions are met, we update `earliestExpiry` and `bestAppleIndex`.
3.  **Eat Apple**: If we found a valid apple to eat (`bestAppleIndex != -1`), we increment our total count of eaten apples and decrement the count of the chosen apple batch.
4.  **Advance Day**: We increment the day `d` to move to the next day.

The simulation stops when we are past the `n` days of growth and a check reveals there are no more edible apples left in our list.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int eatenApples(int[] apples, int[] days) {
        List<int[]> availableApples = new ArrayList<>();
        int eatenCount = 0;
        int n = apples.length;
        int currentDay = 0;

        // Loop until no more apples can be produced or eaten
        while (true) {
            // Add new apples that grow on the current day
            if (currentDay < n && apples[currentDay] > 0) {
                int expiryDay = currentDay + days[currentDay];
                int appleCount = apples[currentDay];
                availableApples.add(new int[]{expiryDay, appleCount});
            }

            // Find the non-rotten apple that will expire soonest
            int bestAppleIndex = -1;
            int earliestExpiry = Integer.MAX_VALUE;
            for (int i = 0; i < availableApples.size(); i++) {
                int[] batch = availableApples.get(i);
                // Check if the batch is not rotten and has apples
                if (batch[0] > currentDay && batch[1] > 0) {
                    if (batch[0] < earliestExpiry) {
                        earliestExpiry = batch[0];
                        bestAppleIndex = i;
                    }
                }
            }

            // If a suitable apple is found, eat it
            if (bestAppleIndex != -1) {
                eatenCount++;
                availableApples.get(bestAppleIndex)[1]--;
            }

            currentDay++;

            // Check for termination condition
            boolean hasEdibleApples = false;
            for (int[] batch : availableApples) {
                if (batch[0] > currentDay && batch[1] > 0) {
                    hasEdibleApples = true;
                    break;
                }
            }
            if (currentDay >= n && !hasEdibleApples) {
                break;
            }
        }
        return eatenCount;
    }
}
```
### Algorithm
- Initialize `eatenCount = 0`, `currentDay = 0`, and an empty list `availableApples` to store pairs of `[expiryDate, count]`.
- Start a loop to simulate the passage of time, day by day.
- Inside the loop for `currentDay`:
  - If `currentDay` is less than `n` and `apples[currentDay]` is positive, add a new batch `[currentDay + days[currentDay], apples[currentDay]]` to the `availableApples` list.
  - Linearly scan the `availableApples` list to find the batch that is not rotten (`expiryDate > currentDay`) and has the earliest `expiryDate`.
  - If such an apple batch is found, increment `eatenCount` and decrement the apple count of that batch.
  - Increment `currentDay`.
- The loop terminates when `currentDay` is past `n` and there are no more edible apples left in the `availableApples` list.
- Return the total `eatenCount`.

## Greedy Approach with Min-Priority Queue
A much more efficient approach is to use a greedy strategy. The optimal strategy is to always eat an apple that will rot the soonest. This maximizes the chances of eating apples that would otherwise be wasted, while preserving apples with a longer shelf life for later days. A min-priority queue is the perfect data structure to implement this. It can store apple batches (represented by their expiry date and count) and allows for efficient retrieval of the batch with the earliest expiry date.
**Time:** O(D * log n), where `D` is the last day an apple can be eaten (at most `n + max(days)`) and `n` is the number of days apples grow. The main loop runs `D` times, and each iteration involves a few priority queue operations, which take `O(log n)` time. This is efficient enough for the given constraints. · **Space:** O(n), where n is the number of days apples grow. In the worst-case scenario, the priority queue might need to store a distinct batch of apples for each of the `n` days.
**Pros:** Highly efficient and provides the optimal solution.; The greedy choice is provably correct for this problem.; Passes all test cases within the given time and memory constraints.
**Cons:** Requires knowledge of priority queues (min-heaps).; Slightly more complex to implement compared to a simple list-based simulation.
### Explanation
This approach uses a min-priority queue (min-heap) to keep track of the available apples. The priority queue will store arrays or objects containing two pieces of information: the expiry date and the number of apples in that batch. The queue is ordered based on the expiry date, so the batch that will expire soonest is always at the top.

The simulation proceeds day by day:
1.  **Data Structure**: We use a `PriorityQueue<int[]>` in Java, where each `int[]` is a pair `{expiryDate, count}`. We provide a custom comparator to sort by `expiryDate`.
2.  **Iteration**: We loop with a day counter `d`, starting from 0. The loop continues as long as we are within the `n` days of growth or there are still apples in our priority queue.
3.  **Add New Apples**: On day `d`, if `d < n` and `apples[d] > 0`, we add a new batch `{d + days[d], apples[d]}` to the priority queue. This operation takes `O(log k)` time, where `k` is the current size of the queue.
4.  **Remove Rotten Apples**: Before eating, we must discard any apples that have already rotted. We peek at the top of the queue and, as long as it's not empty and its expiry date is less than or equal to the current day `d`, we poll it from the queue.
5.  **Eat an Apple**: After cleaning up, if the queue is not empty, we can eat an apple. We poll the top batch (the one expiring soonest), increment our `eatenApples` count, and decrement its apple count. If apples remain in this batch (`count > 0`), we add it back to the queue.

This process ensures that on any given day, we make the optimal greedy choice, leading to the maximum number of eaten apples.

```java
import java.util.PriorityQueue;

class Solution {
    public int eatenApples(int[] apples, int[] days) {
        // Min-heap storing pairs of [expiryDay, appleCount]
        // Ordered by expiryDay
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        
        int eatenCount = 0;
        int n = apples.length;
        int i = 0;
        
        // Loop continues as long as there are days left to grow apples (i < n)
        // or there are still apples in the priority queue to be eaten.
        while (i < n || !pq.isEmpty()) {
            // 1. Add apples that grow today
            if (i < n && apples[i] > 0) {
                int expiryDay = i + days[i];
                int appleCount = apples[i];
                pq.offer(new int[]{expiryDay, appleCount});
            }
            
            // 2. Remove rotten apples from the top of the queue
            while (!pq.isEmpty() && pq.peek()[0] <= i) {
                pq.poll();
            }
            
            // 3. Eat one apple if available
            if (!pq.isEmpty()) {
                eatenCount++;
                int[] earliestBatch = pq.poll();
                earliestBatch[1]--;
                // If there are still apples left in this batch, add it back
                if (earliestBatch[1] > 0) {
                    pq.offer(earliestBatch);
                }
            }
            
            // Move to the next day
            i++;
        }
        
        return eatenCount;
    }
}
```
### Algorithm
- Initialize a min-priority queue `pq` to store `[expiryDate, count]` pairs, ordered by `expiryDate`.
- Initialize `eatenCount = 0` and the current day `d = 0`.
- Loop as long as there are days left for apples to grow (`d < n`) or there are still apples in the `pq`.
- Inside the loop:
  - If `d < n` and `apples[d] > 0`, add the new batch `[d + days[d], apples[d]]` to the `pq`.
  - Remove all rotten apple batches from the top of the `pq`. A batch is rotten if its `expiryDate <= d`.
  - If the `pq` is not empty after removing rotten ones, it means there's an edible apple. Eat one from the top batch (which expires soonest).
  - To do this, increment `eatenCount`, `poll()` the top batch, decrement its count, and if the count is still positive, `offer()` it back to the `pq`.
  - Increment the day `d`.
- Return `eatenCount` after the loop terminates.

# Solutions
### Java

```java
class Solution {
public
  int eatenApples(int[] apples, int[] days) {
    PriorityQueue<int[]> q =
        new PriorityQueue<>(Comparator.comparingInt(a->a[0]));
    int n = days.length;
    int ans = 0, i = 0;
    while (i < n || !q.isEmpty()) {
      if (i < n && apples[i] > 0) {
        q.offer(new int[]{i + days[i] - 1, apples[i]});
      }
      while (!q.isEmpty() && q.peek()[0] < i) {
        q.poll();
      }
      if (!q.isEmpty()) {
        var p = q.poll();
        ++ans;
        if (--p[1] > 0 && p[0] > i) {
          q.offer(p);
        }
      }
      ++i;
    }
    return ans;
  }
}

```

### CPP

```cpp
using pii = pair < int , int > ; class Solution { public: int eatenApples ( vector < int >& apples , vector < int >& days ) { priority_queue < pii , vector < pii > , greater < pii >> q ; int n = days . size (); int ans = 0 , i = 0 ; while ( i < n || ! q . empty ()) { if ( i < n && apples [ i ]) q . emplace ( i + days [ i ] - 1 , apples [ i ]); while ( ! q . empty () && q . top (). first < i ) q . pop (); if ( ! q . empty ()) { auto [ t , v ] = q . top (); q . pop (); -- v ; ++ ans ; if ( v && t > i ) q . emplace ( t , v ); } ++ i ; } return ans ; } };
```

### Python

```python
class Solution:
    def eatenApples(self, apples: List[int], days: List[int]) -> int: n = len(days) i = ans = 0 q = [] while i < n or q: if i < n and apples[i]: heappush(q, (i + days[i] - 1, apples[i])) while q and q[0][0] < i: heappop(q) if q: t, v = heappop(q) v -= 1 ans += 1 if v and t > i: heappush(q, (t, v)) i += 1 return ans

```