算法设计:对任意给定的整数n和k以及完成任务i需要的时间为Ti,i=12,3……n计算完成这n个任务的朂佳调度。
如果各机器运行速度相等换句话就是任务无论在哪台机器上运行完成时间都相等,则问题较简单
1 . 先将任务由大到小排序
2 . 计算n個任务需要的总时间和平均到k个机器上的时间
3 . 将大于平均时间的任务各分配一个机器找到最大完成时间
4 . 将其他任务顺序安排在一台机器仩,如果时间超出最大时间则把该任务交给下一个机器,下一个任务继续在这台机器上试安排直到所有任务都不能在小于最大完成时間的情况下安排
5 . 安排下一台机器直道所有任务安排完,
6 . 或有可能安排某(些)任务找不到小于最大完成时间 那么重新扫描各台机器使再加上该任务后时间最小按此方法安排万所有任物
数据结构采用链表比较合适,
K个机器k个链n个任务按大小顺序插入一个链表,安排后从任务链表中移动到机器链表中知道链表为空
这个问题的算法是贪心算法,具体证明我就没写出来了。
我写的代码复杂度是n^2,有一个排序是nlogn,喝一個2重for循环.
但是2重for循环可以简化为for+最小堆的维护所以最好的复杂度是NlogN,
但是懒得写最小堆了...