It’s Friday night and you have $n$ parties to go to. Party $i$ has a start time $s_i$ end time $t_i$ and a value $v_i \ge 0$. Think of the value as an indicator of how excited you are about that party. You want to pick a subset of the parties to attend so that you get maximum total value. The only constraint is that in order to get a value $v_i$ from party $i$ you need to attend the party from start to finish. Hence you cannot drop in midway and leave before the party ends. This means that if two parties overlap, you can only attend one of them. For example, if party 1 has a start time of 7pm and ends at 9pm and party 2 starts at 7:30pm and ends at 10pm, you can only attend one of them. On the other hand, if party 2 starts at 9pm or later then you can attend both. Given as input start times, end times and values of each of the n parties, design an $O(n \log n)$ time algorithm to plan your night optimally. Describe in English the idea of your algorithm. If you use dynamic programming define the memo table, base case and recursive steps. You don’t need to write the pseudo code or provide a proof of correctness.

I am having difficulty beginning this problem. My initial thought was to have the base case be to choose the value with the initial start time and the greatest $v_i$, however if party $i$ runs for your entire start to end time, you might not maximize $v_i$. I would greatly appreciate some insight into how to do this problem.

没有正确的解决方案

许可以下: CC-BY-SA归因
不隶属于 cs.stackexchange
scroll top