Leetcode 1705. Maximum Number of Eaten Apples

Problem Explanation

You have an apple tree that grows apples every day for n days. Each day, the tree may grow a certain number of apples, as indicated by the list apples[i], and these apples will rot after some number of days given by the list days[i]. Note that on some days, the tree may not grow any apples, in which case both apples[i] and days[i] will be 0. Your task is to eat at most one apple a day and find the maximum number of apples that can be eaten.

Walk Through an Example

Let's go through an example to understand the problem better. We have two lists: apples = [1,2,3,5,2] and days = [3,2,1,4,2]

On the first day, the tree grows 1 apple, and this apple can be eaten within 3 days. On the second day, the tree grows another 2 apples that can be eaten within next 2 days. Similarly, on subsequent days, we keep track of the apples and their expiration days.

To maximize the number of eaten apples, we can prioritize eating apples that will expire sooner. For that, we can use a priority queue to store the apples with their expiration days. When we come to a new day, we can first eat the apples which will rot soonest.

Approach

1. Use a priority queue to store (expiration_day, apples) tuples.
2. Loop through each day and do the following:
   • Add the apples grown on that day with their expiration days, to the priority queue.
   • Pop an apple from the priority queue that will expire soonest - eat it and remove it from the queue.
   • If there is already a rotten apple in the queue, remove it from the queue.
3. Keep track of the total number of apples eaten.

Explanation Using an Example

Consider the example, apples = [1, 2, 3, 5, 2], and days = [3, 2, 1, 4, 2].

1. For i=0 (day 1), there is 1 apple grown, which will expire in 3 days. We eat this apple, and the count of apples eaten is 1.
2. For i=1 (day 2), there are 2 apples grown, which will expire in 2 days. We eat one of these apples, and the count of apples eaten is 2.
3. For i=2 (day 3), there are 3 apples grown, which expire in 1 day. But since these apples expire today, we don't consider them in the queue. Continue to eat one of the apples grown on day 2, and the count of apples eaten is now 3.
4. For i=3 (day 4), there are 3 apples grown on day 4, which expire in 4 days. Eat the last remaining apple from day 2, and then eat apples from day 4 for the next 3 days. The count of apples eaten is now 7.

In this example, you can eat a maximum of 7 apples.

Python Solution

1import heapq
2
3class Solution:
4    def eatenApples(self, apples, days):
5        priority_queue = []
6        total_apples_eaten = 0
7        
8        for i in range(len(apples)):
9            if apples[i] > 0:
10                heapq.heappush(priority_queue, (i+days[i], apples[i]))
11            
12            while priority_queue and priority_queue[0][0] <= i:
13                heapq.heappop(priority_queue)
14
15            if priority_queue:
16                rotten_day, remaining_apples = heapq.heappop(priority_queue)
17                total_apples_eaten += 1
18                remaining_apples -= 1
19                
20                if remaining_apples > 0:
21                    heapq.heappush(priority_queue, (rotten_day, remaining_apples))
22        
23        # Continue to eat apples after n days
24        while priority_queue and priority_queue[0][0] <= i + 1:
25            heapq.heappop(priority_queue)
26        
27        while priority_queue:
28            i += 1
29            rotten_day, remaining_apples = heapq.heappop(priority_queue)
30            total_apples_eaten += min(rotten_day - i, remaining_apples)
31        
32        return total_apples_eaten

Java Solution

1import java.util.PriorityQueue;
2
3class Solution {
4    public int eatenApples(int[] apples, int[] days) {
5        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((a,b) -> a[0] - b[0]);
6        int totalApplesEaten = 0;
7
8        for (int i = 0; i < apples.length; i++) {
9            if (apples[i] > 0) {
10                priorityQueue.offer(new int[]{i + days[i], apples[i]});
11            }
12
13            while (!priorityQueue.isEmpty() && priorityQueue.peek()[0] <= i) {
14                priorityQueue.poll();
15            }
16
17            if (!priorityQueue.isEmpty()) {
18                int[] rottenDayRemainingApples = priorityQueue.poll();
19                totalApplesEaten++;
20                rottenDayRemainingApples[1]--;
21
22                if (rottenDayRemainingApples[1] > 0) {
23                    priorityQueue.offer(rottenDayRemainingApples);
24                }
25            }
26        }
27
28        // Continue to eat apples after n days
29        while (!priorityQueue.isEmpty() && priorityQueue.peek()[0] <= i + 1) {
30            priorityQueue.poll();
31        }
32
33        while (!priorityQueue.isEmpty()) {
34            int[] rottenDayRemainingApples = priorityQueue.poll();
35            totalApplesEaten += Math.min(rottenDayRemainingApples[0] - i, rottenDayRemainingApples[1]);
36            i++;
37        }
38
39        return totalApplesEaten;
40    }
41}

JavaScript Solution

