Calculate the maximum amount of money a person can make

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:

Complexity Analysis :

Time Complexity : O(Nlog(N))

Space Complexity : O(N)