Implement the interval partitioning algorithm discussed in class and run it agai
ID: 3794183 • Letter: I
Question
Implement the interval partitioning algorithm discussed in class and run it against the problem instance shown below. In this problem instance, there are 10 jobs, labeled a through j, with the start time and end time shown on the timeline at the bottom. (This illustration is from the lecture slide.) The program should output the room allocated each time a new job is booked during the run and the list of all jobs allocated to each room after the run. Feel free to use Java priority queue class or write your own. Name your program Intv 1 Part.java. Submit all source codes as one program file and submit a printout of the run output as a text file. Program codes should be working and neatly organized and well commented. There will be no point given to codes that are not working, and many points will be deducted for codes hard to read.Explanation / Answer
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();
import heapq
# This is our priority queue implementation
class PriorityQueue:
def __init__(self):
self._queue = []
self._index = 0
def push(self, item, priority):
heapq.heappush(self._queue, (priority, self._index, item))
self._index += 1
def pop(self):
if(self._index == 0):
return None
return heapq.heappop(self._queue)[-1];