传统的DP是将结果存在dp[]数组中,这题是用二分在结果数组res[]里找最接近startTime的结果。
struct Node{
int start, end, profit;
bool operator< (const Node &b) const{
return end < b.end;
}
};
typedef pair<int, int> PII;
class Solution {
public:
inline int find(vector<PII> &arr, int t){
if (arr.empty() || arr[0].first > t) return 0;
int l = 0, r = arr.size() - 1;
while (l < r){
int mid = (l+r+1)/2;
if (arr[mid].first <= t) l = mid;
else r = mid - 1;
}
return arr[l].second;
}
int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
int n = startTime.size();
vector<Node> arr(n);
vector<PII> res;
for (int i = 0; i<n; i++)
arr[i] = {startTime[i], endTime[i], profit[i]};
sort(arr.begin(), arr.end());
int max_profit = -1e9;
for (int i = 0; i<n; i++){
int t = arr[i].end;
int cur_profit = arr[i].profit + find(res, arr[i].start);
if ( cur_profit > max_profit){
res.push_back({t, cur_profit});
max_profit = cur_profit;
}
}
return max_profit;
}
};