Essays /

15 H Essay

Essay preview

15-2

Algorithms – Greedy Algorithms

“Greed … is good. Greed is right.
Greed works.”
“Wall Street”

Greedy Algorithms

Data Structures and Algorithms
Andrei Bulatov

15-3

Algorithms – Greedy Algorithms

15-4

Algorithms – Greedy Algorithms

Interval Scheduling

Greedy Algorithm

Consider the following problem (Interval Scheduling)
There is a group of proposed talks to be given. We want to
schedule as many talks as possible in the main lecture room. Let t1 , t 2 ,K, t m be the talks, talk t j begins at time b j and ends at time e j . (No two lectures can proceed at the same time, but a lecture can begin at the same time another one ends.) We assume that e1 ≤ e2 ≤ K ≤ em.

Greedy algorithm:
At every step choose a talk with the earliest ending time among all those talks that begin after all talks already scheduled end.

t4

t4
t7

t3

t1

t1
t8

t5

t2

t8

t5

t2

t6

t6
9:00

9:00

t7

t3

10:00

11:00

10:00

11:00

12:00

12:00

Algorithms – Greedy Algorithms

15-5

Algorithms – Greedy Algorithms

Greedy Algorithm (cntd)

Optimality

Input: Set R
Output: Set

Proof
By induction on n we prove that if the greedy algorithm schedules n talks, then it is not possible to schedule more than n talks. Basis step. Suppose that the greedy algorithm has scheduled only one talk, t1. This means that every other talk starts before e1 , and ends after e1. Hence, at time e1 each of the remaining talks needs to use the lecture hall. No two talks can be scheduled because of that.

Inductive step. Suppose that if the greedy algorithm schedules k talks, it is not possible to schedule more than k talks.
We prove that if the algorithm schedules k + 1 talks then this is the optimal number.

of proposed talks
A of talks scheduled in the main lecture

hall
set A:=∅
while R≠∅
choose a talk i∈R that has the smallest finishing time
set A:=A∪{i}
delete all talks from R that are not compatible with
i
endw...

Read more

Keywords

-10 -11 -12 -13 -14 -15 -16 -17 -18 -2 -20 -21 -22 -23 -24 -25 -26 -27 -28 -29 -3 -30 -4 -5 -6 -7 -8 -9 0 00 1 10 11 12 15 2 3 4 5 9 ad add ahead algorithm alreadi also alway among analysi andrei anoth arc argument associ assum attempt b base basi begin belong build bulatov c call case ce chang check choic choos claim clear cntd compat compon connect consid construct contain cost cut cycl d data defin deg delet denot design differ digraph dijkstra direct distanc diy doesn e e.1 e1 e2 earliest edg ei em end endwhil everi exampl exchang explor f find finish first follow form g generat give given good graph greed greedi group h hall heap henc hold howev hypothesi implement improv includ inde induct input instanc instead interv iter j k kruskal least leav lectur lemma len length let lighter lightest local log loop m main mani mean method min minim minimum mn mn3 moment must n natur need next node nonempti note null number o object obtain one optim output p path pick point posit possibl predecessor prim prioriti problem proceed produc proof proper properti propos prove provid pu pv px q qed question queue r reachabl recal reduc remain replac requir return right room run s-t-shortest say schedul see select sens set shortest show sinc singl small smaller smallest solut sound sourc span start stay step still store straightforward street structur subset suppos t1 t2 t3 t4 t5 t6 t7 t8 take talk theorem therefor ti time total tree tu two u undirect uniqu unreach updat use v valu vertex vertic w wall want weight work x y