题目分析

本题也是经典的动态规划问题了，其实难度并没有hard的level，小伙伴们想一下如何构造状态转移方程？

动态规划

遇到时间类的问题，一般的思路是按照开始时间或者结束时间进行排序。

根据数据量可知，startTime[i]是1e9的量级，因此把时间作为自变量是不可能的，如果量级是1e7以下，可以用dp[i]表示i时刻以内，可以赚取的最大零花钱。

那么只能用dp[i]表示前i份工作可以获取的最大零花钱，则dp[i] = max(dp[i - 1], dp[k] + profit[i])。

因为只有在第i份工作结束后才能拿到对应的钱，因此结束越早的工作，越应该提前考虑去做。本题明显是按照结束时间排序的

其中k满足第k份工作的结束时间小于等于第i份工作的开始时间。因为工作按照结束时间排序，因此也可以使用二分来迅速查找符合条件的k。

所以算法的**时间复杂度为O(nlog(n))，空间复杂度为O(n)**。

class Solution {
    public static void main(String[] args) {
        System.out.println(new Solution().jobScheduling(new int[]{1,2,3,3}, new int[]{3,4,5,6}, new int[]{50, 10, 40, 70}));
    }

    private int[] endTime;

    private Integer[] arr;

    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        arr = IntStream.range(0, n).boxed().toArray(Integer[]::new);
        this.endTime = endTime;
        Arrays.sort(arr, Comparator.comparingInt(t -> endTime[t]));
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int k = startTime[arr[i - 1]] < endTime[arr[0]] ? -1 : binarySearch(i - 1, startTime[arr[i - 1]]);
            dp[i] = Math.max(dp[i - 1], dp[k + 1] + profit[arr[i - 1]]);
        }
        return dp[n];
    }

    private int binarySearch(int right, int target) {
        int left = 0;
        while (left < right) {
            int mid = (left + right + 1) >> 1;
            if (endTime[arr[mid]] <= target) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}

刷题总结

本题难度不大，希望小伙伴们务必能够独立求解本题。现在互联网的环境越来越卷，这种动态规划可能已经是面试中最简单的题型的，因此一定要会做它。