Skip to content

1705. Maximum Number of Eaten Apples 👍

  • Time: $O(n\log n)$
  • Space: $O(n)$
 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
class Solution {
 public:
  int eatenApples(vector<int>& apples, vector<int>& days) {
    const int n = apples.size();
    int ans = 0;
    using P = pair<int, int>;  // (the rotten day, the number of apples)
    priority_queue<P, vector<P>, greater<>> minHeap;

    for (int i = 0; i < n || !minHeap.empty(); ++i) {  // i := day
      // Remove the rotten apples.
      while (!minHeap.empty() && minHeap.top().first <= i)
        minHeap.pop();
      // Add today's apples.
      if (i < n && apples[i] > 0)
        minHeap.emplace(i + days[i], apples[i]);
      // Eat one apple today.
      if (!minHeap.empty()) {
        const auto [rottenDay, numApples] = minHeap.top();
        minHeap.pop();
        if (numApples > 1)
          minHeap.emplace(rottenDay, numApples - 1);
        ++ans;
      }
    }

    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
class Solution {
  public int eatenApples(int[] apples, int[] days) {
    final int n = apples.length;
    int ans = 0;
    // (the rotten day, the number of apples)
    Queue<Pair<Integer, Integer>> minHeap =
        new PriorityQueue<>((a, b) -> a.getKey().compareTo(b.getKey()));

    for (int i = 0; i < n || !minHeap.isEmpty(); ++i) {
      // Remove the rotten apples.
      while (!minHeap.isEmpty() && minHeap.peek().getKey() <= i)
        minHeap.poll();
      // Add today's apples.
      if (i < n && apples[i] > 0)
        minHeap.offer(new Pair<>(i + days[i], apples[i]));
      // Eat one apple today.
      if (!minHeap.isEmpty()) {
        final int rottenDay = minHeap.peek().getKey();
        final int numApples = minHeap.poll().getValue();
        if (numApples > 1)
          minHeap.offer(new Pair<>(rottenDay, numApples - 1));
        ++ans;
      }
    }

    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
class Solution:
  def eatenApples(self, apples: list[int], days: list[int]) -> int:
    n = len(apples)
    ans = 0
    minHeap = []  # (the rotten day, the number of apples)

    i = 0
    while i < n or minHeap:
      # Remove the rotten apples.
      while minHeap and minHeap[0][0] <= i:
        heapq.heappop(minHeap)
      # Add today's apples.
      if i < n and apples[i] > 0:
        heapq.heappush(minHeap, (i + days[i], apples[i]))
      # Eat one apple today.
      if minHeap:
        rottenDay, numApples = heapq.heappop(minHeap)
        if numApples > 1:
          heapq.heappush(minHeap, (rottenDay, numApples - 1))
        ans += 1
      i += 1

    return ans