1705. Maximum Number of Eaten Apples

Problem

There is a special kind of apple tree that grows apples every day for n days. On the iᵗʰ 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.

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

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 * 10⁴
0 <= apples[i], days[i] <= 2 * 10⁴
days[i] = 0 if and only if apples[i] = 0.

Test Cases

1 2	class Solution: def eatenApples(self, apples: List[int], days: List[int]) -> int:

solution_test.py

import pytest

from solution import Solution


@pytest.mark.parametrize('apples, days, expected', [
    ([1,2,3,5,2], [3,2,1,4,2], 7),
    ([3,0,0,0,0,2], [3,0,0,0,0,2], 5),

    ([9,2], [3,5], 5),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, apples, days, expected):
    assert sol.eatenApples(apples, days) == expected

Thoughts

显然每天都应该吃最快要过期的苹果（先吃快烂了的苹果，还是先吃最新鲜的苹果，似乎是两种不同的生活态度）。

利用最小堆做成优先队列，每天收获的新苹果，计算出保质期是到哪天，放入堆中。堆顶是过期时间最早的苹果。

每天检查堆顶的苹果是否已经到期或过期，是就丢弃。否则就吃掉一个堆顶的苹果。如果这一拨苹果吃光了，则弹出。

n 天之后，不会再有新的苹果，可以一次计算出堆顶的一拨苹果最多能吃几天，不用真的一天一天地累加。

Code

solution.py

from heapq import heappop, heappush


class Solution:
    def eatenApples(self, apples: list[int], days: list[int]) -> int:
        min2 = lambda a, b: a if a <= b else b
        store: list[list[int]] = [] # Min-heap of [expiry, count].
        eaten = 0
        for d, cnt in enumerate(apples):
            while store and d >= store[0][0]:
                heappop(store) # Drop rotten apples.

            if apples[d] > 0:
                heappush(store, [d + days[d], apples[d]]) # Save today's new apples in store.

            if store:
                eaten += 1 # Eat an apple which is most likely to rot.
                store[0][1] -= 1
                if store[0][1] == 0:
                    heappop(store)

        d += 1
        while store:
            expiry, cnt = heappop(store)
            if d >= expiry:
                continue # Drop rotten apples.

            cnt = min2(cnt, expiry - d)
            eaten += cnt # Eat all apples which are most likely to rot, before rotten.
            d += cnt

        return eaten

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。