We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Eaten Apples

Difficulty: Medium

Problem Description

Given two integer arrays apples and days of length n, representing the number of apples grown on each day and the number of days until they rot, return the maximum number of apples you can eat if you can eat at most one apple a day.

Key Insights

  • You can eat apples that are still fresh (not rotten).
  • Each apple has a specific lifespan defined by the days array.
  • You can continue eating after the initial n days, which allows for the consumption of rotting apples if they are still available.
  • A greedy approach can be beneficial by focusing on the freshest apples available each day.

Space and Time Complexity

Time Complexity: O(n log n) - Due to the priority queue operations. Space Complexity: O(n) - For the priority queue to store the apples.

Solution

To solve this problem, we can use a max-heap (priority queue) to keep track of the apples that can be eaten over time. For each day, we check if any fresh apples are available, and we prioritize eating apples that are about to rot soonest. This way, we maximize the number of apples consumed while ensuring we don’t let any apples rot unnecessarily.

  1. Use a max-heap to manage the apples that can be eaten.
  2. Iterate over the days:
    • Add new apples to the heap.
    • Remove apples from the heap that have rotted.
    • Consume one apple from the heap if available.
  3. Continue this process until all possible apples have been consumed.

Code Solutions

import heapq

def maxEatenApples(apples, days):
    max_heap = []
    total_eaten = 0
    n = len(apples)
    
    for day in range(n):
        # Add today's apples to the heap
        if apples[day] > 0:
            heapq.heappush(max_heap, (day + days[day], apples[day]))
        
        # Remove rotten apples from the heap
        while max_heap and max_heap[0][0] <= day:
            heapq.heappop(max_heap)
        
        # Eat one apple if there are any available
        if max_heap:
            total_eaten += 1
            # Update the count of apples remaining
            remaining_apples = max_heap[0][1] - 1
            if remaining_apples > 0:
                max_heap[0] = (max_heap[0][0], remaining_apples)
            else:
                heapq.heappop(max_heap)  # Remove the entry if all apples are eaten
    
    # Continue eating after the last day
    day += 1
    while max_heap:
        # Remove rotten apples from the heap
        while max_heap and max_heap[0][0] <= day:
            heapq.heappop(max_heap)
        
        if max_heap:
            total_eaten += 1
            remaining_apples = max_heap[0][1] - 1
            if remaining_apples > 0:
                max_heap[0] = (max_heap[0][0], remaining_apples)
            else:
                heapq.heappop(max_heap)  # Remove the entry if all apples are eaten
        day += 1
    
    return total_eaten
← Back to All Questions