Interval partitioning problem
In continuation of greedy algorithm problem, (earlier we discussed : even scheduling and coin change problems) we will discuss another problem today. Problem is known as interval partitioning problem and it goes like : There are n lectures to be schedules and there are certain classrooms. Each lecture has a start time si and finish time fi. Task is to schedule all lectures in minimum number of classes and there cannot be more than one lecture in a classroom at a given time. For example, below partitioning needs us to have 4 classes for scheduling 9 lectures from 9:30 AM to 5:00 PM.
10 lectures can also be scheduled using three classrooms as shown below.
So, second solution optimizes the output.
Another variant of interval partitioning problem is : You want to schedule jobs on a computer. Requests take the form (si , fi) meaning a job that runs from time si to time fi. You get many such requests, and you want to process as many as possible, but the computer can only work on one job at a time.
By hit and trial method we can come to conclusion the best strategy to follow is to pick lecture based on earliest start time. So, here goes the algorithm : At any given time, pick up a lecture with least start time and yet not scheduled and then assign it to first available class. Will it work? Sure it does.
Interval partitioning problem: greedy algorithm
1. Sort all lectures based on start time in ascending order. 2. Number of initial classrooms = 0 3. While lecture to be scheduled: 3.1 Take first lecture yet not scheduled, 3.2 If there a already a class available for lecture's start time Assign lecture to the class. 3.3 If not, then allocate a new classroom number of classroom = number of classroom + 1 4. Return number of classrooms.
Before jumping into the code, let’s discuss some data structures which we can use to implement this algorithm.
Understand that we have to find a compatible classroom for a lecture. There are many classrooms, we need to check if the finish time of lecture in that classroom is less than start time of new lecture. If yes , then classroom is compatible, if there is no such class, allocate a new class. If we store our allocated classrooms in such a way that it always gives classroom with least finish time of last lecture scheduled there, we can safely say that if this classroom is not compatible, none of the others will be.(Why?) Every time we assign a lecture to a classroom, sort the list of classroom, so that first classroom is with least finish time.
Think a bit hard, what I explained above is typical use case of min heap. Every time finish time of last lecture changes for a classroom, heap is readjusted and root gives us classroom with min finish time. Complexity (n log n). In other words, we can say we will be using priority queue keyed on finish time of last lecture.
- To determine whether lecture j is compatible with some classroom, compare sj to key of min classroom k in priority queue.
- When a lecture is added to a classroom, increase key of classroom k to fj.
Well know we have algorithm and data structure to implement in, so let’s code it.
PrioritityQueue implementation is given below:
Classroom class is implemented as follows.
This algorithm takes overall time of O(n log n) dominated by the sorting of jobs on start time. Total number of priority queue operations is O(n) as we have only n lectures to schedule and for each lecture we have push and pop operation.
Please share your views and suggestions in comments and feel free to share and spread the word.Thanks!