题解 | #牛奶供应问题#

思路

本以为要用到动态规划，其实不用，en 贪不会有什么问题。

根据 贪心策略，对于当前任务 taskDurations[i]，肯定是把其安排在最早空闲的生产线上。

于是用 优先队列（大根堆） 维护每条生产线所执行时间，然后模拟即可。

时间复杂度为 ，空间复杂度为 。

参考代码

import java.util.*;


public class Solution {
    
    public int animalTaskScheduler (int[] taskDurations, int capacity) {
        PriorityQueue<Integer> q = new PriorityQueue<>(capacity);

        for (int i = 0; i < taskDurations.length; i++) {
            if (q.size() < capacity) {
                q.add(taskDurations[i]);
            } else {
                q.add(q.poll() + taskDurations[i]);
            }
        }

        int ans = 0;
        while (!q.isEmpty()) {
            ans = Math.max(ans, q.poll());
        }
        return ans;
    }
}