Maximum Number Of Eaten Apples
01 · Problem
An apple tree is observed for n days. On day i (0-indexed) it produces apples[i] apples, and those apples go bad at the start of day i + days[i], so they can be eaten on days i through i + days[i] - 1. On some days the tree produces nothing; this is shown as apples[i] == 0 and days[i] == 0.
You may eat at most one apple per day, and you may keep eating after day n - 1 as long as you still hold apples that have not gone bad.
Return the maximum total number of apples you can eat.
02 · Examples
apples = [1,2,3,5,2], days = [3,2,1,4,2]
7
Eat one apple every day from day 0 to day 6, always from the batch that spoils soonest (e.g. the day-4 apples are eaten on days 4 and 5 before returning to the day-3 batch, which lasts through day 6). From day 7 everything has gone bad. Total = 7.
apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2]
5
Eat the three day-0 apples on days 0, 1 and 2, nothing is available on days 3 and 4, then eat the two day-5 apples on days 5 and 6. Total = 5.
apples = [2,1], days = [1,1]
2
The day-0 apples spoil after one day, so only one can be eaten on day 0. The day-1 apple is eaten on day 1. Total = 2.
03 · Constraints
- 01n == apples.length == days.length
- 021 <= n <= 2 * 104
- 030 <= apples[i], days[i] <= 2 * 104
- 04apples[i] == 0 if and only if days[i] == 0
04 · Optimal complexity
- Time
- O(n log n)
- Space
- O(n)
Practice it alone or rehearse it as an interview.
Practice Mode gives you an editor and test runs, nothing else. AI Interview Mode puts a voice interviewer on the other side, adds a clock, and ends with a scored summary of the round.