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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Number of Eaten Apples

Number: 1824

Difficulty: Medium

Paid? No

Companies: Oracle, Adobe, Uber

Problem Description

You are given two arrays: apples and days. On the ith day, the tree produces apples[i] apples that will rot after days[i] days (specifically, on day i + days[i]). You can eat at most one apple per day, and you can continue eating even after the n days. Determine the maximum number of apples you can eat without consuming any rotten ones.

Key Insights

  • Use a min-heap (priority queue) to efficiently track apples with their expiration dates.
  • Each heap element stores a pair: (expiry day, number of apples remaining).
  • As days progress, add new apples with their expiry date to the heap.
  • Remove any apples from the heap whose expiry day is less than or equal to the current day.
  • Always consume an apple from the batch with the earliest expiry to maximize the number of edible apples.
  • Continue the process even after processing the given days until no valid apples remain in the heap.

Space and Time Complexity

Time Complexity: O(n log n), where n is the number of days. Each day may involve heap push and pop operations. Space Complexity: O(n) in the worst case when many batches of apples are stored in the heap.

Solution

The solution employs a greedy approach using a min-heap (priority queue). As you iterate over each day:

  1. If new apples are produced (apples[i] > 0), push a pair (i + days[i], apples[i]) into the heap, indicating the expiration day and count.
  2. Remove expired batches from the heap by checking the top element's expiration date.
  3. If the heap is non-empty, remove one apple from the batch with the smallest expiration day (to avoid wastage). If the batch still has remaining apples, update and push it back.
  4. Continue this process for all days, and even after the n days until the heap is empty.

This method ensures that apples are eaten in an order that minimizes waste due to rotting.

Code Solutions

import heapq

def eatenApples(apples, days):
    # min-heap to store (expiry day, number of apples remaining)
    apple_heap = []
    total_eaten = 0
    day = 0
    n = len(apples)
    
    # Loop until all days are processed and no apples remain in the heap
    while day < n or apple_heap:
        # If there are new apples available on this day, add them to the heap
        if day < n and apples[day] > 0:
            # Push tuple (expiry_day, count)
            heapq.heappush(apple_heap, (day + days[day], apples[day]))
        
        # Remove expired apples from heap
        while apple_heap and apple_heap[0][0] <= day:
            heapq.heappop(apple_heap)
        
        # If there are any valid apples, eat one apple from the batch with the earliest expiry
        if apple_heap:
            expiry, count = heapq.heappop(apple_heap)
            # Eat one apple
            total_eaten += 1
            # If there are more apples left in the batch, push the updated count back to the heap
            if count - 1 > 0:
                heapq.heappush(apple_heap, (expiry, count - 1))
        
        # Move to the next day
        day += 1

    return total_eaten

# Example usage:
# apples = [1,2,3,5,2]
# days = [3,2,1,4,2]
# print(eatenApples(apples, days))  # Output should be 7
← Back to All Questions