1705 Maximum Number of Eaten Apples

이 문제는 먼저 썩는 사과 먼저 먹어야 하는 전형적인 우선순위 큐 문제이다.

C++

class Solution {
public:
    int eatenApples(vector<int>& apples, vector<int>& days) {
        using mypair = pair<int, int>;
        priority_queue<mypair, vector<mypair>, greater<mypair>> pq;
        int cnt{};
        size_t i;
        for(i = 0; i < apples.size() || !pq.empty(); ++i){
            while(!pq.empty() && pq.top().first <= i)
                pq.pop();
            if (i < apples.size() && apples[i]!=0)
                pq.push({days[i] + i, apples[i]});
            if (!pq.empty()){
                mypair top = pq.top();
                pq.pop();
                if (i < apples.size()){
                    top.second -= 1;
                    ++cnt;
                    if (top.second>0)
                        pq.push(top);
                }
                else{
                    int offset = min(top.first - int(i), top.second);
                    cnt += offset;
                    i += offset - 1;
                }
            }
        }
        return cnt;
    }
};

Python

class Solution:
    def eatenApples(self, apples: List[int], days: List[int]) -> int:
        from queue import PriorityQueue
        pq = PriorityQueue()
        cnt = 0
        i = 0
        while i < len(apples) or not pq.empty():
            while not pq.empty() and pq.queue[0][0] <= i:
                pq.get()
            if i < len(apples) and apples[i] != 0:
                pq.put((days[i] + i, apples[i]))
            if not pq.empty():
                top = list(pq.queue[0])
                pq.get()
                if (i < len(apples)):
                    top[1] -= 1
                    cnt = cnt + 1
                    if top[1] > 0:
                        pq.put(tuple(top))
                else:
                    offset = min(top[0] - i, top[1])
                    cnt += offset
                    i += offset - 1
            i = i + 1
        return cnt