Maximum Number Of Eaten Apples - Leetcode Solution

Problem Statement:

There is a special kind of apple tree that grows apples every day for n days. On the ith day, the tree generates 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 each day, you can eat at most one apple from the tree but only if the apple is not rotten.

Given two integer arrays apples and days of length n, return the maximum number of apples you can eat.

Solution:

To solve this problem, we will use a priority queue (heapq module in python) to store the number of apples that are not rotten and sort them based on their expiration date. We will iterate over the days from i = 0 to i = n-1.

On each day, we will check the apples that have expired on the previous day(s) and remove them from the priority queue. We will then add the number of apples that are generated on the current day to the priority queue. If there are no more apples left in the priority queue, we move on to the next day.

We keep a count of the number of apples that we have eaten and continue until we have eaten all the apples that are not rotten or the days have ended.

Algorithm:

1. Create an empty priority queue (min heap) to store apples.
2. Initialize variables eatenApples = 0 and i = 0.
3. While i < n or the priority queue is not empty: a. Remove all the apples that have expired on previous days from the priority queue. b. If there are apples left in the priority queue: i. Eat one apple and increment eatenApples ii. Reduce the expiration date of the apple by 1 day. c. If there are no more apples left in the priority queue and i < n: i. Add the apples[i] to the priority queue with expiration date days[i]+i ii. Increment i.
4. Return eatenApples.

Python Code:

import heapq

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

    pq = []  # Priority queue to store apples
    eatenApples = 0
    n = len(apples)
    i = 0
    
    while i < n or pq:
        # Remove all the apples that have expired on previous days
        while pq and pq[0][0] <= i:
            heapq.heappop(pq)
            
        if pq:
            # Eat one apple
            apple, expire = heapq.heappop(pq)
            apple -= 1
            eatenApples += 1
            
            if apple > 0:
                # Add the apple back to the priority queue
                heapq.heappush(pq, (apple, expire))
        elif i < n:
            # Add the apples[i] to the priority queue with expiration date days[i]+i
            if apples[i] > 0:
                heapq.heappush(pq, (apples[i], i+days[i]))
                
            i += 1
            
    return eatenApples

Time Complexity:

The time complexity of this algorithm is O(n log n) because we are using a priority queue to store the apples and each operation on the priority queue takes O(log n) time.

Space Complexity:

The space complexity of this algorithm is O(n) because we are using a priority queue to store the apples.

1