Interval partitioning problem : Greedy algorithm

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.

Interval partitioning problem

10 lectures can also be scheduled using three classrooms as shown below.

interval partition problem example

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.

First thing to note about interval partitioning problem is that we have to minimize something, in this case, number of classrooms. What template this problem fits into? Greedy may be? Yes, let’s try our greedy strategy, but to apply it, we need some parameter on which particular lecture will be selected for a classroom. There are some parameters for each lecture like start time, end time, shortest lecture, or lecture with minimum number of conflicts with others. Problem statement is bit similar to event scheduling problem but here optimization is done on resource where processing can be done simultaneously on different resources, where as in event scheduling, one one event can be processed at a time as we had only one resource.

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.

Reference :

Please share your views and suggestions in comments and feel free to share and spread the word.Thanks!