Last week recap
• Divide & Conquer algorithms:
ØMaster theorem
ØFast integer mul8plica8on in 𝑂 𝑛!”#! $ [Karatsuba]
ØFast matrix mul8plica8on in 𝑂 𝑛!”#! % [Strassen]
ØFinding closest pair of points in R& in 𝑂 𝑛 log 𝑛
ØFinding 𝑘'( smallest element (in par8cular, median) o Randomized algorithm: 𝑂(𝑛) expected 8me
o Determinis8c algorithm: 𝑂(𝑛) worst-case 8me
2021-01-18 CSC373 Winter 2021 – Sam Toueg 1
Greedy Algorithms
2021-01-18 CSC373 Winter 2021 – Sam Toueg 2
Greedy (also known as “Myopic’’) Algorithms:
• Op#miza#on problem: given an input, find an output (a “solu#on’’) that maximizes/minimizes an objec#ve func#on 𝑓 under some constraints
• Greedy algorithm:
ØBuild the solu#on incrementally in stages ØAt each stage, extend the solu#on
oGreedily: in a way that maximizes the immediate benefit for 𝑓
oIrrevocably: no backtracking/regreIng/changing previous decisions • For some problems this gives op#mal solu#ons:
ØE.g. : Prim’s and Kruskal’s Minimum Spanning Tree algorithms
ØProblems we will see this week… • In general, it is not so good:
ØIt op#mizes the “next move’’ without seeing the big picture…
ØHence the name “myopic’’
2021-01-18 CSC373 Winter 2021 – Sam Toueg 3
Greedy Algorithms: Interval Scheduling
2021-01-18 CSC373 Winter 2021 – Sam Toueg 4
Interval Scheduling
Problem
ØInput: 𝑛 intervals (“jobs’’), interval 𝑗 starts at time 𝑠! and finishes at time 𝑓! ØOutput: maximum-size set of intervals that do not overlap
(i.e., that are “compatible’’)
𝑠! 1 𝑓!
𝑠” 2 𝑓”
Compa.ble
Not Compa.ble
𝑠% 3 𝑓%
𝑠# 5 𝑓#
time
𝑠$ 4 𝑓$
2021-01-18
CSC373 Winter 2021 – Sam Toueg 5
Interval Scheduling Algorithms
• Brute force algorithm: try every subset of 𝑛 intervals and take the &
largest set of compa9ble intervals, (i.e., the largest “feasible set’’). 𝑂(2 ) • Greedy algorithm (general scheme):
sort intervals in some order
𝐴 ← ∅ [set of compa2ble intervals] for each interval 𝑖 in sorted order do
if 𝑖 is compa2ble with intervals in 𝐴 then 𝐴 ← 𝐴 ∪ {𝑖}
return 𝐴
• What order gives the biggest feasible set?
Ø Earliest start 2me: increasing order of 𝑠”
Ø Earliest finish 2me: increasing order of 𝑓”
Ø Shortest interval: increasing order of 𝑓” − 𝑠”
Ø Fewest conflicts: increasing order of 𝑐” , where 𝑐” is the number of remaining jobs that conflict with 𝑗
2021-01-18 CSC373 Winter 2021 – Sam Toueg 7
Earliest start .me:
2021-01-18 CSC373 Winter 2021 – Sam Toueg 8
increasing start .me
Earliest finish .me:
2021-01-18 CSC373 Winter 2021 – Sam Toueg 10
increasing finish .me
Shortest interval:
2021-01-18 CSC373 Winter 2021 – Sam Toueg 12
increasing length
Fewest conflicts:
same # of conflicts
increasing
# of conflicts
2021-01-18
CSC373 Winter 2021 – Sam Toueg 14
Interval Scheduling Algorithms
• Greedy algorithm (general scheme):
sort intervals in some order
𝐴←∅
for each interval 𝑖 in sorted order do
if 𝑖 is compa2ble with intervals in 𝐴 then 𝐴 ← 𝐴 ∪ {𝑖}
return 𝐴
• Which order gives an op9mal schedule (i.e., biggest feasible set)?
Ø Earliest start 2me: increasing order of 𝑠”
Ø Earliest finish 2me: increasing order of 𝑓”
Ø Shortest interval: increasing order of 𝑓” − 𝑠”
Ø Fewest conflicts: increasing order of 𝑐” , where 𝑐” is the number of remaining jobs that conflict with 𝑗
2021-01-18 CSC373 Winter 2021 – Sam Toueg 17
Earliest Start Time? No!
Input:
Schedule by Earliest Start Time:
Optimal schedule:
2021-01-18 CSC373 Winter 2021 – Sam Toueg 18
Shortest Interval First? No!
Input:
Schedule by Shortest Interval First:
Optimal schedule:
2021-01-18 CSC373 Winter 2021 – Sam Toueg 20
Fewest Con@licts First? No!
Input:
Schedule by Fewest Conflicts First:
Optimal schedule:
2021-01-18 CSC373 Winter 2021 – Sam Toueg 22
Interval Scheduling Algorithm • Earliest Finish Time (EFT): increasing order of 𝑓” ✅
• Greedy algorithm by Earliest Finish Time (EFT):
sort intervals in order of increasing finish 2me 𝐴←∅
for each interval 𝑖 in sorted order do
if 𝑖 is compa2ble with intervals in 𝐴 then 𝐴 ← 𝐴 ∪ {𝑖}
return 𝐴
IntuiAon: taking the interval that finishes earliest first gives more space to the remaining intervals
How do we prove that this outputs an op.mal schedule?
2021-01-18 CSC373 Winter 2021 – Sam Toueg 24
Interval Scheduling Algorithm
Greedy:
⋯
𝑂𝑃𝑇:
⋯
𝑆:
⋯
Proof of op.mality:
• Suppose for contradic.on that this greedy algorithm is not op.mal
• Say greedy selects intervals 𝑖!, 𝑖”, … , 𝑖’ sorted by increasing finish .me
• Consider an op.mal schedule 𝑂𝑃𝑇: 𝑗!, 𝑗”, … , 𝑗( (also sorted by finish .me)
such that 𝑂𝑃𝑇 matches the greedy schedule for as long as possible Øi.e.,𝑗! =𝑖!,𝑗” =𝑖”,…,𝑗) =𝑖) forthegreatestpossible𝑟
• Consider the schedule 𝑆: 𝑖!, 𝑖”, … , 𝑖), 𝑖)*!, 𝑗)*”, … , 𝑗(
Ø 𝑆 is s.ll feasible (since 𝑓+!”# ≤ 𝑓,!”# all intervals in 𝑆 are compa.ble)
Ø 𝑆 is s.ll op.mal (because it has the same # of intervals 𝑚 as 𝑂𝑃𝑇)
Greedy algorithm with Earliest Finish Time (EFT): sort intervals in order of increasing finish .me
𝐴←∅
for each interval 𝑖 in sorted order do
if 𝑖 is compa.ble with intervals in 𝐴 then 𝐴 ← 𝐴 ∪ {𝑖}
return 𝐴
𝑖!
𝑖!
𝑖”
𝑖”
𝑖”
𝑖)
𝑖)
𝑖)
𝑖)*!
𝑗)*!
𝑖)*!
⋯
⋯
𝑖!
⋯
Ø It matches the greedy schedule for one more interval 2021-01-18 CSC373 Winter 2021 – Sam Toueg
Contradic.on!
25
Interval Scheduling Algorithm
Greedy algorithm with Earliest Finish Time (EFT):
sort intervals in order of increasing finish 2me 𝐴←∅
for each interval 𝑖 in sorted order do
We only need to check if 𝑠+ ≥ finish .me of the last interval added to 𝐴
then
if 𝑖 is compa2ble with intervals in 𝐴
𝐴 ← 𝐴 ∪ {𝑖} return 𝐴
How to implement this algorithm efficiently?
2021-01-18 CSC373 Winter 2021 – Sam Toueg 27
Interval Scheduling Algorithm
Greedy algorithm with Earliest Finish Time (EFT):
sort intervals in order of increasing finish time 𝐴←∅
𝐹 ← −∞
for each interval 𝑖 in sorted order do
if𝑠” ≥𝐹then 𝐴←𝐴∪ 𝑖
𝐹 ← 𝑓#
return 𝐴
Running .me:
𝑂 𝑛log𝑛
2021-01-18
CSC373 Winter 2021 – Sam Toueg 28
Greedy Algorithms Interval Partitioning
2021-01-18 CSC373 Winter 2021 – Sam Toueg 29
Interval Partitioning
• Mo#va#on: given a set of lecture #me intervals (for many courses) • Schedule them into as few classrooms as possible
• This schedule uses 4 classrooms for 10 lecture intervals
2021-01-18 CSC373 Winter 2021 – Sam Toueg 30
Interval Partitioning
• Motivation: given a set of lecture time intervals (for many courses) • Schedule them into as few classrooms as possible
• This schedule uses only 3 classrooms for the same 10 lecture intervals
2021-01-18 CSC373 Winter 2021 – Sam Toueg 31
Interval Partitioning
Problem
ØInput: 𝑛 intervals (“jobs’’), interval 𝑗 starts at Ame 𝑠! and finishes at Ame 𝑓! ØOutput: group intervals into fewest parAAons such that the intervals in
Idea:
• • •
each parAAon are compaAble, i.e., do not overlap.
Doesn’t work!
Find maximum set of compa.ble intervals using the previous greedy EFT algorithm Call it one par..on
Recurse on the remaining intervals
1 𝑓!
𝑠”2𝑓” 𝑠$4𝑓$ 𝑠%3𝑓%
𝑠!
𝑠- 6 𝑓-
𝑠# 5 𝑓#
not optimal!
op.mal
Partition 3
Par..on 2 Par..on 1
.me
2021-01-18 CSC373 Winter 2021 – Sam Toueg
33
Interval Partitioning Algorithms
• Greedy algorithm (general scheme):
sort intervals in some order
for each interval 𝑖 in sorted order do
if 𝑖 is compa2ble with some exis2ng par22on 𝐴 then 𝐴 ← 𝐴 ∪ {𝑖}
else
insert 𝑖 into a new par22on
return all par22ons
• Which order gives an op9mal scheduling, i.e., one with fewest par99ons?
Ø Earliest start 2me: increasing order of 𝑠”
Ø Earliest finish 2me: increasing order of 𝑓”
Ø Shortest interval: increasing order of 𝑓” − 𝑠”
Ø Fewest conflicts: increasing order of 𝑐” , where 𝑐” is the number of remaining jobs that conflict with 𝑗
2021-01-18 CSC373 Winter 2021 – Sam Toueg 36
Earliest Finish Time ? No!
Input:
Schedule by Earliest Finish Time:
.me
Op.mal schedule:
1 2 3
1 2
2021-01-18
CSC373 Winter 2021 – Sam Toueg
37
Shortest Interval First? No!
Input:
Schedule by Shortest Interval First:
.me
Op.mal schedule:
1 2 3
1 2
2021-01-18
CSC373 Winter 2021 – Sam Toueg
38
Fewest Conflicts First? No!
Input:
Schedule by Fewest Conflicts First:
.me
Optimal schedule:
1 2 3
1 2
2021-01-18
CSC373 Winter 2021 – Sam Toueg
39
Interval Partitioning Algorithms • Earliest Start Time (EST): increasing order of 𝑠” ✅
• Greedy algorithm with Earliest Start Time (EST):
sort intervals in order of increasing start 2me for each interval 𝑖 in sorted order do
if 𝑖 is compa2ble with some exis2ng par22on 𝐴 then 𝐴 ← 𝐴 ∪ {𝑖}
else
insert 𝑖 into a new par22on
return all par22ons
How do we prove that this outputs an optimal schedule?
depth =2
depth=1 depth=3
max depth = 3
.me
2021-01-18 CSC373 Winter 2021 – Sam Toueg
40
Interval Partitioning Algorithms
Greedy algorithm with Earliest Start Time (EST): sort intervals in order of increasing start time for each interval 𝑖 in sorted order do
if 𝑖 is compatible with some existing partition 𝐴 then
𝐴 ← 𝐴 ∪ {𝑖}
else
return all partitions
insert 𝑖 into a new partition
How do we prove that this outputs op.mal schedule?
depth =2
depth=1 depth=3
max depth = 3
.me
The depth at 2me 𝑡 is the number of intervals that contain 2me 𝑡 The maximum depth 𝑑$%& is the maximum depth over all 2mes
Clearly: # par22ons needed ≥ 𝑑$%&
We now show that this algorithm creates only 𝑑$%& par22ons! So it is op2mal. 2021-01-18 CSC373 Winter 2021 – Sam Toueg 41
𝑑=3
Par33on 3 Par33on 2
Par33on 1
𝑑(./ ≥depth=𝑑=3𝑗
Interval Partitioning Algorithms
Proof of op.mality:
• Let 𝑑 = # par22ons created by this greedy algorithm
• Par22on 𝑑 was created because there was an interval 𝑗 that overlaps with
some previously scheduled interval in each of 𝑑 − 1 other par22ons
• Since we sorted by start 0me, all these 𝑑 − 1 intervals start at/before 𝑠”
• Since interval 𝑗 overlaps with them, all these 𝑑 − 1 intervals finish aPer 𝑠”
• So at 2me 𝑠”, we have 𝑑 overlapping intervals
• Thus 𝑑(./ ≥ 𝑑
• So all feasible schedules must have 𝑑#$% ≥ 𝑑 par22ons
• Hence algo is op2mal!
𝑠,
.me
2021-01-18 CSC373 Winter 2021 – Sam Toueg 42
𝑑=3
Par33on 3 Par33on 2
Par33on 1
depth = 2
𝑗
Interval Partitioning Algorithms
Proof of op.mality:
• Let 𝑑 = # par22ons created by this greedy algorithm
• Par22on 𝑑 was created because there was an interval 𝑗 that overlaps with
some previously scheduled interval in each of 𝑑 − 1 other par22ons
• Since we sorted by start 0me, all these 𝑑 − 1 intervals start at/before 𝑠
𝑠,
.me
❌”
• Since interval 𝑗 overlaps with them, all these 𝑑 − 1 intervals finish aPer 𝑠”
• So at 2me 𝑠 , we have 𝑑 overlapping intervals ❌”
• Thus𝑑 ≥𝑑
❌
(./
So all feasible schedules must have 𝑑
≥ 𝑑 par22ons
•
❌
Hence algo is op2mal!
#$%
•
❌
What if intervals are not sorted by start .me?
2021-01-18 CSC373 Winter 2021 – Sam Toueg 43
Interval Partitioning Algorithms
Greedy algorithm with Earliest Start Time (EST): sort intervals in order of increasing start Ame for each interval 𝑖 in sorted order do
𝐴 ← 𝐴 ∪ {𝑖}
else
insert 𝑖 into a new parAAon
return all parAAons
How to implement it efficiently?
• Store parAAons in a priority queue
Ø key = finish 2me of the last interval inserted in the par22on
Key step!
if 𝑖 is compaAble with some exisAng parAAon 𝐴 then
2021-01-18 CSC373 Winter 2021 – Sam Toueg
44
Interval Partitioning Algorithms
• Store each parAAon as a tuple [key, intervals] in a min heap Ø key = finish 2me of the last interval inserted in the par22on Ø intervals = set of intervals in the par22on
Greedy algorithm with Earliest Start Time (EST):
create an empty min heap 𝐻
sort all intervals in order of increasing start Ame for each interval 𝑖 in sorted order do
𝑃 ←𝐻.Min()
if𝑃=Nullor𝑠” <𝑃.keythen
create a new parAAon 𝐴 with 𝐴.key =𝑓", 𝐴.intervals ={𝑖} 𝐻.Insert(𝐴)
else𝐴 ← 𝐻.Extract_Min() 𝐴.intervals ← 𝐴.intervals ∪ {𝑖} 𝐴.key ← 𝑓"
𝐻.Insert(𝐴)
return 𝐻
2021-01-18 CSC373 Winter 2021 - Sam Toueg
𝑂(𝑛) heap opera.ons 𝑂(𝑛 log 𝑛) .me
45