Leetcode 2054. Two Best Non-Overlapping Events / 1235. Maximum Profit in Job Scheduling

[Woodyiiiiiii]

这种LIS的类型题目如下：

• 2054. Two Best Non-Overlapping Events
• 1751. Maximum Number of Events That Can Be Attended II
• 1235. Maximum Profit in Job Scheduling

还有：

• 2830. Maximize the Profit as the Salesman

这类题型的问题模版一般是：

1. 给一个数组，里面的区间可以按顺序增长选择
2. 可能有个最大范围k
3. 求最大利润

与LIS不同的是，不能直接用贪心去维护一个绝对单调递增的数列，因为加入了新的一个变量(利润)，所以要遍历所有可能的结果，选择最大的那个分枝。

解题思路是自顶向下的DP/记忆化搜索。先排序，再遍历数组，对于该当前元素分为两种情况，一种是选择该元素，另一种是不选择。递进公式是dp[i][j] = Math.max(dfs(events, i + 1, j, k, dp), dfs(events, nextIdx, j + 1, k, dp) + events[i][2])。选择该元素的情况下，就要通过二分法找到该元素下一个不相交冲突的元素；否则遍历到下一个元素。

DFS本来是要O(klgn2^n)，但因为有记忆化搜索，时间复杂度为O(knlgn)。

以1751. Maximum Number of Events That Can Be Attended II为例子：(可以从限制条件n * k的范围推算可以用记忆化)

class Solution {
    public int maxValue(int[][] events, int k) {
        int n = events.length;
        Arrays.sort(events, (o1, o2) -> {
            if (o1[0] == o2[0]) {
                return o1[1] - o2[1];
            }
            return o1[0] - o2[0];
        });
        int[][] dp = new int[n][k];
        return dfs(events, 0, 0, k, dp);
    }

    private int dfs(int[][] events, int i, int j, int k, int[][] dp) {
        if (i == events.length || j == k) return 0;
        if (dp[i][j] != 0) return dp[i][j];
        int nextIdx = bs(events, i);
        return dp[i][j] = Math.max(dfs(events, i + 1, j, k, dp), dfs(events, nextIdx, j + 1, k, dp) + events[i][2]);
    }

    private int bs(int[][] events, int i) {
        int l = 0, r = events.length;
        while (l < r) {
            int m = (l + r) >> 1;
            if (events[m][0] > events[i][1]) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
}

23/07/15我用DP复写了一遍，不同的是排序时要先以结束时间排序：

class Solution {
    public int maxValue(int[][] events, int k) {
        int n = events.length;
        Arrays.sort(events, (o1, o2) -> {
            if (o1[1] == o2[1]) {
                return o1[0] - o2[0];
            }
            return o1[1] - o2[1];
        });
        int[][] dp = new int[n][k + 1];
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= k; j++) {
                dp[i][j] = i - 1 >= 0 ? dp[i - 1][j] : 0;
                if (j > 0) {
                    int start = events[i][0];
                    int idx = bs(events, start, dp, i);
                    int pre = idx - 1 >= 0 ? dp[idx - 1][j - 1] : 0;
                    dp[i][j] = Math.max(dp[i][j], pre + events[i][2]);
                }
                ans = Math.max(ans, dp[i][j]);
            }
        }
        return ans;
    }

    // the smallest index that events[index][1] >= start
    private int bs(int[][] events, int start, int[][] dp, int i) {
        int l = 0, r = i;
        while (l < r) {
            int m = (l + r) >> 1;
            if (events[m][1] >= start) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
}

如果是k不限制的情况下1235. Maximum Profit in Job Scheduling，则不用二维数组：

class Solution {

    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        int[][] jobs = new int[n][3];
        for (int i = 0; i < n; ++i) {
            jobs[i][0] = startTime[i];
            jobs[i][1] = endTime[i];
            jobs[i][2] = profit[i];
        }
        Arrays.sort(jobs, (o1, o2) -> {
            if (o1[0] == o2[0]) {
                return o1[1] - o2[1];
            }
            return o1[0] - o2[0];
        });
        int[] dp = new int[n];
        return dfs(jobs, 0, dp);
    }

    private int dfs(int[][] jobs, int i, int[] dp) {
        if (i == jobs.length) return 0;
        if (dp[i] != 0) return dp[i];
        int nextIdx = bs(jobs, i);
        return dp[i] = Math.max(dfs(jobs, i + 1, dp), dfs(jobs, nextIdx, dp) + jobs[i][2]);
    }

    private int bs(int[][] events, int i) {
        int l = 0, r = events.length;
        while (l < r) {
            int m = (l + r) >> 1;
            if (events[m][0] >= events[i][1]) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
}

---

2054. Two Best Non-Overlapping Events这道题因为k确定是2，可以用堆来做。

class Solution {
    public int maxTwoEvents(int[][] events) {
        Arrays.sort(events, (o1, o2) -> {
            if (o1[0] == o2[0]) {
                return o1[1] - o2[1];
            }
            return o1[0] - o2[0];
        });
        int ans = 0, maxCompleted = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparing(o -> o[1]));
        for (int[] event : events) {
            while (!pq.isEmpty() && pq.peek()[1] < event[0]) {
                maxCompleted = Math.max(maxCompleted, pq.poll()[2]);
            }
            ans = Math.max(ans, maxCompleted + event[2]);
            pq.offer(event);
        }
        return ans;
    }
}

这有道类似的题目，可以锻炼下逻辑思维，有空可以做一下：1353. Maximum Number of Events That Can Be Attended

---

• https://leetcode.com/problems/two-best-non-overlapping-events/solutions/2475494/understanding-the-pattern-java-solution-recursion-memoization/