Golang 程序实现加权间隔调度算法
加权间隔调度问题围绕一组间隔展开，每个间隔都有一个相关权重。在本文中，我们将使用两种方法在 Go 中实现加权间隔调度算法:递归和动态规划。这个经典的优化问题涉及选择具有最大总权重的非重叠间隔。
解释
递归方法
递归方法采用一种简单而优雅的方法。它逐一检查每个间隔并考虑两种情况 - 是否包括当前间隔或跳过它。此方法利用递归探索所有可能的间隔组合，计算最大权重。虽然概念清晰，但由于子问题重叠，它可能不是针对较大输入的最有效方法。
动态规划方法
动态规划方法是对递归方法的优化。它利用记忆化原理，存储先前计算的结果以避免冗余计算。此方法为各种间隔大小构建最大权重表，并利用这些预先计算的值来有效地计算解决方案。它比递归方法更有效，尤其是对于较大的数据集。
语法
func recursiveWeightedIntervalScheduling(intervals []Interval) int
语法将间隔切片作为输入并返回一个整数。它使用递归方法来查找非重叠间隔的最大总权重。该方法递归地探索所有可能的区间组合，并选择总权重最高的区间组合。但是，由于冗余计算，对于大量间隔，其效率可能会降低。
算法
根据间隔的完成时间按升序对间隔进行排序。
初始化一个动态规划表 DP，大小为 len(intervals)+1，其中 DP[i] 表示到第 i 个间隔为止不重叠间隔的最大总权重。
将 DP[0] 设置为 0，因为没有要考虑的间隔。
以间隔(从 1 开始)对每个间隔 i 进行迭代 −
使用二分搜索或线性搜索找到最后一个兼容间隔 j(其中 j 的完成时间小于或等于 i 的开始时间)。
计算包括当前间隔 i 以及 DP[j] 的总权重并将其分配给 DP[i]。
将 DP[i] 更新为 DP[i] 和 DP[i-1] 之间的最大值，以考虑排除当前间隔的可能性。
非重叠间隔的最大总权重将存储在 DP[len(intervals)] 中。
示例 1
在此示例中，我们有六个加权间隔，表示为开始时间、结束时间和相应权重的集合。目标是找到非重叠间隔的最大总权重，即选择一个间隔子集，使得没有两个间隔在时间上重叠，并且它们的权重总和最大化。 Go 中的递归加权区间调度算法通过递归探索所有可能的区间组合并选择总权重最高的区间组合，有效地解决了这个问题。
package main
import "fmt"
type Interval struct {
start, finish, weight int
}
func schedule(intervals []Interval, currentIndex, prevFinish int) int {
if currentIndex == len(intervals) {
return 0
}
if intervals[currentIndex].start < prevFinish {
return schedule(intervals, currentIndex+1, prevFinish)
}
includeCurrent := intervals[currentIndex].weight + schedule(intervals, currentIndex+1, intervals[currentIndex].finish)
skipCurrent := schedule(intervals, currentIndex+1, prevFinish)
return max(includeCurrent, skipCurrent)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
intervals := []Interval{
{1, 4, 3},
{3, 7, 5},
{0, 6, 8},
{5, 9, 2},
{8, 12, 6},
{10, 15, 4},
}
maxWeight := schedule(intervals, 0, 0)
fmt.Println("非重叠间隔的最大总重量:", maxWeight)
}
func sortByFinish(intervals []Interval) {
n := len(intervals)
for i := 0; i < n-1; i++ {
for j := 0; j < n-i-1; j++ {
if intervals[j].finish > intervals[j+1].finish {
intervals[j], intervals[j+1] = intervals[j+1], intervals[j]
}
}
}
}
输出
非重叠间隔的最大总重量: 14
示例 2
在此示例中，我们有六个加权区间:[1, 4, 3]、[3, 5, 2]、[0, 6, 4]、[5, 7, 1]、[8, 9, 3] 和 [5, 9, 5]。使用 Go 中的动态规划加权区间调度算法来查找非重叠区间的最大总权重。对于给定的输入区间，发现非重叠区间的最大总权重为 14。
package main
import (
"fmt"
"sort"
)
type Interval struct {
start, end, weight int
}
func latestNonOverlapping(intervals []Interval, i int) int {
for j := i - 1; j >= 0; j-- {
if intervals[j].end <= intervals[i].start {
return j
}
}
return -1
}
func findMaxWeight(intervals []Interval) int {
sort.Slice(intervals, func(i, j int) bool {
return intervals[i].end < intervals[j].end
})
n := len(intervals)
dp := make([]int, n)
dp[0] = intervals[0].weight
for i := 1; i < n; i++ {
nonOverlap := latestNonOverlapping(intervals, i)
if nonOverlap != -1 {
dp[i] = max(dp[i-1], dp[nonOverlap]+intervals[i].weight)
} else {
dp[i] = max(dp[i-1], intervals[i].weight)
}
}
return dp[n-1]
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func main() {
intervals := []Interval{
{1, 4, 3},
{3, 5, 2},
{0, 6, 4},
{5, 7, 1},
{8, 9, 3},
{5, 9, 5},
}
maxWeight := findMaxWeight(intervals)
fmt.Println("非重叠间隔的最大总重量:", maxWeight)
}
输出
非重叠间隔的最大总重量: 8
实际实施
项目管理
加权间隔调度可用于项目调度，其中任务具有不同的重要性和时间范围。通过选择具有最大综合重要性且没有重叠的任务序列，该算法可帮助项目经理优化任务执行以获得更好的项目成果。
会议室预订
在企业环境中，安排会议或研讨会等活动至关重要。加权间隔调度有助于有效地确定优先级和安排活动，确保重要活动得到安排，优化会议室的资源使用。
结论
在本文中，我们研究了使用两种方法的加权间隔调度算法:递归和动态规划。递归方法使用递归来探索所有可能的间隔组合，而动态规划方法存储中间结果以提高效率。
