> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/heap/1705.-maximum-number-of-eaten-apples.md).

# 1705. Maximum Number of Eaten Apples

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

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`.

apples\[i]表示在第i天能得到多少苹果，该天得到的苹果会在days\[i]后腐烂，问每天最多吃一个苹果，最后最多能吃到多少苹果。遍历每一天，贪心的每次选最快过期的苹果吃一个，选最早/小用heap。

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