Consider this classic scheduling problem: for a certain lecture room, we are giv
ID: 3881229 • Letter: C
Question
Consider this classic scheduling problem: for a certain lecture room, we are given the start and end times of a set of classes that could be assigned to the room. We wish to create a schedule that maximizes the number of classes offered in the room, so that none of them overlap in time. (The remaining classes are assigned to other rooms.) Note that there may be more than one optimal schedule! A bold 376 classmate claims to have come up with an algorithm that will always produce an optimal schedule, which works as follows:Explanation / Answer
a)Schedule that we will get for above algorithm is, so first sort the data by start time in increasing order
EECS 376 10:30 AM - 12:00 PM
EECS 482x 11:00 AM - 5:00PM
EECS 281 11:30 AM - 1:00 PM
US 371 12:00 PM - 1:00 PM
ASTRO 106 1:00 PM - 2:00 PM
EECS 370 1:30 PM - 3:00 PM
THTREMUS 285 2:00PM - 3:15PM
EARTH 103 2:15PM - 4:15PM
CRUMHORN 400 4:00PM - 4:30PM
HISTORY 220 5:00PM - 6:00PM
Class marked with BOLD is the schedule returned by algorithm mentioned in question.
This is also the optimal schedule as we can observe from below when we sort the classes by ascending order of end time. Schedule part of solution is marked as BOLD.
EECS 376 10:30 AM - 12:00 PM
EECS 281 11:30 AM - 1:00 PM
US 371 12:00 PM - 1:00 PM
ASTRO 106 1:00 PM - 2:00 PM
EECS 370 1:30 PM - 3:00 PM
THTREMUS 285 2:00PM - 3:15PM
EARTH 103 2:15PM - 4:15PM
CRUMHORN 400 4:00PM - 4:30PM
EECS 482x 11:00 AM - 5:00PM
HISTORY 220 5:00PM - 6:00PM
b) Now consider three classes with following time
A 10:00 AM - 5:00 PM
B 11:00AM - 4:00 PM
C 4:00PM - 5:00 PM
So, schedule returned by algorithm mentioned in question is {A} but we can observe that optimal schedule to maximize number of classes is {B,C}
c)
Y = {c1, c2,..........,ck} Output of our algorithm
S = {s1, s2,...........,sm} Optimal schedule
Supporse original problem has only one activity. So, that activity will be selected and and optimal solution has also that activity, so our answer is true for n=1.
Now, lets say finishing time of activity ci is later than si than means that there exits a activity sj where ci==sj and optimal schedule j>i, so there exist a activity j whose finishing time is less than ci but it is not part of solution, but we can add that activity to our solution and sill maintain optimality. So, number is equal to m.
Feel free to reach out if you have any doubts.
Rate if the answer was helpful.
Thanks