Daily bit(e) of C++ | Optimizing conference value
Daily bit(e) of C++ #238, Common interview problem: Optimizing conference value.
Today, we will look at a common interview problem: Optimizing conference value.
Given a conference schedule as std::vector<Talk>, where Talk = {start, end, value}, return the maximum total value you can obtain by attending at most k talks.
Start and end times are exclusive (i.e. the earliest start time for the next event is end+1).
For example, for the input: {1,5,5}, {3,8,11},{7,12,4}, the maximum value is obtained by attending a single talk; therefore, for any k (except for zero), the result will be 11.
Before you continue reading, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/31nxxG85W.
Solution
We can choose to attend each talk or not, leading to overall 2^cnt possible combinations (slightly less since we are limited by k). This would be infeasible.
We can employ a top-down approach if we first sort the events by their start time. Then, we can calculate the optimal value recursively by considering the talk at index idx:
If we do not pick a talk, the total value is: max_value(idx+1, earliest, attended), re-using the earliest start value and the number of already attended talks.
If we pick the talk, the total value is: talks[idx].value + max_value(idx+1, talks[idx].end+1, attended+1).
We can also do a bottom-up solution; however, we need one more step. Since we will be revisiting each talk multiple times (due to the second dimension created by k), pre-calculating the next feasible talk will be helpful.
Our overall solution:
sort the talks based on their start time
pre-calculate the next feasible talk using binary search (for each talk)
calculate the cnt*k matrix
