CSCC73 - Greedy Algorithms - Tutorial

NOTE: reposting solutions on a public domain is an academic offence and will be treated as such.

1. Consider a road trip from Toronto to Vancouver. There are n electric charging stations at certain
locations along the route. You can assume that you are given the distance between each charging
station. Ie., if x1 is the closest charging station, it might have value 100km. If x2 is the next charging
station it may have value 300km which means it is 400km away from the starting point.

Your car has a specific km range r.

Goal: make as few recharging stops as possible.

Give a greedy algorithm defining appropriate notation and prove the correctness of your algorithm.
Assume the charging stations x1 . . . xn are sorted in order of increasing distance from your current
location. Let the greedy choice be select xi such that i is as large as possible such that your car has
the range to make it there. I.e., always go to the furthest station within range. If stopping at station
xi , remove stations x1 . . . xi from the set of stations and recurse with range reset to r.

Correctness: use an exchange argument. Can phrase as a contradiction argument. Suppose G not
optimal. Consider the set of stations selected by the greedy algorithm G = g0 , g1 , . . . gk and a ”most
similar” optimal solution O = f0 , f1 , . . . , fj where O and G agree for gi = fi , i = 0 . . . m and m is
maximum over all optimal solutions.

Consider station gm+1 6= fm+1 . Notice that by the greedy choice, the car has range to reach gm+1
and that gm+1 ≥ fm+1 . This means that we can swap gm+1 and fm+1 since the new distance between
stations is decreased, ie.
fm+2 − fm+1 ≥ fm+2 − gm+1
however this contradicts that O is the most similar optimal solution to G. Therefore G is optimal.

2. Consider the following interval covering problem.

Input: A set of intervals I = {I1 , . . . , In } where each interval Ij = [sj , fj ].
Output: A cover I 0 ⊆ I such that for all I ∈ I, there exists I 0 ∈ I 0 such that I 0 ∩ I 6= ∅.

(a) Show that the “most obvious greedy algorithm” (i.e.. always choosing that interval which overlaps
the largest number of currently uncovered intervals) does not produce a minimal size cover.
Solution:

A B C

D E
Notice that the obvious greedy algorithm picks B first which then results in the selection of A and
C rather than just D and E.

1
(b) Describe an optimal greedy algorithm for the interval covering problem. Provide a proof that
your algorithm always produces an optimal cover.
Solution:
Consider making two lists of the intervals. For the first list, sort the intervals by increasing finish
time. Think of this list as keeping track of the intervals covered so far. Make the second list the
intervals sorted by increasing start time. Think of the second list as the set of candidates to cover
the intervals in the first list.

Consider the interval with earliest finish time f1 . We want to select the interval with si < f1
and maximum possible f value. To find this interval, walk the second list keeping track of the
interval with latest finish time but with start time before f1 . Notice you only need to walk all
those intervals with start time before f1 . Let i be this interval with start time si and finish time fi .

Delete all those intervals with start time < fi in the first list (ie., covered by (si , fi ) ). We can see
this by noticing that since (si , fi ) overlaps the interval that finishes earliest, every other interval
that starts before fi must finish after f1 and therefore finishes after si so is covered.

Then delete all those intervals j with sj < f1 and fj < fi . These intervals cannot cover any
interval to the right of red since they end before red ends.

Recurse on the subproblem.

Example:

List 1: green, yellow, orange, pink, red, black, light blue, purple, blue

List 2: yellow, orange, green, pink, red, black, light blue, purple, blue

Greedy choice: find interval finishing last but starting before green ends.. Pick
red. Delete from list 1, those intervals starting before red ends.

List 1': blue

Delete from list 2 those intervals that start before green ends and finish before
red ends. Ie., they cannot cover any interval to the right of red.

List 2': red, black, light blue, purple, blue

Proof :
The greedy stays ahead approach works well here. Notice that the greedy algorithm selects the
interval that covers the the interval that finishes earliest and reaches furthest. Suppose an optimal

2
solution does NOT include the greedy choice. We will show that we can swap an interval out and
replace it with the greedy choice.
• By definition of the greedy algorithm, (s1 , f1 ) is the interval that finishes first (green).
• The greedy algorithm selects (si , fi ) such that si < f1 and fi > fj for all j such that sj < f1 .
• Since (s1 , f1 ) finishes first, every interval that intersects it, must start before f1 and finish
after f1 .
• Suppose an optimal solution does not include (si , fi ) but rather has interval (sk , fk ) that
intersects (s1 , f1 ).
• Since (sk , fk ) intersects (s1 , f1 ), sk < f1 and f1 < fk < fi by definition of the greedy choice.
• Every interval covered by (sk , fk ) must finish after f1 . It either starts or finishes between f1
and fk .
• Since fk < fi , all these intervals would also start or finish between f1 and fi and further
(si , fi ) may intersect intervals where fk < sj < fi . Therefore replacing (sk , fk ) with (si , fi )
in any optimal solution is acceptable.
Complexity: Once again the complexity is bounded by sorting. Sorting takes O(n log n) time.
Picking the greedy interval requires walking part of the list of intervals. Notice that each interval
is visited only once, hence this portion of the algorithm is linear. Therefore, the complexity is
O(n log n).