1235. Maximum Profit in Job Scheduling

Description

image-20211117153013070

image-20211117153023077

Solution

Time interval question.

An simple intuition should be, if we find a best solution for a previous time, then we could use this information to calculate the later one with startTime[i] > endTime[i-1].

So we could use binary search to find the endTime suitable for current startTime.

To use bs, we need sort by endTime.

Code

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
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] = {startTime[i], endTime[i], profit[i]};
        sort(jobs.begin(), jobs.end(), [](vector<int> &a, vector<int> &b){
            if(a[1] == b[1])
                return a[0] < b[0];
            return a[1] < b[1];
        });
        vector<int> dp(n);
        vector<int> before;
        //dp[i] -> includesively previous i's jobs' maximum profits, dp[i] = max(dp[i-1], dp[bs(starttime)] + jobs[i].profit)
        int res = 0;
        dp[0] = jobs[0][2];
        before.push_back(jobs[0][1]);
        for(int i = 1 ; i < n; i++){
            dp[i] = dp[i-1];
            auto iter = upper_bound(before.begin(), before.end(), jobs[i][0]);
            if(iter != before.begin() && *prev(iter) <= jobs[i][0]){
                dp[i] = max(dp[i], dp[prev(iter) - before.begin()] + jobs[i][2]);
            }else{
                dp[i] = max(dp[i], jobs[i][2]);
            }
            before.push_back(jobs[i][1]);
            res = max(res, dp[i]);
        }
        return res;
    }
};