牛奶供应问题

[编程题]牛奶供应问题

热度指数：560 时间限制：C/C++ 5秒，其他语言10秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛是一只聪明的牛，它是一个任务调度专家。在一个动物园中，有许多动物需要执行不同的任务。牛牛需要设计一个任务调度系统来管理动物的任务执行顺序。

每个动物的任务执行时间不同，并且每个动物只能执行一次任务。牛牛希望通过合理的任务调度，使得完成所有任务的总时间最小。

请你编写一个函数animalTaskScheduler，接收一个整数数组taskDurations和一个整数capacity作为参数，表示动物的任务执行时间和可以同时执行任务的容量。函数应返回一个整数，表示完成所有任务的最短时间。

示例1

输入

[3, 2, 4, 1, 5],3

输出

示例2

输入

[1, 2, 3, 4, 5],2

输出

备注:

taskDurations：一个整数数组，表示每个动物任务的执行时间。数组长度为n，满足1 ≤ n ≤ 1000。数组元素满足1 ≤ taskDurations[i] ≤ 1000。
capacity：一个整数，表示循环队列的容量。满足1 ≤ capacity ≤ 1000。

算法知识视频讲解

Java

牛客825478369号

题目描述不清。有capacity个worker，任务只能按taskDurations的顺序分配给某一个worker执行，每个worker某一时间只能执行一个任务，求完成任务的最小时间

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param taskDurations int整型一维数组 
     * @param capacity int整型 
     * @return int整型
     */
    public int animalTaskScheduler (int[] taskDurations, int capacity) {
        // write code here
        int[] time = new int[capacity];
        PriorityQueue<Integer> queue = new PriorityQueue<>((a,b) -> time[a] - time[b]);
        for (int i = 0; i < capacity; i++) {
            queue.add(i);
        }
        int max= 0;
        for (int taskDuration : taskDurations) {
            int i = queue.poll();
            time[i] += taskDuration;
            max = Math.max(max, time[i]);
            queue.add(i);
        }
        return max;
    }
}

发表于 2023-09-21 10:11:25 回复(0)

Java

boboKing_

import java.util.*;


public class Solution {
    public int animalTaskScheduler (int[] taskDurations, int capacity) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>();
        for(int i=0;i<taskDurations.length;i++){
            if(priorityQueue.size()<capacity){
                priorityQueue.add(taskDurations[i]);
            }
            else{
                int temp=priorityQueue.poll();
                priorityQueue.add(temp+taskDurations[i]);
            }
        }
        int result=0;
        while(priorityQueue.size()>0){
            result=priorityQueue.poll();
        }
        return result;

    }
}

发表于 2023-08-24 10:08:55 回复(0)

Java

陶良策

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

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

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

代码如下

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;
    }
}

编辑于 2023-08-14 15:16:43 回复(0)

提交观点

问题信息

难度：

3条回答 13收藏 682浏览

牛奶供应问题

输入

输出

输入

输出

备注:

问题信息

热门推荐

相关试题