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.
