[leetcode 2589][Go][贪心]完成所有任务的最少时间

题目链接

leetcode 2589 完成所有任务的最少时间

解题思路

将tasks根据右端点排序，只考虑右端点的情况，那么就只有三种:

  • 没有交集
  • 后n个数组的前缀与当前数组的后缀重合
  • 与相邻的数组完全包含

对于这三种情况，只要尽量将时间点靠近右端点就能尽量重合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func findMinimumTime(tasks [][]int) int {
	var run = make([]bool, 2001)
    sort.Slice(tasks, func(i, j int) bool {
        return tasks[i][1] < tasks[j][1]
    })
	var ret = 0
	for i := range tasks {
		s, e, d := tasks[i][0], tasks[i][1], tasks[i][2]
		for j := s; j <= e; j++ {
			if run[j] {
				d--
			}
		}
		for j := e; j >= s && d > 0; j-- {
			if !run[j] {
				run[j] = true
				d--
				ret++
			}
		}
	}
	return ret
}

上述代码的时间复杂度为