Problem

Input: sequence of tasks where a represents the amount of time it takes to complete it. We also have a time budget .

Output: maximize the number of tasks completed within time .

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 such that given a set of tasks, . We want to maximize .
  • Constraint: given the set of tasks , it must be true that .

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 . Then, up until a task , we can say that the total time taken must be , which must be less than .

Let be the solution from our greedy algorithm, which consists of tasks . In addition, we assume there exists another optimal solution such that it contains

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

Lemma

Assume for induction that contains from where . This is our induction hypothesis. We want to prove that there exists a new such that it is

  1. feasible (this means we’re still within our constraints)
  2. contains as well as .

We want to show how to construct from . This is an Exchange argument.

Case 1

contains . Then we’re already done, and let .

Case 2

does not contain but does. This implies that chose some that comes after instead of it. This is because we’ve sorted our tasks in order of time. It also implies (takes more time to complete).

Then, let’s construct a new such that .

  1. The solution is still feasible, because we’ve shown above that . 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, contains tasks in addition to .

By induction, this implies our greedy algorithm is correct and optimal, because we can keep exchanging tasks and building new s until we build an such that .

Runtime

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