Maximum Number of Eaten Apples

Maximum Number of Eaten Apples

What is this problem about?

The Maximum Number of Eaten Apples coding problem simulates daily apple eating. Each day i, you receive apples[i] apples that will expire after days[i] days from day i (i.e., they expire at day i + days[i] - 1). Each day you eat at most one apple, choosing the one expiring soonest to minimize waste. After n days, you may continue eating leftover apples. Maximize the total apples eaten.

Why is this asked in interviews?

Uber includes this problem to test priority queue (min-heap) usage with greedy scheduling. It combines the classic "earliest deadline first" (EDF) scheduling algorithm with the added complexity of continuing beyond the input period. Candidates who recognize this as an EDF problem and implement it with a min-heap demonstrate strong scheduling algorithm knowledge.

Algorithmic pattern used

Greedy with min-heap (priority queue): Use a min-heap keyed by expiry date. Each day:

1. Add the new batch (expiry_day, count) to the heap if count > 0.
2. Pop expired batches (expiry ≤ current day).
3. If heap is non-empty, eat one apple from the batch expiring soonest; decrement its count. If count reaches 0, remove it.

After day n, continue until the heap is empty, incrementing day each iteration and repeating the process. Total complexity: O(n log n).

Example explanation

apples = [1, 2, 3, 5, 2], days = [3, 1, 1, 4, 2]

• Day 0: Add (0+3-1=2, 1)=(expiry 2, count 1). Eat from it. Count=0. Eaten=1.
• Day 1: Add (1+1-1=1, 2)=(expiry 1, count 2). Heap: [(1,2)]. Eat from expiry-1 batch. Count=1. Eaten=2.
• Day 2: Add (2+1-1=2, 3). Heap: [(1,1),(2,3)]. Eat from expiry-1 (soonest). Count=0. Eaten=3.
• Day 3: Add (3+4-1=6, 5). Heap: [(2,3),(6,5)]. Eat from expiry-2. Count=2. Eaten=4.
• Day 4: Add (4+2-1=5, 2). Heap: [(2,2),(5,2),(6,5)]. Eat from expiry-2. Count=1. Eaten=5.
• Day 5 (post-input): Heap: [(2,1),(5,2),(6,5)]. Expiry-2 ≤ 5: remove. Eat from expiry-5. Eaten=6.
• Continue until heap empty...

Common mistakes candidates make

• Not continuing after day n: The problem explicitly states you continue eating after the input period ends. Many candidates stop at day n.
• Not removing expired batches: Popping from the heap without checking expiry leads to eating expired apples.
• Incrementing count instead of decrementing: When eating from a batch, decrement the count; when the count hits 0, don't eat from that batch anymore.

Interview preparation tip

For the Array Heap Priority Queue Greedy interview pattern, "earliest deadline first" is a foundational scheduling greedy. Whenever you see "choose the item expiring soonest to maximize total items used," reach for a min-heap keyed by expiry. Practice identifying EDF scenarios — they appear in scheduling, task assignment, and resource allocation problems at Uber, Google, and Amazon.