Maximum Number of Eaten Apples (Priority Queue)

To solve the Maximum Number of Eaten Apples problem, I would approach it using a greedy strategy supported by a Min-Heap. The core logic is that we should always consume the apples that are closest to spoiling to minimize waste. First, I would initialize a priority queue ordered by expiration date. As we iterate through each day, we add any newly grown apples to our heap, recording their specific expiration date and quantity. Before eating, we clean the heap by removing any entries where the current day exceeds the expiration date. If the heap still contains valid apples, we extract the one with the earliest expiration, increment our total count, and decrement its remaining quantity. If the quantity drops to zero, we remove it from the heap entirely. This process continues until both the input array is exhausted and the heap is empty. For example, if on Day 1 we get 5 apples expiring on Day 3, and on Day 2 we get 3 expiring on Day 4, we prioritize the Day 3 apples. This ensures optimal usage. Regarding complexity, since we push and pop from the heap at most once per apple batch, the time complexity is O(N log N), where N is the number of days. The space complexity is O(N) to store the heap elements. This approach mirrors Airbnb's need for efficient resource management in dynamic environments.