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.
Read full article from 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();
Read full article from Interval partitioning problem : Greedy algorithm – Algorithms and Me