规划兼职工作

题目链接

规划兼职工作

题目描述

注意

• 1 <= startTime[i] < endTime[i] <= 10^9
• 时间上出现重叠的 2 份工作不能同时进行
• 如果你选择的工作在时间 X 结束，那么你可以立刻进行在时间 X 开始的下一份工作

解答思路

• 题目中并没有指名startTime以及endTime是否为升序排序，为了更方便进行遍历，需要新建一个Work类，包含startTime、endTime以及profit属性，同时设定一个比较规则，使其通过endTime来进行排序，这样做的目的是方便获取最先完成的工作
• 使用动态规划的思想，数组dp保存的是第i份工作的最大利润，从第0份工作开始求对应dp的值，其中第1份工作的最大利润dp[0]就是第1份工作的利润，而后第i份工作的最大利润应该从该份工作开始往前遍历找到第1份结束日期在该份工作开始日期之前的工作，保证可以工作时间上不冲突的同时该选择是最优选择，在选择后，还要与上一份工作的最大利润进行比较，值更大者才是当前这份工作的最大利润

代码

方法一：

class Solution {
    public int jobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.length;
        // 存储的是第i份工作的最大利润
        int[] dp = new int[n];
        // 存储的是按结束日期升序排列的第i份工作的信息
        Work[] works = new Work[n];
        for(int i = 0; i < n; i++) {
            works[i] = new Work(startTime[i], endTime[i], profit[i]);
        }
        Arrays.sort(works);
        for(int i = 0; i < n; i++) {
            if(i == 0) {
                dp[i] = works[i].profit;
            } else {
                // 前一份与之不重叠的工作的报酬
                int pre = 0;
                // 向前寻找第一个结束时间在本次工作开始时间之前的工作
                for(int j = i - 1; j >= 0; j--) {
                    if(works[j].endTime <= works[i].startTime) {
                        pre = dp[j];
                        break;
                    }
                }
                dp[i] = Math.max(dp[i - 1], pre + works[i].profit);
            }
        }
        return dp[n - 1];
    }

    // 兼职工作实体类，通过完成工作日期排序
    class Work implements Comparable<Work> {
        public int startTime, endTime, profit;
        public Work(int startTime, int endTime, int profit) {
            this.startTime = startTime;
            this.endTime = endTime;
            this.profit = profit;
        }
        public int compareTo(Work other) {
            return Integer.compare(this.endTime, other.endTime);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

关键点

• 要先将某一份工作的相关信息按照其结束时间来进行排序，方便获取最先完成的工作
• 对每一份工作i，dp[i]都会保证找到了第i份工作的最大利润，同时也是该份工作的结束时间为止的最大利润