首页 > 试题广场 >

设作业j1，j2, ... j...

[问答题]
设作业j1，j2, ... jN为输入，其中的每一个作业都要花一个时间单位来完成。如果每个作业ji在时间限度ti内完成，那么将挣得di美元，但若在时间限度以后完成则挣不到钱。
a. 给出一个O（N2）贪婪算法求该问题。
b. 修改你的算法以得到O（NlogN）的时间界。提示：时间界完全归因于将作业按照金额排序。算法的其余部分可以使用不相交集数据结构以o（NlogN）实现。
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

上传者：小小
难度：
0条回答 459浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号