Weighted activity selection

You’re the owner of a concert hall. There are a list of performances $[\mathrm{1..}n]$ with start time $s_i$, end time $t_i$ and price $p_i$. We want to pick the set of performances to rent out such that we can collect the maximum amount of rent collected.

This problem can be solved with DP. We consider the following properties:

• The solution space $S$ is given by all the subsets of performances that occur
• The function $f$ says that for each $s\in S$, we have $f(s)={\sum }_{i\in s}{p}_i$.
• The constraints $K$ here is that performances cannot overlap.

Problem

Input: tuples $(s_1,t_1,p_1),\dots ,(s_n,t_n,p_n)$.

Output: a subset $s\subset [n]$ such that the performances don’t overlap, and we get the maximum ${\sum }_{i\in s}{p}_i$.

Naive solution

$S$ are all the subsets of performances, which is given by $|S|=2^n$ (the power set). We could iterate through each one and calculate the collected rent for each. But this has an exponential runtime.

Potential high level questions

• We’re maximizing total rent collected, we should start with performances with the highest prices
• Performances can’t overlap, maybe we should keep track of the max possible money to be made in a given time period
• Sort the performances by price so we can consider the higher prices first
• Sort w.r.t. time so that we can easily check in linear time whether performances overlap

Some intuition

Let’s say that we process inputs by the starting times $s_i$, so $s_1<s_2<\cdots <s_n$. The question we should ask, is, do I rent out to performance $p_1$?

• If yes, then we find the first performer where $s_{j(1)}\ge t_1$, because anyone before the first performer’s end time cannot be booked. Then we can say the total reward is given by $p_1+\text{ALG}([j(1)..n])$, as we’re considering the rest of the performers recursively.
• If no, then we total reward is given by $\text{ALG}([\mathrm{2..}n])$. We don’t discard performance 1, we just don’t consider it, and recurse on the rest of the performances.

Greedily solving without caching

Similar to divide and conquer, we recurse into both options (yes or no), and then calculate the max reward we can get if we choose it. We then compare which one returns the higher price, $C_{\text{yes}}$ or $C_{\text{no}}$, and choose that instead.

The base case is when the array only has one element (some performance $i$), in which case we rent it out to them and return $p_i$.

1. Find $j(1)$, the successor to current first performance in the list.
2. Run the algorithm on array $[j(1)..n]$. return $C_{\text{yes}}$.
3. Run the algorithm on array $[\mathrm{2..}n]$. return $C_{\text{no}}$.
4. Output $\max (C_{\text{yes}}+p_1,C_{\text{no}})$.

Runtime

We can use binary search to find $j(1)$, which runs in $O(\log n)$. Then, we are recursing onto an array of size $n-j(1)$ (if we chose yes), as well as an array of size $n-1$ (if we chose no). The recurrence is then given by

$$T(n)=O(\log n)+T(n-j(1))+T(n-1)$$

Which must be greater than or equal to

$$T(n)=O(1)+2T(n-1)$$

Worst case, $j(1)=1$. We decrement $n$ by 1 each time so we will recurse $O(n)$ times, which means we multiply by $2$ a total of $n$ times. Therefore runtime is $2^n$. This… isn’t any better than naive.

Memoizing the previous algorithm

Using divide and conquer repeats calls to the same subarrays and so we waste time computing the same things over and over.

Let us cache values that we’ve computed, and whenever we’re about to recurse we first check if we’ve already computed it before. Before we execute a recursive call, we check if we’ve run it already.

Let $G[\mathrm{1..}n]$ be an array that stores our computed values. If a $G[i]$ is non-null, this means we’ve already computed the max reward for $[i..n]$. More formally, we can say

$$G[i]=\max (p_i+G[j(1)],G[i+1])$$

1. Find $j(1)$ using binary search.
2. Check if $G[j(1)]$ is non-null. If yes, then use that value. If not, then we actually recurse, and store the value $C_{\text{yes}}$ into $G[j(1)]$.
3. Do the same thing for $i=2$. check $G[2]$, if it’s non-null use the stored value, if it’s null then we recurse into $[\mathrm{2..}n]$ to calculate the value $C_{\text{no}}$ and store in $G[2]$.
4. Output $\max (p_i+C_{\text{yes}},C_{\text{no}})$.

Runtime

We do binary search $O(\log n)$ in each subproblem, where there are $n$ of. Therefore, the runtime is $O(n\log n)$.