Question

Suppose you have n classes that you want to schedule in rooms. Each class has a fixed time interval at which it is offered, and classes whose times overlap cannot be scheduled in the same room. There are enough rooms to schedule all the classes. Design a O(n log n) time algorithm to find an assignment of classes to rooms that minimizes the total number of rooms used.

Answer 1

Function schedule( list of tuple of start and end times, class available)

class_list = create list of class from class available

for items in time_list:

if items is not same range as time_list[-1]:

newdict[items] = class_list[0]

print class time: class venue

elif items is same range as time_list[-1]:

used_class = newdict.values

index = class_list.index(used_class[-1])

new_dict[items] = class_list[index + 1 ]

print class time: class venue

Step-by-step explanation:

The algorithm above describe a program with a time complexity of O(n log n). The function defined accepts two parameters, an array of start and end time tuple and the number of class available for use. The algorithm uses a quick sort to compare the time interval of the items in the list and schedule new classes for classes that overlaps with others.