1235. 规划兼职工作：区间排序 + 动态规划 + 二分查找，联合食用.md

题目简述：

你打算利用空闲时间来做兼职工作赚些零花钱。

这里有 n 份兼职工作，每份工作预计从 startTime[i] 开始到 endTime[i] 结束，报酬为 profit[i]。

给你一份兼职工作表，包含开始时间 startTime，结束时间 endTime 和预计报酬 profit 三个数组，请你计算并返回可以获得的最大报酬。

注意，时间上出现重叠的 2 份工作不能同时进行。

如果你选择的工作在时间 X 结束，那么你可以立刻进行在时间 X 开始的下一份工作。

题目链接：1235. 规划兼职工作

思路

对于这类涉及区间顺序问题，首先对区间进行排序，这一步几乎可以无脑进行。考虑按区间左端点排序。

然后我原本考虑直接暴力 DFS 加记忆化搜索，利用二分查找找到做完某项工作后的剩余可做工作，但在探索 DFS 参数时发现 DFS 可以设计为「在结束了当前最晚的兼职工作后，对于剩余工作至多能通过兼职获得多少零花钱」，这便自然引出 DP。

考虑 $dp[i]$ 表示仅考虑起始时间顺序第 $i$ 项及其之后的所有兼职工作时，至多能够获得多少报酬。对于第 $i$ 项兼职工作，我们有两种选择：

1. 不完成该项兼职工作，此时获得的最大报酬为 $dp[i+1]$；
2. 完成该项兼职工作，此时获得 $profit[i]$ 的报酬，并且下一项可选择的兼职工作必须满足其开始时间不早于当前兼职工作的结束时间。记满足该条件的最小下标为 $j$，则此时获得的最大报酬为 $profit[i] + dp[j]$。

因此有状态转移方程： $$ dp[i]=\max{dp[i+1],\ profit[i]+dp[j]} $$ 其中 $$ j=\min{k:k>i,\ startTime[k]\geqslant endTime[i]} $$ 注：上述 $startTime$、$endTime$ 与 $profit$ 数组均已按照 $startTime$ 升序排序，并保持对应关系不变。

其中，最小的合法 $j$ 通过二分查找确定。

代码

算法的时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。

class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        Integer[] idx = new Integer[n];
        for (int i = 0; i < n; i++) idx[i] = i;
        Arrays.sort(idx, (a, b) -> Integer.compare(startTime[a], startTime[b]));

        int[] dp = new int[n + 1];
        // dp[n] = 0;
        for (int i = n - 1; i >= 0; i--) {
            int target = endTime[idx[i]];
            int l = i;
            int r = n - 1;
            while (l <= r) {
                int mid = l + (r - l) / 2;
                if (startTime[idx[mid]] < target) l = mid + 1;
                else r = mid - 1;
            }

            // dp[i] = 0;
            dp[i] = Math.max(dp[i + 1], profit[idx[i]] + dp[l]);
        }

        return dp[0];
    }
}