Solution is incorrect for problem 15.22 Scheduling Tutors

[GoogleCodeExporter]

Given the following lesson requests:

9 - 9:30
9:30 - 10
10 - 10:30
10:30- 11
11 - 11:30
11 - 11:30
-----------------
The proposed greedy algorithm will resolve with 3 tutors, but these requests 
can be resolved with 2 tutors only.

Another example that won't work: (need 3 instead of 4)
9 - 9:30
9 - 9:30
9:30 - 10
9:30 - 10
10 - 10:30
10 - 10:30
10:30- 11
10:30- 11
11 - 11:30
11 - 11:30
12 - 12:30
12:30 - 1

=============

One solution would be to greedily assign tutors to current most overlapping 
lesson requests and update all overlap counts after each assignment. 

Original issue reported on code.google.com by JouTingL...@gmail.com on 16 Sep 2013 at 3:09

[GoogleCodeExporter]

Hey Jou-Ting,

Thanks for your inquiry. I checked that algorithm in our book but don't see any 
problem of it. Let me explain how our algorithm works as follows:

I will use 'A', 'B', .., as the notations of tutors. Remember that in our 
problem we have limitation that every tutor must stop tutoring for the day at 
most two hours after starting. For your first example,
A 9- 9:30
A 9:30 - 10
A 10 - 10:30
A 10:30 - 11 (A must stop since he/she has tutored for two hours today.)
B 11 - 11:30
C 11 - 11:30

As a result, for the first example, you need three tutors.

For your second example,
A 9 - 9:30
B 9 - 9:30
A 9:30 - 10
B 9:30 - 10
A 10 - 10:30
B 10 - 10:30
A 10:30 - 11 (A must stop since he/she has tutored for two hours today.)
B 10:30 - 11 (B must stop since he/she has tutored for two hours today.)
C 11 - 11:30
D 11 - 11:30
C 12 - 12:30
C 12:30 - 1

As a result, you need four tutors. The strategy I used here is exactly greedy 
method mentioned in the book (i.e., as soon as there is a request that cannot 
be handled by the previously assigned tutors, we choose a new tutor.)

Feel free to ask questions if you have any problem.

Original comment by TsungHsi...@gmail.com on 16 Sep 2013 at 7:12

[GoogleCodeExporter]

Original comment by TsungHsi...@gmail.com on 16 Sep 2013 at 11:11

• Changed state: Invalid