Question

Suppose you have a set of classes to schedule among a large number of lecture halls, where any class can class place in any lecture hall. Each class cj has a start time sj and finish time fj. We wish to schedule all classes using as few lecture halls as possible. Verbally describe an efficient greedy algorithm to determine which class should use which lecture hall at any given time. What is the running time of your algorithm?

Answer 1

This problem is an example of the activity-selection problem. We assume that the activities are mutually compatible. In this, we have to select the maximum subset of all the mutually compatible activities. The best greedy approach is to select the activities using the finishing time. Iterate through all the activities, if the starting time of the $c_{j+1}$ activity is more than the starting time of $c_{j}$ activity, then include that activity in the schedule set.

So, the algorithm would be like

SCHEDULE_HALLS(s , f)

BEGIN

                // include the first activity in the schedule set

                A = {c1}

                i = 1

                for j = 2 to s.length()

                BEGIN

                                If s[j] >= f[i]

                                BEGIN

                                                // add the j th activity in the schedule set

                                                A = A U { cj }

                                                i = j

                                END

               

                END

                Return A

END

The algorithm would run only n times where n is the number of classes to schedule.

SO,

Time Complexity = O(n)