题目地址：

https://leetcode.com/problems/maximum-profit-in-job-scheduling/

给定 n n n个任务，每个任务有个开始时间、结束时间和利润，同一时刻只能做一个任务（如果某个任务的开始时间恰好是另一个任务的结束时间，这个情况是允许的），问最大利润。

0 − 1 0-1 0−1背包问题，思路是动态规划。先将所有任务按照结束时间排序，设 f [ i ] f[i] f[i]是只考虑前 i i i个任务的情况下能得到的最大利润。那么可以按照第 i i i个任务做不做来分类，如果不做，则最大利润是 f [ i − 1 ] f[i-1] f[i−1]，如果做，则要向前找最后一个能做的任务是第几个，这可以用二分，如果找不到，那说明只能做第 i i i个任务了，则 f [ i ] = p [ i ] f[i]=p[i] f[i]=p[i]（ p [ i ] p[i] p[i]是第 i i i个任务的利润），否则设第 k k k个任务是下标最大的且结束在第 i i i个任务开始时间之前的任务，则有 f [ i ] = p [ i ] + f [ k ] f[i]=p[i]+f[k] f[i]=p[i]+f[k]。由于任务已经按照结束时间排序，所以可以用二分来确定 k k k。综上： f [ i ] = max ⁡ { f [ i − 1 ] , f [ k ] + p [ i ] } f[i]=\max\{f[i-1],f[k]+p[i]\} f[i]=max{f[i−1],f[k]+p[i]}最后返回 f [ n ] f[n] f[n]。代码如下：

import java.util.Arrays;

public 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, (j1, j2) -> Integer.compare(j1[1], j2[1]));
        
        int[] f = new int[n + 1];
        for (int i = 1; i <= n; i++) {
        	// 考虑不做第i个任务的情况
            f[i] = f[i - 1];
            // 如果做第i个任务，则在第1到底i - 1个任务里找最后一个
            // 可以结束在第i个任务开始时间之前的任务下标
            int idx = binarySearch(jobs, i - 2, jobs[i - 1][0]);
            f[i] = Math.max(f[i], jobs[i - 1][2] + f[idx + 1]);
        }
        
        return f[n];
    }
    
    private int binarySearch(int[][] jobs, int r, int t) {
        int l = 0;
        while (l < r) {
            int m = l + (r - l + 1 >> 1);
            if (jobs[m][1] <= t) {
                l = m;
            } else {
                r = m - 1;
            }
        }
        
        return jobs[l][1] <= t ? l : -1;
    }
}

时间复杂度 O ( n log ⁡ n ) O(n\log n) O(nlogn)，空间 O ( n ) O(n) O(n)。