Picking tasks in a time budget

Problem

Input: sequence of tasks $t_1,t_2,\dots ,t_n$ where a $t_i\in {\mathbb{R}}_{\ge 0}$ represents the amount of time it takes to complete it. We also have a time budget $T$.

Output: maximize the number of tasks completed within time $T$.

Just like DP, we are able to consider the solution space, objective function, and constraint.

• Solution space: all possible sets of tasks.
• Objective function: a function $f$ such that given a set $S$ of tasks, $f(s)=|S|$. We want to maximize $f$.
• Constraint: given the set of tasks $S$, it must be true that ${\sum }_{t\in S}t\le T$.

Algorithm

Sort the tasks by time it takes to complete it. Pick the shortest time task until we hit our time budget.

Proof of correctness

We sort tasks in increasing length such that $t_1\le t_2\le \cdots \le t_n$. Then, up until a task $t_m$, we can say that the total time taken must be $T_{t_m}$, which must be less than $T$.

Let $G$ be the solution from our greedy algorithm, which consists of tasks $t_1,t_2,\dots ,t_m,t_{m+1},\dots$. In addition, we assume there exists another optimal solution $\text{OPT}$ such that it contains $t_1,t_2,\dots ,t_k,t_{k+1},\dots$

It is convenient for us that we can sort the tasks by time. Then we can say the first $k$ tasks we choose, but really we can say that there exists any $k$ decisions in $\text{OPT}$ that is the same as in $G$. This makes proving our algorithm harder, though.

Lemma

Assume for induction that $\text{OPT}$ contains $t_1,t_2,\dots ,t_k$ from $G$ where $k\le m$. This is our induction hypothesis. We want to prove that there exists a new ${\text{OPT}}^{\prime }$ such that it is

1. feasible (this means we’re still within our constraints)
2. $|\text{OPT}|=|{\text{OPT}}^{\prime }|$
3. ${\text{OPT}}^{\prime }$ contains $t_1,t_2,\dots ,t_k$ as well as $t_{k+1}$.

We want to show how to construct ${\text{OPT}}^{\prime }$ from $\text{OPT}$. This is an Exchange argument.

Case 1

$\text{OPT}$ contains $t_{k+1}$. Then we’re already done, and let ${\text{OPT}}^{\prime }=\text{OPT}$.

Case 2

$\text{OPT}$ does not contain $t_{k+1}$ but $G$ does. This implies that $\text{OPT}$ chose some $t_{\ast }$ that comes after $t_{k+1}$ instead of it. This is because we’ve sorted our tasks in order of time. It also implies $t_{\ast }>t_{k+1}$ (takes more time to complete).

Then, let’s construct a new ${\text{OPT}}^{\prime }$ such that ${\text{OPT}}^{\prime }=\text{OPT}-t_{\ast }\cup \{t_{k+1}\}$.

1. The solution is still feasible, because we’ve shown above that $t_{\ast }>t_{k+1}$. If anything, we just gained some time budget back.
2. We exchange one task for another, so the number of tasks remains the same.
3. Now, ${\text{OPT}}^{\prime }$ contains tasks $[\mathrm{1..}k]$ in addition to $k+1$.

By induction, this implies our greedy algorithm is correct and optimal, because we can keep exchanging tasks and building new ${\text{OPT}}^{\prime }$s until we build an ${\text{OPT}}^{\prime }$ such that $G={\text{OPT}}^{\prime }$.

Runtime

Sorting takes $O(n\log n)$ because of the Lower bound for comparison-based sorting algorithms. Iterating through the sorted tasks takes at most $O(n)$. Therefore, total runtime is dominated by our sorting.