DeepSeek LeetCode 2589. 完成所有任务的最少时间 Go实现
以下是 LeetCode 2589 的 Go 语言实现,思路与 Java 版本完全一致:
核心代码
```go
func findMinimumTime(tasks [][]int) int {
// 按结束时间升序排序
sort.Slice(tasks, func(i, j int) bool {
return tasks[i][1] < tasks[j][1]
})
// 标记时间点是否被占用(题目时间范围 ≤ 2000)
used := make([]bool, 2001)
total := 0
for _, task := range tasks {
start, end, duration := task[0], task[1], task[2]
// 统计区间内已被占用的时间点数
alreadyUsed := 0
for i := start; i <= end; i++ {
if used[i] {
alreadyUsed++
}
}
// 还需要新占用的时间点
need := duration - alreadyUsed
if need <= 0 {
continue
}
// 从后往前分配未占用的时间点(贪心:尽量靠后)
for i := end; i >= start && need > 0; i-- {
if !used[i] {
used[i] = true
need--
total++
}
}
}
return total
}
```
完整可运行示例
```go
package main
import (
"fmt"
"sort"
)
func findMinimumTime(tasks [][]int) int {
sort.Slice(tasks, func(i, j int) bool {
return tasks[i][1] < tasks[j][1]
})
used := make([]bool, 2001)
total := 0
for _, task := range tasks {
start, end, duration := task[0], task[1], task[2]
alreadyUsed := 0
for i := start; i <= end; i++ {
if used[i] {
alreadyUsed++
}
}
need := duration - alreadyUsed
if need <= 0 {
continue
}
for i := end; i >= start && need > 0; i-- {
if !used[i] {
used[i] = true
need--
total++
}
}
}
return total
}
func main() {
// 测试用例1
tasks1 := [][]int{{2,3,1}, {4,5,1}, {1,5,2}}
fmt.Println(findMinimumTime(tasks1)) // 输出: 3
// 测试用例2
tasks2 := [][]int{{1,3,2}, {2,5,3}, {5,6,2}}
fmt.Println(findMinimumTime(tasks2)) // 输出: 4
}
```
Go 语言特点说明
1. 排序:使用 sort.Slice 配合匿名函数,Go 没有 Java 的 Comparator,这样更简洁
2. 数组/切片:make([]bool, 2001) 创建布尔切片,默认值为 false
3. 循环:Go 的 for 循环更统一,不需要括号
4. 多返回值:直接使用 start, end, duration := task[0], task[1], task[2] 解包
复杂度分析
· 时间复杂度:O(n × M),M ≤ 2000
· 空间复杂度:O(M)
优化版本(使用并查集)
如果时间范围很大,可以用并查集快速找到可用的最晚时间点:
```go
func findMinimumTimeOptimized(tasks [][]int) int {
sort.Slice(tasks, func(i, j int) bool {
return tasks[i][1] < tasks[j][1]
})
parent := make([]int, 2001)
for i := range parent {
parent[i] = i
}
var find func(x int) int
find = func(x int) int {
if parent[x] != x {
parent[x] = find(parent[x])
}
return parent[x]
}
total := 0
for _, task := range tasks {
start, end, duration := task[0], task[1], task[2]
// 从 end 往前找可用的时间点
for i := end; i >= start && duration > 0; {
p := find(i)
if p < start {
break
}
// 占用这个时间点
total++
duration--
// 并查集合并到前一个位置
parent[p] = find(p - 1)
i = p - 1
}
}
return total
}
```
并查集优化原理:每次占用一个时间点后,将其指向前一个可用位置,实现 O(α(n)) 的查找速度。
建议先掌握基础版本,理解贪心思想后再看优化版本。
更多推荐




所有评论(0)