Interval Partitioning: Greedy AlgorithmGreedy algorithm. Consider lectures in increasing order of start time: assign lecture to any compatible classroom.Sort intervals by starting time so that s1 s2 ... sn. d 0 number of allocated classrooms for j = 1 to n if (lecture schedule else allocate schedule d d + } { j is compatible with some classroom k) lecture j in classroom k a new classroom d + 1 lecture j in classroom d + 1 1
Implementation. O(n log n). For each classroom k, maintain the finish time of the last job added. Keep the classrooms in a priority queue.