1705. Maximum Number of Eaten Apples
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.
Example 1:
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:
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:
apples.length == n
days.length == n
1 <= n <= 2 * 104
0 <= apples[i], days[i] <= 2 * 104
days[i] = 0
if and only ifapples[i] = 0
.
Rust Solution
struct Solution;
use std::cmp::Reverse;
use std::collections::BinaryHeap;
impl Solution {
fn eaten_apples(apples: Vec<i32>, days: Vec<i32>) -> i32 {
let n = apples.len();
let mut queue: BinaryHeap<Reverse<(usize, i32)>> = BinaryHeap::new();
let mut i = 0;
let mut res = 0;
loop {
if i < n {
queue.push(Reverse((i + days[i] as usize, apples[i])));
}
if i >= n && queue.is_empty() {
break;
}
while let Some(Reverse((j, left))) = queue.peek() {
if i >= *j || *left == 0 {
queue.pop();
} else {
break;
}
}
if let Some(mut top) = queue.peek_mut() {
(top.0).1 -= 1;
res += 1;
}
i += 1;
}
res
}
}
#[test]
fn test() {
let apples = vec![1, 2, 3, 5, 2];
let days = vec![3, 2, 1, 4, 2];
let res = 7;
assert_eq!(Solution::eaten_apples(apples, days), res);
let apples = vec![3, 0, 0, 0, 0, 2];
let days = vec![3, 0, 0, 0, 0, 2];
let res = 5;
assert_eq!(Solution::eaten_apples(apples, days), res);
}
Having problems with this solution? Click here to submit an issue on github.