Interval Scheduling
A public auditorium is open from 6 AM to 9 PM for organizations to host their events. Each organization submits start and finish times for their event, which are displayed below:
Since events cannot be hosted concurrently, not all of the proposals can be accepted. To host the largest number of events, which of the following selection criteria should be used?
Note:
- The rows are merely used to organize the information in a clear manner. It does not imply that the entire row has to be selected.
- If two events share a common point on the time axis, then both proposals cannot be accepted at the same time.
- In the case that two or more events have the same number of overlap, finish time, or duration, then ties are broken arbitrarily.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Well I found it easy to solve the problem, but I did not understand what was meant by the three answer choices, There must be a clearer way to express what you meant by each of them.
Log in to reply
I apologize for not being clear. Could you help frame the question in a better way?
Hi Beth, what do you (or anyone else) feel is confusing about the answer choices? This will allow us to improve the question for others.
For example, are you looking for "Select in increasing order of their finish time - Pick the one that would finish first, without overlapping with any other selected event?"
The question didnt state that overlapped events are placed on different rows, so why pq and qr overlaps but not bc cd de
Log in to reply
I've made the assumption that if events are next to each other, then they overlap if they're on different rows, and don't if they're on the same row. Without this assumption, interpretation becomes very difficult- how did you view it?
"Select in increasing order of their finish time" is indeed the best strategy for the events given in this problem. Is it always the optimal strategy for any set of events?
Log in to reply
Actually it is! Proving this is not very hard, but it is rather surprising that such a simple idea always works.
The nice thing is that regardless of what the events are, selecting in increasing order of their finish time always gives the optimal result. This is not hard to prove but r
I came across this in our algorithm design class.
Log in to reply
Can you sketch out a proof of that as a separate solution?
It looks like your comment was cut off.
It is impossible to select the events in increasing time of finishing since, for instance M finishes before C, but can't be chosen. So the problem needs to be phrased a little differently. The list of events in increasing order of finish time is P Q R =A, B, M =N = O, C, L, D I= J= K, E, F, H, G. Looking at the middle block the finishing times in order are B, M, C, L, D, I, and E (looking just at the first two rows) but this sequence is impossible since B and M overlap, etc. If you have a rule that an event is knocked off the list if it would displace an event that has already started then in the first block, we see that A starts before P, so P couldn't get in if A is already there, and neither could Q and R.. So it can't be that the one that would start first can block an event that has an earlier start time. If ,M L, and I were shifted slightly to the left and another event added on just beyond event I, four events could fit on the second row and there would be another way to have 9 events. It would be possible that there is more than one choice that maximizes the number of events. Can you state the exact theorem? How does it handle overlapping events?
Log in to reply
You are right, when we sort the list of events in increasing order of the finish times, it might be possible that two consecutive entries in the list overlap. This issue can be easily fixed by removing the events that are overlapping with the chosen event.
Once the list is sorted in order of increasing finish times,
P Q R, A, B, M =N = O, C, L, D I= J= K, E, F, H, G
the optimal algorithm would be to select the first element in the list. Next, delete all elements that overlap with it since they can't be chosen and select the next element in the list. In this case, we choose P, it overlaps with A so we delete A. Next we select Q, then R and then B. Since M, N, O overlap with B, we delete them. Next on the list is C, it overlaps with L so L is deleted. Next we select D, delete I, J, K, select E, then select F, delete H and select G.
Finally we have chosen P, Q, R, B, C, D, E, F, G.
Although there is only one optimal solution in this case, there may exist some configuration of events for which there could be multiple ways to choose the maximum number of events.
It is clear that A overlaps P,Q, and R, and that B,C,D,E,F and G overlap H thru O. It is NOT clear that P overlaps Q or that Q overlaps R. When you zoom in on the image above you can clearly see that there is a distance of several pixels between the end of P and the Start of Q as well as the end of Q and the start of R. Also your three choices are not at all easy to discern. A,B, and E all have the same number of overlaps. Likewise C and D also have the same number of overlaps. So which is 1st, 2nd, 3rd, 4th or 5th in increasing order of overlaps? You have the same problem on finishing times. A & R end at the same time as does I,J,K and M,N,O. Regarding duration A and H clearly have different durations. F & G seem to also have the same durations. And I,J,K,L,M,N,O,P,Q,R and B,C,D, and E also appear to have the same durations. So what is the increasing order of their duration? All in All I do not believe this is a Brilliant question.
Log in to reply
Hi Ed
Absolutely, I initially reasoned that P, Q and R did not overlap, based on the spacing, but if this is so, why did the author not just include them all on the same line together?
About the second point: A, B and E have the same number of overlaps. I think the point is here that we have picked P, R and L (which have 2 overlaps), so that disqualifies A, C or D from being chosen.
Again, we've picked P because it is the first event to finish, so we CANNOT pick A.
Regarding duration, we've picked the combination of shortest events that would maximise the total number of events chosen. This turns out to be 7, which is insufficient.
Certainly many elements of this question are confusing, @Agnishom Chattopadhyay would you mind to clarify?
@Dan Ley @Mehdi K. The rows do not mean anything. I have edited the problem to clarify this.
Log in to reply
Thanks, has the edit corrected things?:)
Log in to reply
Yes, I have clarified that
- The rows do not have any meaning
- When there are ties in the ordering, they can be broken arbitrarily.
How do p and q or q and r overlap? Each ends as the other is about to bwgin?
Log in to reply
They are on separate lines, so I judged that they overlapped. If they don't overlap, P, Q and R can be selected by all criteria- it won't change the final answer.
Log in to reply
"They are on separate lines, so I judged that they overlapped", using this logic, A will overlap with {P, Q, R, M, N , O, L, I, ...}
The number of overlaps are seen below:
Selecting in increasing order, we choose "
1
", "
1
" and
1
" in the first slot, then "
3
", "
2
", "
3
" in the second slot, and finally "
1
" and "
1
" in the last slot. This gives
3
+
3
+
2
=
8
events
.
If we select in order of duration, we end up choosing the events shown below:
This again gives us
8
events
.
Finally, if we select in increasing order of their finish time:
Event
P
finishes first, so that must be chosen. Next, Event
Q
. It appears that Event
A
and Event
R
finish at the same time, and since Event
A
is concurrent with Event
P
, Event
R
must be chosen. It follows that we must choose Event
B
, then
C
, then
D
,then
E
, then
F
, and then
G
. This gives a total of
9
events
, so we should
select in increasing order of their finish time
.