以下是 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)) 的查找速度。

建议先掌握基础版本,理解贪心思想后再看优化版本。

 

Logo

欢迎加入DeepSeek 技术社区。在这里,你可以找到志同道合的朋友,共同探索AI技术的奥秘。

更多推荐