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();
  
  
  
  
  
  
  

Read full article from Interval partitioning problem : Greedy algorithm – Algorithms and Me