Question

1705. Maximum Number of Eaten Apples

中文文档

Description

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:

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

Solutions

Solution 1: Greedy + Priority Queue

We can greedily choose the apple that is most likely to rot among the unrotten apples, so that we can eat as many apples as possible.

Therefore, we can use a priority queue (min heap) to store the rotting time of the apples and the corresponding number of apples. Each time we take out the apple with the smallest rotting time from the priority queue, then reduce its quantity by one. If the quantity of the apple is not zero after reduction, we put it back into the priority queue. If the apple has rotted, we pop it out from the priority queue.

The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array apples or days.

class Solution:
  def eatenApples(self, apples: List[int], days: List[int]) -> int:
    n = len(days)
    i = ans = 0
    q = []
    while i < n or q:
      if i < n and apples[i]:
        heappush(q, (i + days[i] - 1, apples[i]))
      while q and q[0][0] < i:
        heappop(q)
      if q:
        t, v = heappop(q)
        v -= 1
        ans += 1
        if v and t > i:
          heappush(q, (t, v))
      i += 1
    return ans

class Solution {
  public int eatenApples(int[] apples, int[] days) {
    PriorityQueue<int[]> q = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    int n = days.length;
    int ans = 0, i = 0;
    while (i < n || !q.isEmpty()) {
      if (i < n && apples[i] > 0) {
        q.offer(new int[] {i + days[i] - 1, apples[i]});
      }
      while (!q.isEmpty() && q.peek()[0] < i) {
        q.poll();
      }
      if (!q.isEmpty()) {
        var p = q.poll();
        ++ans;
        if (--p[1] > 0 && p[0] > i) {
          q.offer(p);
        }
      }
      ++i;
    }
    return ans;
  }
}

using pii = pair<int, int>;

class Solution {
public:
  int eatenApples(vector<int>& apples, vector<int>& days) {
    priority_queue<pii, vector<pii>, greater<pii>> q;
    int n = days.size();
    int ans = 0, i = 0;
    while (i < n || !q.empty()) {
      if (i < n && apples[i]) q.emplace(i + days[i] - 1, apples[i]);
      while (!q.empty() && q.top().first < i) q.pop();
      if (!q.empty()) {
        auto [t, v] = q.top();
        q.pop();
        --v;
        ++ans;
        if (v && t > i) q.emplace(t, v);
      }
      ++i;
    }
    return ans;
  }
};

func eatenApples(apples []int, days []int) int {
  var h hp
  ans, n := 0, len(apples)
  for i := 0; i < n || len(h) > 0; i++ {
    if i < n && apples[i] > 0 {
      heap.Push(&h, pair{i + days[i] - 1, apples[i]})
    }
    for len(h) > 0 && h[0].first < i {
      heap.Pop(&h)
    }
    if len(h) > 0 {
      h[0].second--
      if h[0].first == i || h[0].second == 0 {
        heap.Pop(&h)
      }
      ans++
    }
  }
  return ans
}

type pair struct {
  first  int
  second int
}

type hp []pair

func (a hp) Len() int       { return len(a) }
func (a hp) Swap(i, j int)    { a[i], a[j] = a[j], a[i] }
func (a hp) Less(i, j int) bool { return a[i].first < a[j].first }
func (a *hp) Push(x any)    { *a = append(*a, x.(pair)) }
func (a *hp) Pop() any      { l := len(*a); t := (*a)[l-1]; *a = (*a)[:l-1]; return t }