题解 | #牛奶供应问题#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param taskDurations int整型一维数组 
     * @param capacity int整型 
     * @return int整型
     */
    public int animalTaskScheduler (int[] taskDurations, int capacity) {
        // write code here
        Queue<Integer> queue=new PriorityQueue<>();
        for(int i=0; i<taskDurations.length; i++){
            if(queue.size()<capacity){
                queue.add(taskDurations[i]);
            } else {
                int t=queue.poll();
                t+=taskDurations[i];
                queue.add(t);
            }
        }
        int res=0;
        while(!queue.isEmpty()){
            res=queue.poll();
        }
        return res;
    }
}

链接：https://www.nowcoder.com/questionTerminal/8c66c9b7deea496193e609b70f39783d?commentTags=Java链接：https://www.nowcoder.com/questionTerminal/8c66c9b7deea496193e609b70f39783d?commentTags=Java

来源：牛客网

第一次遇到这种题型，一开始我以为要用到排序，但是按照题目的示例一，不能对给定的任务排序，只能按照任务给定的顺序去调度。如果经过排序，可以找到更短的调度时间。

使用模拟和贪心的方法找到最短的调度时间。

遍历所有任务，用优先队列保存调度的时间，然后在队列的容量不超过capacity时，把当前的任务加到优先队列中，当优先队列的容量超过capacity时，就把队列中用时最短的一个任务找出来，用 t 保存这个最短的任务，然后 t = t + taskDurations[i] 保存当前任务和新任务的时间，可以理解为从当前的优先队列里面拿出一个用时最短的任务，这个任务做完了还有多余的时间来做其他的任务，所以需要从taskDurations里面取一个任务跟在当前 t 任务的后面，并且加到优先队列中，遍历完taskDurations，遍历优先队列，找到用时最长的任务即为结果。