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, eat an apple that grew on the first day.
- On the second day, eat an apple that grew on the second day.
- On the third day, eat another apple that grew on the second day. After this day, the apples grown on the third day have already rotted.
- From the fourth day through the seventh day, eat apples that grew on the fourth day.

Input: apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2]
Output: 5
Explanation: You can eat 5 apples:
- From the first day through the third day, eat apples that grew on the first day.
- Do not eat an apple on the fourth or fifth day.
- On the sixth and seventh days, eat apples that grew on the sixth day.

Analysis

#

Because you can eat at most one apple per day, the optimal strategy is to eat the apple that will expire earliest after the current day. This strategy is also common in everyday life: people generally eat the food they own that is closest to its expiration date first, which minimizes waste and lets them eat as many apples as possible.

Following this strategy, use an array rots to record when apples expire, and use eatId to track the expiration day of the earliest apple currently available. On each day, we only need to do the following (assume the current day is i and array indices start at 1, as in the problem statement):

• First ensure that eatId, the earliest expiration day among the apples that can currently be eaten, is at least the current day.
• Then process the apples harvested today. If today produces a apples that rot after n days, add them to rots by setting rots[i + n - 1] += a. We cannot eat this batch on day i+n, so its last edible day is i+n-1.
• Finally choose an apple to eat. If eatId is later than the expiration day of today’s new batch, set eatId to today’s expiration day; in other words, if today’s new apples rot sooner, eat them first.
• After choosing an edible apple (if rots[eatId] is zero, there are no apples left on the currently selected day, so advance eatId to a day that still has apples; by definition, eatId is the nearest expiration day, so it can only move forward), increment the answer and decrement rots[eatId] by 1. If no apples remain, eat nothing.

Rust Code

#

impl Solution {
    pub fn eaten_apples(apples: Vec<i32>, days: Vec<i32>) -> i32 {
        let mut rots = [0; 40005];
        let mut eatId = 0;
        let mut res = 0;
        for index in 1..40003 {
            eatId = eatId.max(index);
            if index <= apples.len() && apples[index - 1] != 0 {
                rots[index - 1 + days[index - 1] as usize] += apples[index - 1];
                eatId = eatId.min(index - 1 + days[index - 1] as usize);
            }
            while rots[eatId] == 0 && eatId < 40002 {
                eatId += 1;
            }
            if eatId != 40002 {
                rots[eatId] -= 1;
                res += 1;
            }
        }
        res
    }
}