Maximum Number of Eaten Apples

January 26, 2024

Problem Statement #

There is a special apple tree that grows several types of apples at different rates. The apples mature at different times, and they rot at different times after maturing. You are given two integer arrays apples and days, both of the same length. The i-th element of each array represents the number of apples that mature and the number of days they stay fresh, respectively, starting from the i-th day. You can only eat one apple each day, and you cannot keep any uneaten apples overnight. Return the maximum number of apples you can eat.

Example:

1. Input: apples = [1,2,3,5,2], days = [3,2,1,4,2] Output: 7 Explanation: Eat an apple every day to achieve the maximum number of 7 apples.

Solution Approach #

The solution uses a min-heap to efficiently manage the apples’ expiry dates.

Algorithm Steps #

1. Use a min-heap to store the expiry date and count of apples.
2. For each day, add new apples and their expiry dates to the heap.
3. Eat the apple that is closest to expiring and remove expired apples.
4. Continue until all apples are eaten or have expired.
5. Count the total number of apples eaten.

Code (Python) #

import heapq

def eatenApples(apples, days):
    min_heap = []  # (expiry date, apple count)
    day = 0
    total_eaten = 0

    while day < len(apples) or min_heap:
        # Add new apples
        if day < len(apples) and apples[day] > 0:
            heapq.heappush(min_heap, (day + days[day], apples[day]))
        
        # Remove expired apples
        while min_heap and min_heap[0][0] <= day:
            heapq.heappop(min_heap)

        # Eat an apple
        if min_heap:
            expiry, count = heapq.heappop(min_heap)
            if count > 1:
                heapq.heappush(min_heap, (expiry, count - 1))
            total_eaten += 1

        day += 1

    return total_eaten

# Test the function
print(eatenApples([1,2,3,5,2], [3,2,1,4,2]))  # Output: 7

Time Complexity #

O(n log n), where n is the number of days. Heap operations contribute to the log n factor.

Space Complexity #

O(n), for the heap.