Here is the problem statament
2 thigs we will use in this task 1. Dynamic Programming 2. Binary search
First of all we sort our array by the start time.
Suppose this is our array
s1 e1 c1 (start, end, cost)
s2 e2 c2
...
...
sn en cn
Then we will keep our array for dynamic programming approach, we call it dp. As we all know, for dynamic programming we need to build our current solution based on the ones we got from our previous operations. We need to loop from back of the sorted array. When we are on I th element. We need to find the leftmost element which is on the right side of I ( index is grater than I) and the start time of that element is more than the end time of our current element( AKA we can take the Ith order and the order which we found with this step). That will be element with the index J. So we are sure that the orders from J-1 to I+1 can't be taken If we take teh order I. So does it worth it? That makes our dp[I]= max (dp[I-1], dp[J]+cost[I]) (AKA we either reject this order and take the profit we already collected ,or we reject all the orders from I+1 to J-1 to take the order I). Make sure to check the source code for a better understanding ,
Please stop writing blogs :P not your cup of tea
ReplyDelete