1751. 最多可以参加的会议数目IIJava

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你一个 events 数组，其中 events[i] = [startDayi, endDayi, valuei] ，表示第 i 个会议在 startDayi 天开始，第 endDayi 天结束，如果你参加这个会议，你能得到价值 valuei 。同时给你一个整数 k 表示你能参加的最多会议数目。

你同一时间只能参加一个会议。如果你选择参加某个会议，那么你必须完整地参加完这个会议。会议结束日期是包含在会议内的，也就是说你不能同时参加一个开始日期与另一个结束日期相同的两个会议。

请你返回能得到的会议价值最大和。

示例 1：

输入：events = [[1,2,4],[3,4,3],[2,3,1]], k = 2
输出：7
解释：选择绿色的活动会议 0 和 1，得到总价值和为 4 + 3 = 7 。

示例 2：

输入：events = [[1,2,4],[3,4,3],[2,3,10]], k = 2
输出：10
解释：参加会议 2 ，得到价值和为 10 。
你没法再参加别的会议了，因为跟会议 2 有重叠。你 不 需要参加满 k 个会议。

示例 3：

输入：events = [[1,1,1],[2,2,2],[3,3,3],[4,4,4]], k = 3
输出：9
解释：尽管会议互不重叠，你只能参加 3 个会议，所以选择价值最大的 3 个会议。

提示：

1 <= k <= events.length
1 <= k * events.length <= 10⁶
1 <= startDayi <= endDayi <= 10⁹
1 <= valuei <= 10⁶

# 思路

dp + 二分

# 解法

class Solution {
    public int maxValue(int[][] events, int k) {
        List<int[]> dp = new ArrayList<>(List.of(new int[k+1]));
        Arrays.sort(events, Comparator.comparingInt(o -> o[1]));
        int max = 0;
        for (int i = 0; i < events.length; i++) {
            int l = 0, r = dp.size()-1, mid = r >> 1;
            while (l < r) {
                if (dp.get(mid)[k] < events[i][0]) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
                mid = l + ((r - l + 1) >> 1);
            }
            int[] ints = dp.get(l);
            int[] res;
            int[] pre = dp.get(dp.size()-1);
            if (dp.get(dp.size()-1)[k] == events[i][1]) {
                res = dp.get(dp.size()-1);
            } else {
                res = new int[k+1];
                dp.add(res);
            }
            res[0] = Math.max(Math.max(res[0], pre[0]), events[i][2]);
            res[k] = events[i][1];
            for (int j = 1; j < k; j++) {
                res[j] = Math.max(ints[j-1] + events[i][2], Math.max(res[j], pre[j]));
            }
            max = Math.max(max, res[k-1]);
        }
        return max;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

# 总结

分析出几种情况，然后分别对各个情况实现

#Java