## Wednesday, June 8, 2016

### Interval partitioning problem : Greedy algorithm – Algorithms and Me

Interval partitioning problem : Greedy algorithm – Algorithms and Me
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.

```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.```
• ```

from PriorityQueue import PriorityQueue

from Classroom import Classroom

jobs = [(1, 930, 1100), (2, 930, 1300), (3, 930, 1100), (5, 1100, 1400),(4, 1130, 1300), (6, 1330, 1500), (7, 1330, 1500), (8,1430,1700), (9, 1530, 1700), (10, 1530, 1700)]

def find_num_classrooms():

num_classrooms = 0;

priority_queue = PriorityQueue()

for job in jobs:

# we have job here, now pop the classroom with least finishing time

classroom = priority_queue.pop();

if(classroom == None) :

#allocate a new class

num_classrooms+= 1;

priority_queue.push(Classroom(num_classrooms,job[2]),job[2]);

else:

#check if finish time of current classroom is

#less than start time of this lecture

if(classroom.finish_time  <= job[1]):

classroom.finish_time = job[2]

priority_queue.push(classroom,job[2])

else:

num_classrooms+= 1;

#Since last classroom needs to be compared again, push it back

priority_queue.push(classroom,job[2])

#Push the new classroom in list

priority_queue.push(Classroom(num_classrooms,job[2]),job[2])

return  num_classrooms

print "Number of classrooms required: " +  find_num_classrooms();

```