### 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*