LeetCode Daily Problem ---- Minimum Time to Complete All Tasks (Problem 2589).
发布时间
阅读量:
阅读量
LeetCode 每日一题 ---- 【2589.完成所有任务的最少时间】
- 2589.达成所有任务所需最短时间
-
- 途径:采用贪心算法结合暴力求解
-
任务完成时间最小化策略
贪心算法与暴力方法结合
该问题存在多种求解方式,鉴于数据规模相对较小,此处仅采用最为简洁的贪心+暴力方法进行处理,其余可选方案包括线段树以及栈结合二分法等。
第一步
按照区间的右端点由小到大的顺序对所有区间进行排序。
第二步
完成排序后,针对 tasks[i] 这一区间而言,其右侧的区间要么与之无任何重叠部分,要么在重叠区域中包含该区间的部分后缀内容。
以排序后的区间 [1,5],[3,7],[6,8] 为例,对于 [1,5] 而言,其右侧的区间可能与之无交集,如 [6,8];也可能存在交集,并且该交集恰好为 [1,5] 的后缀部分。例如 [1,5] 与 [3,7] 的交集为 [3,5],这一部分正是 [1,5] 的后缀(即 3、4、5 这三个元素构成了 1、2、3、4、5 的后半段)。
第三步
依次遍历已排序的所有任务区间,在此过程中记录每个区间内已经运行过的电脑时间点。若当前记录的时间点数量少于所需持续时间,则需要增加新的时间点。根据提示内容可知,在新增时间点时应优先选择安排在当前区间的后缀位置上,这样有助于后
全部评论 (0)
还没有任何评论哟~
