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

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)
}

# -*-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)