Problem

There is a special kind of apple tree that grows apples every day for n days. On the ith day, the tree grows apples[i] apples that will rot after days[i] days, that is on day i + days[i] the apples will be rotten and cannot be eaten. On some days, the apple tree does not grow any apples, which are denoted by apples[i] == 0 and days[i] == 0.

You decided to eat at most one apple a day (to keep the doctors away). Note that you can keep eating after the first n days.

Given two integer arrays days and apples of length n, return the maximum number of apples you can eat.

Examples

Example 1

1
2
3
4
5
6
7

Input: apples = [1,2,3,5,2], days = [3,2,1,4,2]
Output: 7
Explanation: You can eat 7 apples:
- On the first day, you eat an apple that grew on the first day.
- On the second day, you eat an apple that grew on the second day.
- On the third day, you eat an apple that grew on the second day. After this day, the apples that grew on the third day rot.
- On the fourth to the seventh days, you eat apples that grew on the fourth day.

Example 2

1
2
3
4
5
6

Input: apples = [3,0,0,0,0,2], days = [3,0,0,0,0,2]
Output: 5
Explanation: You can eat 5 apples:
- On the first to the third day you eat apples that grew on the first day.
- Do nothing on the fouth and fifth days.
- On the sixth and seventh days you eat apples that grew on the sixth day.

Constraints

  • n == apples.length == days.length
  • 1 <= n <= 2 * 10^4
  • 0 <= apples[i], days[i] <= 2 * 10^4
  • days[i] = 0 if and only if apples[i] = 0.

Solution

Method 1 – Greedy + Min Heap

Intuition

To maximize the number of apples eaten, always eat the apple that will rot the soonest. Use a min-heap to keep track of apple batches by their expiration day, and eat one apple per day from the batch that expires first.

Approach

  1. For each day, if apples grow, add a batch (expire_day, count) to the min-heap.
  2. Remove any batches from the heap that have expired or have no apples left.
  3. If the heap is not empty, eat one apple from the batch with the earliest expiration.
  4. Continue this process until all apples are processed and the heap is empty.
  5. Count the total apples eaten.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int eatenApples(vector<int>& apples, vector<int>& days) {
        int n = apples.size(), ans = 0, i = 0;
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
        while (i < n || !pq.empty()) {
            if (i < n && apples[i] > 0) {
                pq.emplace(i + days[i], apples[i]);
            }
            while (!pq.empty() && (pq.top().first <= i || pq.top().second == 0)) pq.pop();
            if (!pq.empty()) {
                auto p = pq.top(); pq.pop();
                ans++;
                if (--p.second > 0) pq.push(p);
            }
            i++;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

import "container/heap"
type apple struct{expire, count int}
type minHeap []apple
func (h minHeap) Len() int { return len(h) }
func (h minHeap) Less(i, j int) bool { return h[i].expire < h[j].expire }
func (h minHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x interface{}) { *h = append(*h, x.(apple)) }
func (h *minHeap) Pop() interface{} { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
func eatenApples(apples, days []int) int {
    n, ans, i := len(apples), 0, 0
    h := &minHeap{}
    heap.Init(h)
    for i < n || h.Len() > 0 {
        if i < n && apples[i] > 0 {
            heap.Push(h, apple{i + days[i], apples[i]})
        }
        for h.Len() > 0 && ((*h)[0].expire <= i || (*h)[0].count == 0) {
            heap.Pop(h)
        }
        if h.Len() > 0 {
            (*h)[0].count--
            ans++
            if (*h)[0].count == 0 {
                heap.Pop(h)
            }
        }
        i++
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

import java.util.*;
class Solution {
    public int eatenApples(int[] apples, int[] days) {
        int n = apples.length, ans = 0, i = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        while (i < n || !pq.isEmpty()) {
            if (i < n && apples[i] > 0) {
                pq.offer(new int[]{i + days[i], apples[i]});
            }
            while (!pq.isEmpty() && (pq.peek()[0] <= i || pq.peek()[1] == 0)) pq.poll();
            if (!pq.isEmpty()) {
                int[] p = pq.poll();
                ans++;
                if (--p[1] > 0) pq.offer(p);
            }
            i++;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

import java.util.PriorityQueue
class Solution {
    fun eatenApples(apples: IntArray, days: IntArray): Int {
        val n = apples.size
        var ans = 0
        var i = 0
        val pq = PriorityQueue(compareBy<Pair<Int, Int>> { it.first })
        while (i < n || pq.isNotEmpty()) {
            if (i < n && apples[i] > 0) {
                pq.add(Pair(i + days[i], apples[i]))
            }
            while (pq.isNotEmpty() && (pq.peek().first <= i || pq.peek().second == 0)) pq.poll()
            if (pq.isNotEmpty()) {
                val p = pq.poll()
                ans++
                if (p.second - 1 > 0) pq.add(Pair(p.first, p.second - 1))
            }
            i++
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

import heapq
class Solution:
    def eatenApples(self, apples: list[int], days: list[int]) -> int:
        n, ans, i = len(apples), 0, 0
        heap = []
        while i < n or heap:
            if i < n and apples[i] > 0:
                heapq.heappush(heap, (i + days[i], apples[i]))
            while heap and (heap[0][0] <= i or heap[0][1] == 0):
                heapq.heappop(heap)
            if heap:
                expire, count = heapq.heappop(heap)
                ans += 1
                if count - 1 > 0:
                    heapq.heappush(heap, (expire, count - 1))
            i += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

use std::collections::BinaryHeap;
use std::cmp::Reverse;
impl Solution {
    pub fn eaten_apples(apples: Vec<i32>, days: Vec<i32>) -> i32 {
        use std::collections::BinaryHeap;
        let n = apples.len();
        let mut ans = 0;
        let mut i = 0;
        let mut heap = BinaryHeap::new();
        while i < n || !heap.is_empty() {
            if i < n && apples[i] > 0 {
                heap.push(Reverse((i as i32 + days[i], apples[i])));
            }
            while let Some(&Reverse((expire, count))) = heap.peek() {
                if expire <= i as i32 || count == 0 {
                    heap.pop();
                } else {
                    break;
                }
            }
            if let Some(Reverse((expire, mut count))) = heap.pop() {
                ans += 1;
                count -= 1;
                if count > 0 {
                    heap.push(Reverse((expire, count)));
                }
            }
            i += 1;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    eatenApples(apples: number[], days: number[]): number {
        const n = apples.length;
        let ans = 0, i = 0;
        const heap: [number, number][] = [];
        const push = (item: [number, number]) => {
            heap.push(item);
            heap.sort((a, b) => a[0] - b[0]);
        };
        while (i < n || heap.length) {
            if (i < n && apples[i] > 0) push([i + days[i], apples[i]]);
            while (heap.length && (heap[0][0] <= i || heap[0][1] === 0)) heap.shift();
            if (heap.length) {
                let [expire, count] = heap.shift()!;
                ans++;
                if (count - 1 > 0) push([expire, count - 1]);
            }
            i++;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), where n is the number of days, due to heap operations for each day.
  • 🧺 Space complexity: O(n), for the heap storing apple batches.