greedy scheduling
Concept
Interval scheduling
- given a set of intervals
- return the maximum set of disjoint(non-intersecting) intervals
- we want the largest number of non-clashing intervals
bad
- min start - counter ex. one long one
- min (finish - start) - counter ex.
- min no. of overlaps with other intervals
good
- min finish
ScheduleIntervals([s_1,f_1] ... [s_n,f_n])
sort intervals by finish time (f_i <= f_{i+1})
S <- empty set
for i=1...n do
if [s_i,f_i] does not intersect any other interval in S
insert interval i into S
return S
O(n log n)
Interval coloring
- give “colors” to each interval
- minimize the number of colors with overlapping intervals having different colors
ColorIntervals([s1,f1] ... [sn,fn])
sort intervals by start time (si <= si+1)
Busy = empty min-heap
Free = empty min-heap
q = 0
for each interval i:
while Busy is not empty and minimumFinish(Busy) < start[i]:
move that room from Busy to Free
if Free is empty:
q = q + 1
room = q
else:
room = ExtractMin(Free)
color[i] = room
insert (finish[i], room) into Busy
return (color, q)
O(n log n)
Minimum total completion time
-
order to complete a set of jobs to reduce the total completion time
-
related to SJF
-
exchange argument
-
suppose b > a
-
… | b | a | …
-
r r+b r+b+a -
total completion time = T’ + r + b
-
vs
-
… | a | b | …
-
r r+a r+a+b -
total completion time = T’ + r + a
ShortestFirst(j_1 ... j_2):
jobs = sort jobs by nondecreasing duration (j_i <= j_{i+1})
return jobs
Adjacent exchange