结合了「二分」的线性 DP 经典题｜Java 刷题打卡-一一网

本文正在参加「Java主题月 – Java 刷题打卡」，详情查看活动链接

题目描述

这是 LeetCode 上的 1751. 最多可以参加的会议数目 II ，难度为困难。

Tag : 「二分」、「线性 DP」

给你一个 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^6$
1 <= startDayi <= endDayi <= $10^9$
1 <= valuei <= $10^6$

基本思路

定义 f[i][j] 为考虑前 i 个时间，选择不超过 j 的最大价值

对于每件时间，都有选择与不选两种选择，不选有 f[i][j] = f[i - 1][j]。

选择的话，则要找到第 i 件事件之前，与第 i 件事件不冲突的事件，记为 last，则有 f[i][j] = f[last][j - 1]。

两者取一个 max，则是 f[i][j] 的值。

分析到这里，因为我们要找 last，我们需要先对 events 的结束时间排序，然后找从右往左找，找到第一个满足 结束时间小于当前事件的开始时间 的事件，就是 last

而找 last 的过程，可以直接循环找，也可以通过二分来找，都能过。

动态规划

不通过「二分」来找 last 的 DP 解法。

代码：

class Solution {
    public int maxValue(int[][] es, int k) {
        int n = es.length;
        Arrays.sort(es, (a, b)->a[1]-b[1]);
        int[][] f = new int[n + 1][k + 1]; // f[i][j] 代表考虑前 i 个事件，选择不超过 j 的最大价值
        for (int i = 1; i <= n; i++) {
            int[] ev = es[i - 1];
            int s = ev[0], e = ev[1], v = ev[2];
            
            // 找到第 i 件事件之前，与第 i 件事件不冲突的事件
            // 对于当前事件而言，冲突与否，与 j 无关
            int last = 0;
            for (int p = i - 1; p >= 1; p--) {
                int[] prev = es[p - 1];
                if (prev[1] < s) {
                    last = p;
                    break;
                }
            }
            
            for (int j = 1; j <= k; j++) {
                f[i][j] = Math.max(f[i - 1][j], f[last][j - 1] + v);    
            }
        }
        return f[n][k];
    }
}
复制代码

时间复杂度：排序复杂度为 $O(n\log{n})$ ，循环 n 个事件，每次循环需要往回找一个事件，复杂度为 $O(n)$ ，并更新 k 个状态，复杂度为 $O(k)$ ，因此转移的复杂度为 $O(n * (n + k))$ ；总的复杂度为 $O(n * (n + k + \log{n}))$
空间复杂度： $O(n * k)$

二分 + 动态规划

通过「二分」来找 last 的 DP 解法。

代码：

class Solution {
    public int maxValue(int[][] es, int k) {
        int n = es.length;
        Arrays.sort(es, (a, b)->a[1]-b[1]);
        int[][] f = new int[n + 1][k + 1]; // f[i][j] 代表考虑前 i 个事件，选择不超过 j 的最大价值
        for (int i = 1; i <= n; i++) {
            int[] ev = es[i - 1];
            int s = ev[0], e = ev[1], v = ev[2];
            
            // 通过「二分」，找到第 i 件事件之前，与第 i 件事件不冲突的事件
            // 对于当前事件而言，冲突与否，与 j 无关
            int l = 1, r = i - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                int[] prev = es[mid - 1];
                if (prev[1] < s) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            int last = (r > 0 && es[r - 1][1] < s) ? r : 0;
            
            for (int j = 1; j <= k; j++) {
                f[i][j] = Math.max(f[i - 1][j], f[last][j - 1] + v);    
            }
        }
        return f[n][k];
    }
}
复制代码

时间复杂度：排序复杂度为 $O(n\log{n})$ ，循环 n 个事件，每次循环需要往回找一个事件，复杂度为 $O(\log{n})$ ，并更新 k 个状态，复杂度为 $O(k)$ ，因此转移的复杂度为 $O(n * (\log{n} + k))$ ；总的复杂度为 $O(n * (k + \log{n}))$
空间复杂度： $O(n * k)$