2
$\begingroup$

The problem of scheduling lectures in minimum number of classrooms is as follows: Find minimum number of classrooms to schedule all lecture so that no two occur at the same time in the same room.

The common algorithm that I find in books is:

Sort intervals by starting time so that s1 ≤ s2 ≤ ... ≤ sn.
d ← 0 //number of classrooms
for j = 1 to n {
 if (lecture j is compatible with some classroom k)
 schedule lecture j in classroom k
 else
 allocate a new classroom d + 1
 schedule lecture j in classroom d + 1
 d ← d + 1
}

Now, I was thinking of an alternate approach where I sort my lectures by finishing times in ascending order and every time I check if lecture j is compatible with some classroom k and there are multiple classrooms that are compatible with that lecture, I schedule it in the classroom which the last jobs finish time in that classroom is closest to that jobs start time, i.e minimise the time a classroom is empty.

Sort intervals by starting time so that f1 ≤ f2 ≤ ... ≤ fn.
d ← 0 //number of classrooms
for j = 1 to n {
 if (lecture j is compatible with some classroom k)
 schedule lecture j in classroom k which was used last
 else
 allocate a new classroom d + 1
 schedule lecture j in classroom d + 1
 d ← d + 1
}

I would like to know if this approach is right(not necessarily optimal). I have dry run it on a couple of cases, and looks to be okay. If yes, how can I prove its correctness? If not, how can what changes can I make the algorithm work.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.