Activity selection and fractional knapsack

Why it exists

Three problems show what a correct greedy algorithm looks like, and one of them shows what happens when the same idea is applied where it does not work. Activity selection (schedule the most non-overlapping jobs) and the fractional knapsack (fill a bag with the most valuable cuttable goods) are solved exactly by a simple rule and a sort; the 0/1 knapsack (items cannot be cut) has the same rule and is not solved by it. GATE asks for the greedy rule, the running time, the selected set for a given instance, and why a plausible rule fails.

Prerequisites

You need the greedy-choice property and the exchange argument (greedy method).

Precise definitions

Activity selection. Activities $1, \ldots, n$, activity $i$ occupying the half-open time interval $[s_i, f_i)$. Two activities are compatible if their intervals do not overlap (one may start exactly when the other finishes). Choose a largest set of mutually compatible activities.

Interval partitioning. The same activities must all be performed, each in a "room"; activities in one room may not overlap. Find the fewest rooms.

Fractional knapsack. A bag holds weight $W$. Item $i$ has weight $w_i$ and value $v_i$, and any fraction $x_i \in [0, 1]$ of an item may be taken (worth $x_i v_i$ and weighing $x_i w_i$). Maximise $\sum x_i v_i$ subject to $\sum x_i w_i \le W$.

0/1 knapsack. The same, but each item is taken completely or not at all ($x_i \in \{0, 1\}$).

Job sequencing with deadlines. $n$ jobs, each needing one unit of time on one machine, job $i$ with a deadline $d_i$ (it must be finished at time $d_i$ or earlier, that is, started in one of the slots $1, \ldots, d_i$) and a profit $p_i$ earned only if it meets its deadline. Choose and order jobs for maximum total profit.

How it works

Activity selection

Rule: sort by finish time; take the first activity; then repeatedly take the next activity that starts no earlier than the finish of the last chosen one. The animation runs the real code on nine activities already sorted by finish time: chosen ones turn green, rejected ones (overlapping the last chosen) fade.

Why earliest finish. Choosing the activity that finishes first leaves the largest possible remaining time. Proof (exchange). Let $a$ be the activity with the earliest finish time and $O$ any optimal solution, with first activity $b$ (in the order of finish). Since $f_a \le f_b$ and everything else in $O$ starts at or after $f_b$, replacing $b$ by $a$ keeps $O$ compatible and of the same size: an optimal solution contains $a$. What remains is the same problem on the activities that start at or after $f_a$ (optimal substructure), so by induction the greedy algorithm is optimal. $\blacksquare$

Other plausible rules fail. Each of them was tried against the exact optimum (found by trying all subsets).

Earliest start first is blocked by one long activity; shortest first can pick a short activity in the middle that overlaps two others; fewest conflicts first also fails (a counterexample with at most eleven activities was found by search). Only earliest finish first is right.

Running time. Sorting by finish time: $\Theta(n \log n)$; the single scan afterwards: $\Theta(n)$. If the activities are already sorted the algorithm is $\Theta(n)$.

Interval partitioning. Sort the activities by start time; give each to any room that is free, opening a new room only when all are busy. The number of rooms equals the maximum number of activities running at the same time (the depth): it is at least that (all of those need different rooms) and the algorithm never opens a room unless that many are running. Time $\Theta(n \log n)$.

Fractional knapsack

Rule: sort the items by value per unit weight, largest first; take whole items while they fit; take a fraction of the first item that does not fit; stop. The animation fills a bag of $30$ units with four items of ratios $8, 6, 5, 3$.

Why it is optimal. Suppose an optimal filling takes some of an item with a lower ratio while a higher-ratio item is not fully taken. Remove a little weight $\varepsilon$ of the lower-ratio item and add the same weight of the higher-ratio one: the weight is unchanged and the value rises by $\varepsilon(r_{\text{high}} - r_{\text{low}}) > 0$. So no optimal solution can contain such a pair, and the greedy filling (which has no such pair) is optimal. The result was also confirmed against an exact linear programming search on random instances. $\blacksquare$

Running time. $\Theta(n \log n)$ for the sort, then $\Theta(n)$. (A selection algorithm for the item at the critical ratio makes it $\Theta(n)$ in all.)

The 0/1 knapsack is different. With items of weight and value $(10, 60), (20, 100), (30, 120)$ and capacity $50$ the ratios are $6, 5, 4$. The same rule takes the first two items (weight $30$, value $160$) and cannot fit the third; but the items $2$ and $3$ together (weight $50$) are worth $220$. The exchange argument fails because a fraction cannot be moved: the leftover capacity is wasted. The 0/1 knapsack has no known polynomial-time greedy algorithm; it is solved by dynamic programming in $\Theta(nW)$ time (dynamic programming problems), which is pseudo-polynomial.

Job sequencing with deadlines

Rule: consider the jobs in order of decreasing profit; put each into the latest free time slot not after its deadline; if there is none, reject it. The table runs it on six jobs.

Why it works. A set of jobs can all be scheduled exactly when, for every $t$, at most $t$ of the jobs have deadline $t$ or earlier (they must all fit into the slots $1, \ldots, t$). Placing a job in the latest free slot keeps the early slots open for jobs with early deadlines; processing by profit makes the accepted set a maximum-profit feasible set (the feasible sets form a matroid, for which greedy by weight is optimal). The result for the table was checked against an exhaustive search over all subsets.

Running time. With a simple search for the latest free slot: $O(n^2)$ (for each job scan down from its deadline). With a disjoint-set structure for free slots: nearly $O(n \log n)$ (the sort dominates).

Worked examples

Cheat box

Traps and GATE patterns

Connections

All three rely on the exchange argument of the greedy method. The 0/1 knapsack and its dynamic programming solution are in dynamic programming problems. The same style of greedy choice, always merge the two smallest, builds Huffman codes.

PYQs

We are given 9 tasks T1, T2... T9. The execution
of each task requires one unit of time. We can
execute one task at a time. Each task Ti has a
profit Pi and a deadline di Profit Pi is earned if the
task is completed before the end of the d th unit of
time.
What is the maximum profit earned?

We are given 9 tasks T1, T2... T9. The execution
of each task requires one unit of time. We can
execute one task at a time. Each task Ti has a
profit Pi and a deadline di Profit Pi is earned if the
task is completed before the end of the d th unit of
time.
Are all tasks completed in the schedule that
gives maximum profit?

Self-check

Revision card

References