2
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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). $\endgroup$
    – Marcelo Fornet
    Nov 1, 2018 at 19:03
  • $\begingroup$ 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 $\endgroup$
    – John L.
    Nov 1, 2018 at 22:52

1 Answer 1

Reset to default
0
$\begingroup$

Since this problem is a learning exercise of yours, I will just write the ordered subproblems used in dynamic programming. In general, I consider it is about more than half way through a nontrivial problem that can be solved by dynamic programming when the ordered subproblems have been specified clearly, at least in term of "difficult" thinking since the rest are more routine.

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<i$ 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.

Improve this answer
$\endgroup$
8
  • $\begingroup$ Thank you for the response, I should have specified that I did not want a solution, and rather just guidance. Would the recurrence relation be to select a party P(sub)i whose start time is less than or equal to the end time of the previous party? And then my base case would be when an end time is greater than or equal to the time range for when I would stop attending parties? If this is the case, I am unsure of what data structure I should maintain in order to keep track of the largest possible v(sub)i $\endgroup$
    – Colin Null
    Nov 1, 2018 at 22:33
  • $\begingroup$ 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. $\endgroup$
    – John L.
    Nov 1, 2018 at 22:55
  • $\begingroup$ That makes sense. Does my recursive step and my base case make sense for this problem? I feel as if it may be incomplete at this moment. $\endgroup$
    – Colin Null
    Nov 1, 2018 at 22:59
  • $\begingroup$ 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. $\endgroup$
    – John L.
    Nov 1, 2018 at 23:01
  • $\begingroup$ 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$. $\endgroup$
    – Colin Null
    Nov 1, 2018 at 23:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.