Description Link to heading

1705.maximum-number-of-eaten-apples

Solution Link to heading

The optimal strategy is to eat the apple that rots first, we can use the priority queue to simulate the process.

app_decay[i][0] indicates the expected decay time of the apples born on day i, and app_decay[i][1] indicates how many apples were born on day i.

The top() of the priority queue pq must be a vector with the minimum vec[0].

We traverse the array by time, if there are apples born on this day, we push app_decay[i] to pq, and pop the elements of the top() of pq until the heap is empty or pq.top()[0] > i, then pq.top()[1]--.

Code Link to heading 

class Solution {
  public:
    int eatenApples(vector<int> &apples, vector<int> &days) {
        vector<vector<int>> app_decay(apples.size(), vector<int>(2, 0));
        for (int i = 0; i < apples.size(); i++) {
            app_decay[i][0] = i + days[i];
            app_decay[i][1] = apples[i];
        }
        priority_queue<vector<int>> q;
        auto cmp = [&](vector<int> &v1, vector<int> &v2) {
            return v1[0] >= v2[0];
        };
        priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> pq(cmp);
        int res = 0;
        for (int i = 0; i < apples.size(); i++) {
            if (app_decay[i][1] != 0) {
                pq.push(app_decay[i]);
            }
            vector<int> vec;
            while (!pq.empty() && pq.top()[0] <= i) {
                pq.pop();
            }
            if (!pq.empty()) {
                vec = pq.top();
                pq.pop();
            }
            if (!vec.empty() && vec[0] > i) {
                vec[1]--;
                if (vec[1] != 0) {
                    pq.push(vec);
                }
                res++;
            }
        }
        int date = apples.size();
        while (!pq.empty()) {
            vector<int> vec1;
            while (!pq.empty() && pq.top()[0] <= date) {
                pq.pop();
            }
            if (!pq.empty()) {
                vec1 = pq.top();
                pq.pop();
            }
            if (!vec1.empty() && vec1[0] > date) {
                vec1[1]--;
                if (vec1[1] != 0)
                    pq.push(vec1);
                res++;
            }
            date++;
        }
        return res;
    }
};