2025-07-21：不重叠区间的最大得分。用go语言，给定一个二维整数数组 intervals，其中每个元素 interval|interval|tuple|下标|字典|整数|算法

2025-07-21：不重叠区间的最大得分。用go语言，给定一个二维整数数组 intervals，其中每个元素 intervals[i] = [li, ri, weighti] 表示一个区间，起点是 li，终点是 ri，权重是 weighti。你最多可以选出 4 个互不重叠的区间，使得这些被选区间的权重总和最大。

这里的“互不重叠”指的是两个区间之间没有任何交集，且如果两个区间在边界点（左端点或右端点）重合，也视为重叠，不能同时选择。

最终需要返回一个数组，包含所选区间的下标，最多 4 个，并且在所有得分最高的组合中，选出字典序最小的那一个。

1 <= intervals.length <= 5 * 10000。

intervals[i].length == 3。

intervals[i] = [li, ri, weighti]。

1 <= li <= ri <= 1000000000。

1 <= weighti <= 1000000000。

输入： intervals = [[5,8,1],[6,7,7],[4,7,3],[9,10,6],[7,8,2],[11,14,3],[3,5,5]]。

输出： [1,3,5,6]。

解释：

可以选择下标为 1、3、5 和 6 的区间，其权重分别为 7、6、3 和 5。

题目来自力扣3414。

解决步骤

1.数据预处理：

• 将每个区间及其原始下标存储为一个元组（tuple），包含左端点（l）、右端点（r）、权重（weight）和原始下标（i）。
• 根据右端点对所有区间进行排序。这样做的目的是为了方便后续的动态规划处理，因为按右端点排序后，可以更容易地找到不与当前区间重叠的前驱区间。

2.动态规划初始化：

• 定义一个动态规划数组f，其中f[i][j]表示从前i个区间中选择最多j个不重叠区间时的最大权重和及其对应的区间下标组合。
•f是一个二维数组，大小为(n+1) x 5，其中n是区间的数量。5是因为最多可以选择 4 个区间（包括 0 个区间的情况）。

3.动态规划填充：

• 遍历排序后的区间，对于每个区间t，尝试将其加入到已有的选择中。
• 对于每个可能的区间数量j（从 1 到 4）：
- • 找到所有右端点小于当前区间t的左端点的区间。这些区间可以与t不重叠。这一步通过二分查找实现，找到第一个右端点大于等于t.l的区间，其左边的区间就是可能的前驱。
- • 计算两种情况的权重和：
- - • 不选择当前区间t：直接继承f[i][j]的值。
  - • 选择当前区间t：权重和为f[k][j-1].sum + t.weight，其中k是前驱区间的数量。
- • 比较这两种情况，选择权重和较大的那个。如果权重和相同，选择字典序较小的下标组合。
- • 更新f[i+1][j]为当前最优解。

4.结果提取：

• 最终的最大权重和及其对应的区间下标组合存储在f[n][4]中。
• 返回f[n][4].id，即所选区间的下标。

时间复杂度

• 排序区间：O(n log n)。
• 动态规划填充：
- • 外层循环遍历n个区间。
- • 内层循环遍历 4 个可能的区间数量。
- • 对于每个区间和数量，需要进行一次二分查找（O(log n)）。
- • 因此，动态规划部分的时间复杂度为O(n * 4 * log n) = O(n log n)。
• 总时间复杂度：O(n log n)。

空间复杂度

• 存储排序后的区间：O(n)。
• 动态规划数组f：O(n * 5) = O(n)。
• 存储每个状态的区间下标组合：最坏情况下可能需要O(n * 4)的空间（每个状态存储最多 4 个下标）。
• 总空间复杂度：O(n)。

总结

• 时间复杂度：O(n log n)。
• 空间复杂度：O(n)。

Go完整代码如下：

package main import (     "fmt"     "slices"     "sort" ) func maximumWeight(intervals [][]int) []int {     type tuple struct{ l, r, weight, i int }     a := make([]tuple, len(intervals))     for i, interval := range intervals {         a[i] = tuple{interval[0], interval[1], interval[2], i}     }     slices.SortFunc(a, func(a, b tuple)int { return a.r - b.r })     n := len(intervals)     type pair struct {         sum int         id  []int     }     f := make([][5]pair, n+1)     for i, t := range a {         k := sort.Search(i, func(k int)bool { return a[k].r >= t.l })         for j := 1; j < 5; j++ {             s1 := f[i][j].sum             // 为什么是 f[k] 不是 f[k+1]：上面算的是 >= t.l，-1 后得到 < t.l，但由于还要 +1，抵消了             s2 := f[k][j-1].sum + t.weight             if s1 > s2 {                 f[i+1][j] = f[i][j]                 continue             }             newId := slices.Clone(f[k][j-1].id)             newId = append(newId, t.i)             slices.Sort(newId)             if s1 == s2 && slices.Compare(f[i][j].id, newId) < 0 {                 newId = f[i][j].id             }             f[i+1][j] = pair{s2, newId}         }     }     return f[n][4].id } func main() {     intervals := [][]int{{5, 8, 1}, {6, 7, 7}, {4, 7, 3}, {9, 10, 6}, {7, 8, 2}, {11, 14, 3}, {3, 5, 5}}     result := maximumWeight(intervals)     fmt.Println(result) }

Python完整代码如下：

# -*-coding:utf-8-*- from bisect import bisect_left from copyimport deepcopy def maximumWeight(intervals):     # 定义元组结构 l, r, weight, 原始下标 i     a = [(l, r, w, i) for i, (l, r, w) in enumerate(intervals)]     # 按右端点排序     a.sort(key=lambda x: x[1])          n = len(intervals)     # f[i][j] 存储选前 i 个区间，选 j 个区间时的最大权重和及对应的id列表     # 初始化为 sum=0，id=[]     f = [[{'sum':0, 'id':[]} for _ in range(5)] for _ in range(n+1)]     # 右端点单独提取，方便二分查找     ends = [item[1] for item in a]     for i, (l, r, w, idx) in enumerate(a):         # 找到第一个右端点 >= l 的区间位置         k = bisect_left(ends, l)         for j in range(1,5):             s1 = f[i][j]['sum']  # 不选第 i 个区间             # 选第 i 个区间，更新权重和             # f[k][j-1] 是不与当前区间重叠的组合             s2 = f[k][j-1]['sum'] + w             if s1 > s2:                 f[i+1][j] = f[i][j]             elif s1 < s2:                 new_id = deepcopy(f[k][j-1]['id'])                 new_id.append(idx)                 new_id.sort()                 f[i+1][j] = {'sum': s2, 'id': new_id}             else:  # s1 == s2，比较字典序，选字典序更小的                 new_id = deepcopy(f[k][j-1]['id'])                 new_id.append(idx)                 new_id.sort()                 if f[i][j]['id'] and f[i][j]['id'] < new_id:                     f[i+1][j] = f[i][j]                 else:                     f[i+1][j] = {'sum': s2, 'id': new_id}         # j=0 情况继承不变         f[i+1][0] = f[i][0]     return f[n][4]['id'] if __name__ == '__main__':     intervals = [[5, 8, 1], [6, 7, 7], [4, 7, 3], [9, 10, 6], [7, 8, 2], [11, 14, 3], [3, 5, 5]]     result = maximumWeight(intervals)     print(result)