Topic describes

This is 1705 on LeetCode. The maximum number of apples to eat is medium difficulty.

Tag: greedy, priority queue, heap

There is a special apple tree, n days in a row, can grow several apples each day.

On day I, the trees will grow apples[I], which will rot and become inedible after days[I] (i.e., the I + days[I]).

There may be days when apples[I] == 0 and days[I] == 0.

You plan to eat no more than one apple a day to ensure a balanced diet. Notice, you can continue to eat apples after these n days.

You are given two integer arrays of length N days and apples that return the maximum number of apples you can eat.

Example 1:

Input: apples = [1,2,3,5,2], days = [3,2,1,4,2] - The next day, you eat an apple that grew the next day. - On the third day, you eat an apple that grew the next day. After that day, the apples that came out on the third day were already rotten. - From day four to day seven, you eat apples that are four days old.Copy the code

Example 2:

Apples = [3,0,0,0, 2]; days = [3,0,0,0, 2]; 5 Explanation: You can eat five apples: - From day one to day three, you eat apples that are the first day long. - No apples on the fourth and fifth days. - On the sixth and seventh days, you eat apples that are six days old.Copy the code

Tip:


  • a p p l e s . l e n g t h = = n apples.length == n

  • d a y s . l e n g t h = = n days.length == n

  • 1 < = n < = 2 1 0 4 1 <= n <= 2 * 10^4

  • 0 < = a p p l e s [ i ] . d a y s [ i ] < = 2 1 0 4 0 <= apples[i], days[i] <= 2 * 10^4
  • Only in theapples[i] = 0When,days[i] = 0To set up

Greedy + Priority queue (heap)

This problem is a classic combination of priority queue (heap) greedy problem, and combination of sorting greedy problem, belongs to the most common greedy problem type.

Intuitively, we would think it would be best to “eat the apples that expire the fastest first,” and this process of maintaining apple expiration could be implemented using a “small root pile.”

The number of apples is large, but the maximum number of days for apple production is 2∗1042 * 10^42∗104, so we store them in a “small root pile” for maintenance as a binary (last use date, number of apples produced that day).

Specifically, we can simulate the following logic (let NNN be the array length, timetimetime be the current time, ansansans be the number of apples eaten) :

  • First, if “time

  • In the simulation of the day, if “time

    Where the binary group represents (last consumption date, number of apples produced on the day)(last consumption date, number of apples produced on the day)(last consumption date, number of apples produced on the day), and the situation of apples[time]=0apples[time] =0apples[time] =0 needs to be filtered.

  • Then try to remove the earliest ‘use-by’ apple cur from the heap and discard it if the top element has expired;

  • If, after eating a cur apple, there is still a surplus, and the last time is longer than the current time (has not expired), add cur back to the heap;

  • Repeat this logic until all the apples are in the heap.

Intuitions can be deceiving, so we used induction and reduction to prove the above conjecture

Assume that the sequence of apples obtained by the above eating method is (A1, A2… ,an)(a_1, a_2, … ,a_n)(a1,a2,… ,an), and the corresponding sequence of the real optimal solution is (B1, B2… ,bm)(b_1, b_2, … , b_m)(b1,b2,… , bm).

We aim to prove that n=mn =mn =m, that is, the number of apples eaten is consistent (greedy solution is one of the specific solutions of the optimal solution).

So let’s start by proving that the boundary is true, that b1 b1 can be a1a_1A1.

Since the apple with the earliest expiration time is always taken to eat in the greedy solution, the expiration time of A1A_1A1 is less than or equal to the expiration time of B1B_1B1. In this case, if b1b_1B1 in the optimal solution is replaced by A1A_1A1, the length of the whole sequence will not be affected.

First of all, the substitution operation must not make the optimal sequence longer, otherwise it violates the premise that the optimal solution is the longest legal sequence.

The focus is on whether this operation will shorten the optimal sequence length, which needs to be discussed in different cases:

  • A1a_1a1 does not exist in relation to (b2,b3… ,bm)(b_2, b_3, … , b_m)(b2,b3,… ,bm), at this time, directly replacing B1b_1B1 with A1A_1A1 will not naturally affect subsequent sequences, that is to say, after the substitution, the legitimacy of the optimal sequence is still guaranteed, and the length remains unchanged, and the result will not be worse;
  • A1a_1a1 for (b2, b3,… ,bm)(b_2, b_3, … , b_m)(b2,b3,… ,bm), suppose bi=a1b_i = a_1bi= A1, since BI /a1b_i/a_1bi/ A1 is the first out of the heap (with the earliest expiration time) in the greedy solution, Therefore, there must also be bi/ A1B_I/a_1BI/A1 that expires earlier than b1B_1B1, in which case it is still legal to put B1B_1B1 in bib_ibi (later than BI/A1B_I /a_1bi/ A1), In other words, b1b_1B1 and BI/a1b_I /a_1bi/ A1 switch positions, the optimal sequence law is still guaranteed, while the length remains unchanged, and the result will not be worse.

When the first position decision of the greedy solution is the same as that of the optimal solution (the apple eaten is the same), the conditions for the next position decision are exactly the same, and the structure relied on by inductive reasoning has not changed, the above analysis is also valid.

In other words, the above reasoning can be generalized to any position in the optimal solution sequence.

So far, we have proved that the optimal solution can be adjusted to our greedy sequence with the same length, that is, the greedy solution is one of the specific schemes of the optimal solution.

Code:

class Solution {
    public int eatenApples(int[] apples, int[] days) {
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[0]-b[0]);
        int n = apples.length, time = 0, ans = 0;
        while(time < n || ! q.isEmpty()) {if (time < n && apples[time] > 0) q.add(new int[]{time + days[time] - 1, apples[time]});
            while(! q.isEmpty() && q.peek()[0] < time) q.poll();
            if(! q.isEmpty()) {int[] cur = q.poll();
                if (--cur[1] > 0 && cur[0] > time) q.add(cur);
                ans++;
            }
            time++;
        }
        returnans; }}Copy the code
  • Time complexity: Let NNN be the length of the array, at most NNN group apples in/out of the heap. The complexity is O(nlog⁡n)O(n\log{n})O(nlogn)
  • Space complexity: O(n)O(n)O(n)

The last

This is the No.1705 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode as of the start date, some of which have locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.