Given three arrays start[], duration[], amount[] of length N. A person can make money of amount[i] working for the time period [start[i], start[i]+duration[i]] on task i. Maximum amount of money a person can make from the N tasks.
Note: Person can work on only one task at a time.
Example :
Input : start[] = {15, 10, 30, 5, 18}; duration[] = {20, 30, 35, 12, 35} amount[] = {20, 50, 10, 51, 25} Output : 76 Explanation : Person will work on task 3 for the duration of [5, 17] and work on task 4 for the duration of [18, 53] Therefore , Maximum amount = 51+25 = 76
Approach :
- Sort all the arrays in the increasing order of start time of tasks
- Declare dp[N], where dp[i] is maximum amount of money a person can make having tasks [i, i+1,….N-1] in hand.
- Initialize dp[N-1] = amount[N-1]
- Iterate for N-1 times with pointer i = N-2
- If you choose to work on task i, then money = amount[i], and find the lower_bound of start[i]+duration[i] in start array as index.Then increment money +=dp[index]
- Store dp[i] = max(dp[i+1], money)
- Print dp[0] as the maximum amount of money a person can make having tasks [0,1,…N-1] in hand.
Implementation in C++:
//C++ program to calculate the maximum amount of money a person can make #include <iostream> #include<bits/stdc++.h> using namespace std; //Structure definition struct work{ int start; int duration; int amount; }; //Comparision function for sorting the structure members //in the increasing order of start time of tasks bool compare(struct work t1, struct work t2) { return t1.start<t2.start; } //Function to get the first index at which start time >= val int bin_search(struct work A[], int lo, int hi, int val) { int mid; //Iterate until they are equal while(lo<hi) { //Calculate mid index mid = lo + (hi-lo)/2; //If val lies to right if(val > A[mid].start) lo = mid+1; //Else value lies to left else hi = mid; } //Return the index as lo return lo; } int main() { //Input arrays start[], duration[] and amont[] //Length N = 5 int N = 5, i; int start[] = {15, 10, 30, 5, 18}; int duration[] = {20, 30, 35, 12, 35}; int amount[] = {20, 50, 10, 51, 25}; //Create an array of structure variable for storing //input data struct work A[N]; //Store the values at corresponding index for(i=0;i<N;i++) { A[i].start = start[i]; A[i].duration = duration[i]; A[i].amount = amount[i]; } //Sort the structure in the increasing order of start time of tasks sort(A,A+N,compare); //Create a dp[] of length N int dp[N], money, in; //Intialize dp[N-1] = amount[N-1] as there is only one task //to complete dp[N-1] = amount[N-1]; for(i=N-2;i>=0;i--) { //dp[i] is maximum amount a person can make //having tasks of [i, i+1, N-1] in hand //If he works on task i money = A[i].amount; //If end time of task i <= start time of task N-1, //then the person can complete atleast one more task if(A[i].start+A[i].duration<=A[N-1].start) { //Search for first index whose start time > A[i].start1+A[i].duration1 in = bin_search(A,i+1,N-1,A[i].start+A[i].duration); //Add the amount a person gets working on task [in, in+1,..N-1] money +=dp[in]; } //If completing task i gives more amount than not acompleting //task i and moving to (i+1) if(money>dp[i+1]) dp[i] = money; //Else, if chosing not to complete task i else dp[i] = dp[i+1]; } //Return maximum amount a person can make having tasks [0,1,..N-1] in hans cout<<dp[0]; return 0; }
Output:
76
Complexity Analysis :
Time Complexity : O(Nlog(N))
Space Complexity : O(N)