question
If you are given intervals for a list of tasks with start time and end time and a list of priorities for each tasks, you have to select two non-conflicting tasks whose sum of priorities will be maximum
I am thinking of a greedy approach, but I am not able fully arrive at solution can anyone help me
Can you send the entire question like sample input and sample output as it would help to get a bettter idea on the problems.
This question was asked sometime back in an online coding round, I wasn’t able to do it at that time. So I asked it here if anyone has an approach. I don’t have the entire question, but I remember trying to solve this question as a variation of the weighted activity selection problem, but I failed.
I think we can solve it like this -
Sort the array on the basis of end times. Then for each index/interval we can find the best non intersecting interval. For that we can make a prefix array of max priorities till ith index, we can binary search the first index to our left which will be non overlapping, say its x and then sum of priority will be pre[x] + current interval priority . So we can do this for each interval, and then just take the best answer.
I think we can sort the segments based on start times and for the current segment(say ith segment), we can have the maximum priority(mx) of the set of segments seen so far that is non-overlapping with the current segment and update answer = max(answer, priority[i] + mx), we don’t need binary search as such as this will handle all such pairs (i,j) as we move through different segments