Maximum number of eaten apples

Array Greedy Heap (Priority Queue)

42.8% acceptance

Feb 25, 2026

883

200

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::collections::BinaryHeap;
use std::cmp::Reverse;

impl Solution {
  pub fn eaten_apples(apples: Vec<i32>, days: Vec<i32>) -> i32 {
    let n = apples.len();
    let mut heap: BinaryHeap<Reverse<(i32, i32)>> = BinaryHeap::new();
    let mut result = 0;
    let mut day = 0usize;
    while day < n || !heap.is_empty() {
      if day < n && apples[day] > 0 {
        heap.push(Reverse((day as i32 + days[day], apples[day])));
      }
      while let Some(&Reverse((exp, _))) = heap.peek() {
        if exp <= day as i32 { heap.pop(); } else { break; }
      }
      if let Some(Reverse((exp, cnt))) = heap.pop() {
        result += 1;
        if cnt > 1 { heap.push(Reverse((exp, cnt - 1))); }
      }
      day += 1;
    }
    result
  }
}