golang 解法, 执行用时: 220 ms, 内存消耗: 23.9 MB, 提交时间: 2023-09-28 23:26:42

func maxValue(events [][]int, k int) int {
	sort.Slice(events, func(i, j int) bool { return events[i][1] < events[j][1] }) // 按照结束时间排序
	n := len(events)
	f := make([][]int, n+1)
	for i := range f {
		f[i] = make([]int, k+1)
	}
	for i, e := range events {
		p := sort.Search(i, func(j int) bool { return events[j][1] >= e[0] })
		for j := 1; j <= k; j++ {
			// 为什么是 p 不是 p+1：上面算的是 >= e[0]，-1 后得到 < e[0]，但由于还要 +1，抵消了
			f[i+1][j] = max(f[i][j], f[p][j-1]+e[2])
		}
	}
	return f[n][k]
}

func max(a, b int) int { if b > a { return b }; return a }

cpp 解法, 执行用时: 432 ms, 内存消耗: 87.3 MB, 提交时间: 2023-09-28 23:26:19

class Solution {
public:
    int maxValue(vector<vector<int>> &events, int k) {
        sort(events.begin(), events.end(), [](auto &a, auto &b) { return a[1] < b[1]; }); // 按照结束时间排序
        int n = events.size(), f[n + 1][k + 1];
        memset(f, 0, sizeof(f));
        for (int i = 0; i < n; ++i) {
            int p = lower_bound(events.begin(), events.begin() + i, events[i][0],
                                [](auto &e, int lower) { return e[1] < lower; }) - events.begin();
            for (int j = 1; j <= k; ++j)
                // 为什么是 p 不是 p+1：上面算的是 >= events[i][0]，-1 后得到 < events[i][0]，但由于还要 +1，抵消了
                f[i + 1][j] = max(f[i][j], f[p][j - 1] + events[i][2]);
        }
        return f[n][k];
    }
};

java 解法, 执行用时: 49 ms, 内存消耗: 115.2 MB, 提交时间: 2023-09-28 23:26:05

class Solution {
    public int maxValue(int[][] events, int k) {
        Arrays.sort(events, (a, b) -> a[1] - b[1]); // 按照结束时间排序
        var n = events.length;
        var f = new int[n + 1][k + 1];
        for (var i = 0; i < n; ++i) {
            var p = search(events, i, events[i][0]);
            for (var j = 1; j <= k; ++j)
                f[i + 1][j] = Math.max(f[i][j], f[p + 1][j - 1] + events[i][2]);
        }
        return f[n][k];
    }

    // 返回 endDay < upper 的最大下标
    private int search(int[][] events, int right, int upper) {
        var left = -1;
        while (left + 1 < right) {
            var mid = (left + right) / 2;
            if (events[mid][1] < upper) left = mid;
            else right = mid;
        }
        return left;
    }
}

python3 解法, 执行用时: 792 ms, 内存消耗: 62.5 MB, 提交时间: 2023-09-28 23:22:09

'''
定义 f[i][j] 表示参加前 i 个会议中的至多 j 个，能得到的会议价值的最大和。
'''
class Solution:
    def maxValue(self, events: List[List[int]], k: int) -> int:
        events.sort(key=lambda e: e[1])
        n = len(events)
        f = [[0] * (k + 1) for _ in range(n + 1)]
        for i, (start, end, val) in enumerate(events):
            p = bisect_left(events, start, hi=i, key=lambda e: e[1])  # hi=i 表示二分上界为 i（默认为 n）
            for j in range(1, k + 1):
                # 为什么是 p 不是 p+1：上面算的是 >= start，-1 后得到 < start，但由于还要 +1，抵消了
                f[i + 1][j] = max(f[i][j], f[p][j - 1] + val)
        return f[n][k]