题解 | #牛奶供应问题#

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param taskDurations int整型vector
     * @param capacity int整型
     * @return int整型
     */
    int animalTaskScheduler(vector<int>& taskDurations, int capacity) {
        // 定义小根堆pq和任务数n，初始化最大值ret为-1
        priority_queue<int, vector<int>, greater<int>> pq;
        int n = taskDurations.size(), ret = -1;

        // 将前capacity个任务放入小根堆中
        for (int i = 0; i < capacity; i++) {
            pq.push(taskDurations[i]);
        }

        // 从第capacity个任务开始，依次放入小根堆。如果小根堆当前的最小值tmp小于等于当前任务，说明当前任务可以立即执行，否则需要等待tmp时间才能执行
        for (int i = capacity; i < n; i++) {
            int tmp = pq.top();
            pq.pop();
            pq.push(tmp + taskDurations[i]);
        }

        // 遍历小根堆找到最长的等待时间，即为答案
        while (!pq.empty()) {
            ret = max(pq.top(), ret);
            pq.pop();
        }

        return ret;
    }
};

题意表达不清楚。

具体含义就是现在有capacity这么多个工位，每个人工作需要一定的时间，但你必须要按照给定顺序分配工作，那这样思路就很清晰了，开始即前capacity个人开始工作，当有空位时，我们应该立刻安排人来工作，不然就会浪费位置了。那么我们只能将下一个人分配到这个空位上，注意我们不能调整后续人的顺序，所以这样就是最优解了。

具体做法：每次找到工位上工作时间最短的那个工位上，把下一个人安排到这里，依次进行，之后取所有工位中时间最长的那个时间。可以用一个小根堆来解决。