Description

有\(n\)个任务，每个任务需要在\([lo_i, hi_i]\)时间区间内调度并占用时间，可以从中获得\(p_i\)利润。求不重叠的任务调度能获得的最大利润

Constraints

时间复杂度不得超过\(O(nlogn)\)

Solution

这题和630有点像，但是时间是固定的不能自由安排，固定的区间可以考虑dp

设\(dp[i]\)：前\(i\)个区间子集合的最大利润。\(dp[i]\)需要找到某个\(j \in [0, i-1]\)，使得\(dp[i] = max(dp[j] + p_i, dp[i-1])\)

为了能找到\(j\)，原区间先按右端点排序

Code

class Solution {
public:
    int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
        using Tup = tuple<int, int, int>;
        vector<Tup> vec;
        for(size_t i = 0; i < startTime.size(); ++i) {
            vec.emplace_back(startTime[i], endTime[i], profit[i]);
        }
        sort(vec.begin(), vec.end(), [&](auto &lhs, auto &rhs) {
            return get<1>(lhs) < get<1>(rhs);
        });

        vector<int> dp(vec.size(), 0);
        for(size_t i = 0; i < vec.size(); ++i) {
            auto [s, e, p] = vec[i];
            if(i == 0) {
                dp[i] = p;
                continue;
            }
            int lo = 0, hi = i-1;
            while(lo < hi) {
                int mid = lo + (hi - lo + 1) / 2;
                auto [_, je, _2] = vec[mid];
                if(je <= s) {
                    lo = mid;
                } else {
                    hi = mid - 1;
                }
            }
            auto [_, je, _2] = vec[lo];
            if(je <= s) {
                dp[i] = max(dp[i-1], p + dp[lo]);
            } else {
                dp[i] = max(dp[i-1], p);
            }
        }
        return dp.back();
    }
};

Link

LeetCode-1235 Maximum Profit in Job Scheduling