You are given two integer arrays: apples and days, both of length n. On the i-th day, apples[i] apples grow, and each of these apples will rot and become inedible after days[i] days (i.e., on day i + days[i]). Each day, you can eat at most one apple. Your goal is to maximize the total number of apples you can eat before they rot.
Find and return the maximum number of apples you can eat.
Let's break down the problem. Each day, you get some apples, each with a specific expiration date. You want to eat as many apples as possible, but you can only eat one per day, and you can't eat rotten apples.
A brute-force approach would be to, for each day, try all possible apples and pick one that hasn't rotted yet. But this is inefficient, especially if there are many apples and days.
The key insight is that apples that will rot sooner should be prioritized. If you always eat the apple that will rot the soonest, you avoid waste. This leads to the idea of using a data structure that can always give you the apple with the earliest expiration date.
A min-heap (priority queue) is perfect for this, as it can efficiently keep track of the apple batches and their expiration dates, always allowing you to pick the batch that expires first.
We can solve this problem efficiently using a min-heap (priority queue). Here's a step-by-step breakdown:
(expiration day, number of apples) to the heap.
Why a min-heap? Because it always gives us the apple batch that will rot the soonest, ensuring we minimize waste.
Let's say apples = [1,2,3,5,2] and days = [3,2,1,4,2].
Total apples eaten: 7
import heapq
class Solution:
def eatenApples(self, apples, days):
import heapq
n = len(apples)
heap = []
res = 0
day = 0
while day < n or heap:
if day < n and apples[day] > 0:
# (expire day, count)
heapq.heappush(heap, (day + days[day], apples[day]))
# Remove rotten apples
while heap and heap[0][0] <= day:
heapq.heappop(heap)
if heap:
expire, count = heapq.heappop(heap)
res += 1
if count > 1:
heapq.heappush(heap, (expire, count - 1))
day += 1
return res
#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
int eatenApples(vector<int>& apples, vector<int>& days) {
typedef pair<int, int> pii;
priority_queue<pii, vector<pii>, greater<pii>> pq;
int n = apples.size(), res = 0, day = 0;
while (day < n || !pq.empty()) {
if (day < n && apples[day] > 0) {
pq.push({day + days[day], apples[day]});
}
while (!pq.empty() && pq.top().first <= day) pq.pop();
if (!pq.empty()) {
auto tmp = pq.top(); pq.pop();
res++;
if (tmp.second > 1)
pq.push({tmp.first, tmp.second - 1});
}
day++;
}
return res;
}
};
import java.util.PriorityQueue;
class Solution {
public int eatenApples(int[] apples, int[] days) {
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
int n = apples.length, res = 0, day = 0;
while (day < n || !pq.isEmpty()) {
if (day < n && apples[day] > 0) {
pq.offer(new int[]{day + days[day], apples[day]});
}
while (!pq.isEmpty() && pq.peek()[0] <= day) pq.poll();
if (!pq.isEmpty()) {
int[] curr = pq.poll();
res++;
if (curr[1] > 1) pq.offer(new int[]{curr[0], curr[1] - 1});
}
day++;
}
return res;
}
}
class MinHeap {
constructor() {
this.heap = [];
}
push(item) {
this.heap.push(item);
this._siftUp();
}
pop() {
if (this.heap.length === 1) return this.heap.pop();
const top = this.heap[0];
this.heap[0] = this.heap.pop();
this._siftDown();
return top;
}
peek() {
return this.heap[0];
}
_siftUp() {
let idx = this.heap.length - 1;
while (idx > 0) {
let parent = Math.floor((idx - 1) / 2);
if (this.heap[parent][0] <= this.heap[idx][0]) break;
[this.heap[parent], this.heap[idx]] = [this.heap[idx], this.heap[parent]];
idx = parent;
}
}
_siftDown() {
let idx = 0, n = this.heap.length;
while (2 * idx + 1 < n) {
let left = 2 * idx + 1, right = 2 * idx + 2, smallest = idx;
if (left < n && this.heap[left][0] < this.heap[smallest][0]) smallest = left;
if (right < n && this.heap[right][0] < this.heap[smallest][0]) smallest = right;
if (smallest === idx) break;
[this.heap[smallest], this.heap[idx]] = [this.heap[idx], this.heap[smallest]];
idx = smallest;
}
}
isEmpty() {
return this.heap.length === 0;
}
}
var eatenApples = function(apples, days) {
let heap = new MinHeap();
let n = apples.length, res = 0, day = 0;
while (day < n || !heap.isEmpty()) {
if (day < n && apples[day] > 0) {
heap.push([day + days[day], apples[day]]);
}
while (!heap.isEmpty() && heap.peek()[0] <= day) heap.pop();
if (!heap.isEmpty()) {
let [expire, count] = heap.pop();
res++;
if (count > 1) heap.push([expire, count - 1]);
}
day++;
}
return res;
};
Brute-force approach:
The heap ensures we always work efficiently, even for large inputs.
This problem is about maximizing the apples eaten before they rot, given daily growth and expiration. The core insight is to always eat the apple that will rot the soonest, which is efficiently managed using a min-heap. This ensures minimal waste and maximum consumption, with an efficient O(n log n) time solution. The approach is both practical and elegant, as it closely models real-world decision-making for perishable items.