Problem

Input:sequence of tasks $t_{1},t_{2},…,t_{n}$ where a $t_{i}∈R_{≥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 $∑_{t∈S}t≤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}≤t_{2}≤⋯≤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},…,t_{m},t_{m+1},…$. In addition, we assume there exists *another* optimal solution $OPT$ such that it contains $t_{1},t_{2},…,t_{k},t_{k+1},…$

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 $OPT$ that is the same as in $G$. This makes proving our algorithm harder, though.

### Lemma

Assume for induction that $OPT$ contains $t_{1},t_{2},…,t_{k}$ from $G$ where $k≤m$. This is our induction hypothesis. We want to prove that there exists a new $OPT_{′}$ such that it is

- feasible (this means we’re still within our constraints)
- $∣OPT∣=∣OPT_{′}∣$
- $OPT_{′}$ contains $t_{1},t_{2},…,t_{k}$ as well as $t_{k+1}$.

We want to show how to construct $OPT_{′}$ from $OPT$. This is an Exchange argument.

#### Case 1

$OPT$ contains $t_{k+1}$. Then we’re already done, and let $OPT_{′}=OPT$.

#### Case 2

$OPT$ does not contain $t_{k+1}$ but $G$ does. This implies that $OPT$ chose some $t_{∗}$ 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_{∗}>t_{k+1}$ (takes more time to complete).

Then, let’s construct a new $OPT_{′}$ such that $OPT_{′}=OPT−t_{∗}∪{t_{k+1}}$.

- The solution is still feasible, because we’ve shown above that $t_{∗}>t_{k+1}$. If anything, we just gained some time budget back.
- We exchange one task for another, so the number of tasks remains the same.
- Now, $OPT_{′}$ contains tasks $[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 $OPT_{′}$s until we build an $OPT_{′}$ such that $G=OPT_{′}$.

## Runtime

Sorting takes $O(ngn)$ 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.