# Help writing a dynamic programming algorithm in English

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.

• The best approach to start these exercise is to "simplify" the problem as much as possible. You are given a set of weighted segments and need to choose a subset of disjoint segments with maximum weight. What if weights are equal to 1 (greedy works here and maybe give you a hint about the general problem). Nov 1, 2018 at 19:03
• You can use LaTeX to typeset mathematics, even in comment. I edited to show you how; we also have a brief tutorial and more complete reference Nov 1, 2018 at 22:52

The subproblems are computing $$v[i]$$, the maximal total value you can get when you just finished party $$P_i$$. To help computing these subproblems, that is, from earlier subproblems to later subproblems, you may sort the parties by their ending times so that $$P_1,P_2,\cdots,P_n$$ end in order of time. After the sorting, $$v[i]$$ will only depend on those $$v[j]$$ where $$j or, to be more precise, those $$P_j$$ whose ending time is before $$P_i$$'s starting time. (This condition can be made even more restrictive, which may be unnecessary for your exercise and which may be necessary to get a better grade.) There are several more details such as the base case and the recurrence relation, which I will leave for you to fill in.
• You need to keep track of all $v[i]$, which is an array of values. Can you see how you can get the largest possible of them? Just select the largest possible of them once have computed all of them. Nov 1, 2018 at 22:55
• Assume you know all $v[j]$ for $j<i$, how can you compute $v[i]$? For example, if you know the maximal total value for every party $P_j$ before $P_1$ (which is just $P_0$), can you get $v[1]$? If you know the maximal total value for every party $P_j$ before $P_2$ (which are $P_0$ and $P_1$), can you get $v[2]$? If you know the maximal total value for every party $P_j$ before $P_3$, can you get $v[3]$? And so on. Nov 1, 2018 at 23:01
• Just to make sure I am understanding it correctly, the maximum v is found by assuming that we know the maximum $v_i$ that ends at $t_i$ and then finding the maximum $v_j$ where $s_j$ > $t_i$. Nov 1, 2018 at 23:15