Java programming implement the greedy algorithms of Interval Scheduling and Inte
ID: 3726471 • Letter: J
Question
Java programming
implement the greedy algorithms of Interval Scheduling and Interval Partitioning.
Your program should randomly generate certain number n of intervals within a time range [s,t], these three parameters should be received from keyboard. For example, user may want to randomly generate 10 intervals within the time range [5,30], then we know n = 10, s = 5 and t = 30. Your program should have two print outs: one for Interval Scheduling and one for Interval Partitioning. For Interval Scheduling, print out the set of mutually compatible intervals of maximum possible size. While for Interval Partitioning, print out the minimum number of classroom(s) needed to schedule all intervals and the interval(s) in each classroom.
Explanation / Answer
Feel free to post a comment to clarify any queries or doubts
The java code is given as follows:
IntervalPartitioning.java
//IntervalPartitioning
import java.io.*;
import java.util.*;
public class IntervalPartitioning {
ArrayList<Subject> subjects = new ArrayList<Subject>();
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
System.out.print("Enter n : ");
int n = sc.nextInt();
System.out.print("Enter s : ");
int s = sc.nextInt();
System.out.print("Enter t : ");
int t = sc.nextInt();
IntervalPartitioning program = new IntervalPartitioning(n, s, t);
program.intervalPartition();
}
public IntervalPartitioning(int n, int s, int t){
Random rand = new Random();
for(int i = 0; i < n; i++){
// Generate random integers in range s to t
int st = s + rand.nextInt(t - s);
int en = st + rand.nextInt(t - st + 1);
subjects.add(new Subject(st, en));
System.out.println("Added Interval (" + st + ", " + en + ")");
}
}
public void intervalPartition(){
Collections.sort(subjects); //sort subjects/jobs by start time
ArrayList<ClassRoom> allClassRooms = new ArrayList<ClassRoom>(); //list of all rooms & their respective subjects
PriorityQueue<ClassRoom> roomsQueue = new PriorityQueue<ClassRoom>(); //priority Queue holds ClassRooms, ordered by the finish time of the last subject added
ClassRoom firstClassRoom = new ClassRoom(subjects.get(0)); //Create 1st room & add 1st subject (earliest start time)
int roomCount =1; //running total of how many rooms exist
roomsQueue.add(firstClassRoom); //add to queue
allClassRooms.add(firstClassRoom); //add to list of rooms & their contents
for(int i=1; i<subjects.size(); i++){ //loop over all subjects (skipping 1st since already added)
ClassRoom currentClassRoom = roomsQueue.peek(); //get temporary room (earliest finishTime from top of Priority Queue)
Subject currentSubject = subjects.get(i); //current subject from the position in the loop
if(currentSubject.getStartTime() >= currentClassRoom.getLastFinished()){ //Compatible if it starts AFTER or @ the same time as the old subject Finished the last thing finished. MUST BE >= OR JOBS CAN'T BE SCHEDULED RIGHT AFTER EACH OTHER (h after e)
currentClassRoom.addSubject(currentSubject);
roomsQueue.remove();
roomsQueue.add(currentClassRoom); //looks redundant, but actually forces the heap to reorder with a new lastFinished for the same room
}
else{
ClassRoom newClassRoom = new ClassRoom(currentSubject); //create a new room
roomsQueue.add(newClassRoom); //add to queue
allClassRooms.add(newClassRoom); //add new room to the list of all rooms
++roomCount;
}
}
System.out.println("Total rooms needed : " + String.valueOf(roomCount));
}
private class ClassRoom implements Comparable<ClassRoom>{
private LinkedList<Subject> subjects = new LinkedList<Subject>(); //subjects that the room holds
private int lastFinished; //time that the last subject currently in the room finishes
public ClassRoom(Subject subject){addSubject(subject); }
public int getLastFinished(){return lastFinished; }
//Add subject to the room & update lastFinished for the room to match the new subject added
public void addSubject(Subject subject){
subjects.add(subject);
lastFinished = (subject.getFinishTime()); //very important to update, or the room won't update
}
@Override
//Compare based on finish time (for the priority queue)
public int compareTo(ClassRoom otherClassRoom) {return this.getLastFinished() - otherClassRoom.getLastFinished(); }
}
private class Subject implements Comparable<Subject>{
private int startTime;
private int finishTime;
public Subject(int startTime, int finishTime){
this.startTime = startTime;
this.finishTime = finishTime;
}
public int getStartTime(){return startTime; }
public int getFinishTime(){return finishTime; }
@Override
//Compare based on finish time (for initial sorting)
public int compareTo(Subject otherSubject) {
return this.getFinishTime() - otherSubject.getFinishTime();
}
}
}
To keeps things simple, I have make the scheduling in respect to job scheduling.
IntervalScheduling.java
//IntervalScheduling
import java.util.*;
//Basically a struct container type
class Job implements Comparable<Job>{
public int start;
public int finish;
public String name;
public Job(int start, int finish, String name){
this.start=start;
this.finish=finish;
this.name = name;
}
//Compare jobs by finish time
@Override
public int compareTo(Job job) {
return this.finish - job.finish;
}
@Override
public String toString(){
return "Job " + name;
}
}
public class IntervalScheduling {
public static void findOptimalJobScheule(Job[] jobs){
Arrays.sort(jobs); //Sort jobs by finish time
LinkedList<Job> jobsSelected = new LinkedList<Job>();
jobsSelected.add(jobs[0]); //add 1st job
Job lastJobAdded = jobs[0];
for(int i=1; i<jobs.length; i++){
if(jobs[i].start >= lastJobAdded.finish){ //check if job is compatible (starts after or at the time time as the last job finishes)
jobsSelected.add(jobs[i]);
lastJobAdded = jobs[i]; //update for the job that was just added
}
}
System.out.println(" Selected " + jobsSelected.size() + " Jobs: ");
for(Job job : jobsSelected){
System.out.println(job);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter n : ");
int n = sc.nextInt();
System.out.print("Enter s : ");
int s = sc.nextInt();
System.out.print("Enter t : ");
int t = sc.nextInt();
Job[] jobs = new Job[n];
Random rand = new Random();
for(int i = 0; i < n; i++){
// Generate random integers in range s to t
int st = s + rand.nextInt(t - s);
int en = st + rand.nextInt(t - st + 1);
// subjects.add(new Job(st, en));
jobs[i] = new Job(st, en, String.valueOf(i + 1));
System.out.println("Job" + (i + 1) + " Added Interval (" + st + ", " + en + ")");
}
IntervalScheduling.findOptimalJobScheule(jobs);
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.