LeetCode 每日一题 ---- 【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 的后缀）。

第三步
遍历排序后的任务，先统计区间内的已运行的电脑运行时间点，如果个数小于 duration，则需要新增时间点。根据提示 2，尽量把新增的时间点安排在区间 [start,end] 的后缀上，这样下一个区间就能统计到更多已运行的时间点。

class Solution {public int findMinimumTime(int[][] tasks) {// 按照右边界排序Arrays.sort(tasks, (a, b) -> a[1] - b[1]);int ans = 0;int mx = tasks[tasks.length - 1][1];boolean[] run = new boolean[mx + 1];for (int[] t : tasks) {int start = t[0];int end = t[1];int d = t[2];// 电脑开机运行的时间段for (int i = start; i <= end; i ++ ) {if (run[i]) {d -- ;}}// 没有运行完 补充时间for (int i = end; d > 0; i -- ) {if (!run[i]) {run[i] = true;d -- ;ans ++ ;}}   }return ans;}
}

时间复杂度：
O(nlogn + nU)
n 是 task 的长度，U 是max(end) 的大小

空间复杂度：
O(U)

这篇关于LeetCode 每日一题 ---- 【2589.完成所有任务的最少时间】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---