This was asked in coding test of Cisco and nference
Given the start time, duration and values of ‘n’ different people, calculate the maximum value by adding the values of different people together. the values of 2 people can be added if their starting and ending time do not overlap.
Output: 5
Exp: if we start with person1 , we have total value as 2. it ends at 2, so it does not overlap with 2 or 3. if we take 2, the total value is 5 & for the case of 3,its 3. So the maximum value is 5.
I couldn’t solve the problem and hence ask my community for help. its kind of knapsack but overlapping thing is confusing me
Let dp[i] denote the maximum value which we can get, if we consider times from 1 to i.
Lets see where dp[i] can come from.
We decide to do nothing, so dp[i] comes from dp[i - 1]
We decide to add a person, whose end time(start[j] + duration[j]) matches with i. So in this case, dp[i] will come from dp[start[j]]. Furthermore, we have to add value[j] to it, so dp[i] = dp[start[j]] + value[j]
So currently we have, dp[i] = max(dp[i - 1], dp[start[j]] + value[j]) … for all j where end[j] = i.
This takes O(maxEndTime * N), where maxEndTime is the maximum ending time of a person.
This will clearly TLE.
To optimize the approach, we can take a vector of pairs v, containing pairs (end[j], value[j]), and sort it in ascending order according to end[j].
Now, if you notice, the values of end[j] is monotonic, i.e they are ascending or descending (here, they are ascending). So we don’t have to travel through the whole array each time. Instead, for computing dp[i], we can start from the position we were in after computing dp[i - 1]. Maintain a variable LastPos, which stores the last position after computing dp[i - 1].
Now the time complexity has been reduced from O(maxEndTime * N) to O(maxEndTime + N), which will clearly AC.