DP and binary search

Naive DP

High level explanation

The idea is pretty simple, kind of like Knapsack problem, we have two possible actions:

  • Take
  • Not take.

Specifically,

// take this start (i), the res will be profit + dp(j) where j is first non overlap index after i.
// not take this start (i), the res will be dp(i+1)

Code

typedef pair<int, int> PII;
const int N = 5e4 + 10;
int memo[N];
class Solution {
public:
int dp(vector<pair<PII, int>>& startEnd_pro, int i){
const int n = startEnd_pro.size();
if (i == n) return 0;
if (memo[i] != -1)return memo[i];
auto [startEnd, pro] = startEnd_pro[i];
auto [start, end] = startEnd;
int ret = pro;
// take this start, the res will be pro + dp(j) where j is next non overlap index
int j = findNext(startEnd_pro, i);
ret = max(ret, pro + dp(startEnd_pro, j));
// not take this start, the res will be dp(i+1)
ret = max(ret, dp(startEnd_pro, i+1));
return memo[i] = ret;
}
int findNext(vector<pair<PII, int>>& startEnd_pro, int i){
for (int j = i + 1; j < startEnd_pro.size(); ++j){
if (startEnd_pro[j].first.first >= startEnd_pro[i].first.second){
return j;
}
}
return startEnd_pro.size();
}
int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit) {
const int n = startTime.size();
vector<pair<PII, int>> startEnd_pro;
for (int i = 0; i < n; ++ i){
startEnd_pro.emplace_back(make_pair(startTime[i], endTime[i]), profit[i]);
}
sort(startEnd_pro.begin(), startEnd_pro.end());
memset(memo, -1, sizeof memo);
return dp(startEnd_pro, 0);
}
};

Complexity and run time

As the findNext has the complexity of O(n), the overall complextity is O(n²). This solution can already got AC with run time of 157 ms.

Improved one by binary search

only the findNext is updated, the run time is 149 ms.

int findNext(vector<pair<PII, int>>& startEnd_pro, int i){
pair<PII, int> key = make_pair(make_pair(startEnd_pro[i].first.second, -1), -1);
return upper_bound(startEnd_pro.begin(), startEnd_pro.end(), key) - startEnd_pro.begin();
}

Reference

[1] https://leetcode.com/problems/maximum-profit-in-job-scheduling/discuss/733167/Thinking-process-Top-down-DP-Bottom-up-DP

--

--

--

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Blog entry: Noob robotics — The body and new to 3D printing

Install Oracle Database 12c on Red Hat AWS EC2 Instance — Part 4: Install Database and Create…

Rust, second impression

Announcing Dash Bio 1.0.0

Sub query vs exist vs join performance in particular case

One man’s journey to Software Engineering…

Azure functions with docker? sure!

FarmerDoge x RetroDeFi

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Jimmy Shen

Jimmy Shen

Data Scientist/MLE/SWE @takemobi

More from Medium

Leetcode 862. Shortest Subarray with Sum at Least K

Leetcode Q390. Elimination Game (Q320)

Understanding Topological Sorting with Kahn’s Algo

1217. Minimum Cost to Move Chips to The Same Position(easy)