1class Solution {
2    eatenApples(apples, days) {
3        let priorityQueue = [];
4        let totalApplesEaten = 0;
5
6        function add_to_queue(rotten_day, apples) {
7            priorityQueue.push([rotten_day, apples]);
8            priorityQueue.sort((a, b) => a[0] - b[0]);
9        }
10
11        for (let i = 0; i < apples.length; i++) {
12            if (apples[i] > 0) {
13                add_to_queue(i + days[i], apples[i]);
14            }
15
16            while (priorityQueue.length > 0 && priorityQueue[0][0] <= i) {
17                priorityQueue.shift();
18            }
19
20            if (priorityQueue.length > 0) {
21                let rotten_day_apples = priorityQueue.shift();
22                totalApplesEaten++;
23                rotten_day_apples[1]--;
24
25                if (rotten_day_apples[1] > 0) {
26                    add_to_queue(rotten_day_apples[0], rotten_day_apples[1]);
27                }
28            }
29        }
30
31        // Continue to eat apples after n days
32        while (priorityQueue.length > 0 && priorityQueue[0][0] <= i + 1) {
33            priorityQueue.shift();
34        }
35
36        while (priorityQueue.length > 0) {
37            let rotten_day_apples = priorityQueue.shift();
38            totalApplesEaten += Math.min(rotten_day_apples[0] - i, rotten_day_apples[1]);
39            i++;
40        }
41
42        return totalApplesEaten;
43    }
44}

C++ Solution

1#include <queue>
2using namespace std;
3
4class Solution {
5public:
6    int eatenApples(vector<int>& apples, vector<int>& days) {
7        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> priorityQueue;
8        int totalApplesEaten = 0;
9        
10        for (int i = 0; i < apples.size(); i++) {
11            if (apples[i] > 0)
12                priorityQueue.push({i + days[i], apples[i]});
13            
14            while (!priorityQueue.empty() && priorityQueue.top().first <= i)
15                priorityQueue.pop();
16
17            if (!priorityQueue.empty()) {
18                auto rottenDayRemainingApples = priorityQueue.top();
19                priorityQueue.pop();
20                totalApplesEaten++;
21                rottenDayRemainingApples.second--;
22                
23                if (rottenDayRemainingApples.second > 0)
24                    priorityQueue.push(rottenDayRemainingApples);
25            }
26        }
27
28        // Continue to eat apples after n days
29        while (!priorityQueue.empty() && priorityQueue.top().first <= i + 1)
30            priorityQueue.pop();
31        
32        while (!priorityQueue.empty()) {
33            auto rottenDayRemainingApples = priorityQueue.top();
34            priorityQueue.pop();
35            totalApplesEaten += min(rottenDayRemainingApples.first - i, rottenDayRemainingApples.second);
36            i++;
37        }
38
39        return totalApplesEaten;
40    }
41};

C# Solution

1using System.Collections.Generic;
2using System.Linq;
3
4public class Solution {
5    public int EatenApples(int[] apples, int[] days) {
6        var priorityQueue = new SortedDictionary<int, int>();
7        int totalApplesEaten = 0;
8
9        for (int i = 0; i < apples.Length; i++) {
10            if (apples[i] > 0) {
11                int rottenDay = i + days[i];
12                int newApples = apples[i];
13                if (!priorityQueue.ContainsKey(rottenDay))
14                    priorityQueue[rottenDay] = newApples;
15                else
16                    priorityQueue[rottenDay] += newApples;
17            }
18            
19            while (priorityQueue.Count > 0 && priorityQueue.First().Key <= i)
20                priorityQueue.Remove(priorityQueue.First().Key);
21
22            if (priorityQueue.Count > 0) {
23                int rottenDay = priorityQueue.First().Key;
24                int remainingApples = priorityQueue.First().Value;
25                totalApplesEaten++;
26                remainingApples--;
27
28                if (remainingApples > 0) {
29                    priorityQueue[rottenDay] = remainingApples;
30                } else {
31                    priorityQueue.Remove(rottenDay);
32                }
33            }
34        }
35
36        // Continue to eat apples after n days
37        while (priorityQueue.Count > 0 && priorityQueue.First().Key <= i + 1)
38            priorityQueue.Remove(priorityQueue.First().Key);
39
40        while (priorityQueue.Count > 0) {
41            int rottenDay = priorityQueue.First().Key;
42            int remainingApples = priorityQueue.First().Value;
43            totalApplesEaten += System.Math.Min(rottenDay - i, remainingApples);
44            i++;
45        }
46
47        return totalApplesEaten;
48    }
49}

In summary, the problem of finding the maximum number of apples that can be eaten while eating at most one apple a day and considering their expiration days is solved by using a priority queue. The priority queue stores tuples of expiration days and apples count, allowing us to prioritize eating apples expiring sooner. We have provided solutions for Python, JavaScript, Java, C++, and C# languages.