Hard

题目描述

我们有 n 份工作，其中每份工作都安排在 startTime[i] 到 endTime[i] 时间内进行，可以获得 profit[i] 的利润。

给你 startTime，endTime 和 profit 数组，请你返回可以获得的最大利润，使得所选择的工作时间范围互不重叠。

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

示例 1：

输入：startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70]
输出：120
解释：我们选出第 1 份和第 4 份工作， 
时间范围是 [1-3]+[3-6]，我们可以获得的利润是 120 = 50 + 70。

示例 2：

输入：startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60]
输出：150
解释：我们选择第 1，4，5 份工作。 
获得的利润是 150 = 20 + 70 + 60。

示例 3：

输入：startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4]
输出：6

提示：

  • 1 <= startTime.length == endTime.length == profit.length <= 5 * 10^4
  • 1 <= startTime[i] < endTime[i] <= 10^9
  • 1 <= profit[i] <= 10^4

解题思路

这是一个经典的动态规划问题，类似于带权重的区间调度最大化问题。

解题思路：

  1. 预处理和排序：将工作按照结束时间排序，这样便于后续的动态规划状态转移。

  2. 动态规划状态定义：定义 dp[i] 表示考虑前 i 个工作能获得的最大利润。

  3. 状态转移：对于第 i 个工作，我们有两种选择：

    • 不选择第 i 个工作：dp[i] = dp[i-1]
    • 选择第 i 个工作：需要找到最晚的一个与第 i 个工作不冲突的工作 j，则 dp[i] = dp[j] + profit[i]

  4. 二分查找优化：为了快速找到不冲突的工作，我们使用二分查找。在按结束时间排序的数组中，寻找结束时间小于等于当前工作开始时间的最右位置。

算法步骤：

  • 将所有工作信息打包并按结束时间排序
  • 使用动态规划，对每个工作决策选择或不选择
  • 通过二分查找快速定位不冲突的前一个工作
  • 返回最后的最大利润

这种方法时间复杂度为 O(n log n)，空间复杂度为 O(n)，是最优解法。

代码实现

class Solution {
public:
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        int n = startTime.size();
        vector<vector<int>> jobs(n);
        
        // 将工作信息打包
        for (int i = 0; i < n; i++) {
            jobs[i] = {endTime[i], startTime[i], profit[i]};
        }
        
        // 按结束时间排序
        sort(jobs.begin(), jobs.end());
        
        vector<int> dp(n + 1, 0);
        
        for (int i = 1; i <= n; i++) {
            int currentProfit = jobs[i-1][2];
            int currentStart = jobs[i-1][1];
            
            // 不选择当前工作
            dp[i] = dp[i-1];
            
            // 二分查找最晚的不冲突工作
            int left = 0, right = i - 1;
            int lastJob = 0;
            
            while (left <= right) {
                int mid = (left + right) / 2;
                if (jobs[mid][0] <= currentStart) {
                    lastJob = mid + 1;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            
            // 选择当前工作
            dp[i] = max(dp[i], dp[lastJob] + currentProfit);
        }
        
        return dp[n];
    }
};

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:
        n = len(startTime)
        jobs = []
        
        # 将工作信息打包并按结束时间排序
        for i in range(n):
            jobs.append([endTime[i], startTime[i], profit[i]])
        
        jobs.sort()
        
        dp = [0] * (n + 1)
        
        for i in range(1, n + 1):
            current_profit = jobs[i-1][2]
            current_start = jobs[i-1][1]
            
            # 不选择当前工作
            dp[i] = dp[i-1]
            
            # 二分查找最晚的不冲突工作
            left, right = 0, i - 1
            last_job = 0
            
            while left <= right:
                mid = (left + right) // 2
                if jobs[mid][0] <= current_start:
                    last_job = mid + 1
                    left = mid + 1
                else:
                    right = mid - 1
            
            # 选择当前工作
            dp[i] = max(dp[i], dp[last_job] + current_profit)
        
        return dp[n]

public class Solution {
    public int JobScheduling(int[] startTime, int[] endTime, int[] profit) {
        int n = startTime.Length;
        int[][] jobs = new int[n][];
        
        // 将工作信息打包
        for (int i = 0; i < n; i++) {
            jobs[i] = new int[] {endTime[i], startTime[i], profit[i]};
        }
        
        // 按结束时间排序
        Array.Sort(jobs, (a, b) => a[0].CompareTo(b[0]));
        
        int[] dp = new int[n + 1];
        
        for (int i = 1; i <= n; i++) {
            int currentProfit = jobs[i-1][2];
            int currentStart = jobs[i-1][1];
            
            // 不选择当前工作
            dp[i] = dp[i-1];
            
            // 二分查找最晚的不冲突工作
            int left = 0, right = i - 1;
            int lastJob = 0;
            
            while (left <= right) {
                int mid = (left + right) / 2;
                if (jobs[mid][0] <= currentStart) {
                    lastJob = mid + 1;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            
            // 选择当前工作
            dp[i] = Math.Max(dp[i], dp[lastJob] + currentProfit);
        }
        
        return dp[n];
    }
}

var jobScheduling = function(startTime, endTime, profit) {
    const n = startTime.length;
    const jobs = [];
    
    // 将工作信息打包
    for (let i = 0; i < n; i++) {
        jobs.push([endTime[i], startTime[i], profit[i]]);
    }
    
    // 按结束时间排序
    jobs.sort((a, b) => a[0] - b[0]);
    
    const dp = new Array(n + 1).fill(0);
    
    for (let i = 1; i <= n; i++) {
        const currentProfit = jobs[i-1][2];
        const currentStart = jobs[i-1][1];
        
        // 不选择当前工作
        dp[i] = dp[i-1];
        
        // 二分查找最晚的不冲突工作
        let left = 0, right = i - 1;
        let lastJob = 0;
        
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            if (jobs[mid][0] <= currentStart) {
                lastJob = mid + 1;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        // 选择当前工作
        dp[i] = Math.max(dp[i], dp[lastJob] + currentProfit);
    }
    
    return dp[n];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

算法时间复杂度空间复杂度
动态规划 + 二分查找O(n log n)O(n)
  • 时间复杂度：O(n log n)，其中排序需要 O(n log n)，动态规划过程中每次二分查找需要 O(log n)，总共 n 次
  • 空间复杂度：O(n)，用于存储 dp 数组和工作信息数组

相关题目