Question

Implement a greedy strategy in JAVA which takes in a list of job object ( each job object consist of Job id (integer) , startTime (float) and endTime(float)) and outputs a list of non-conflicting jobs according to their start time. (Implement the given method provided in the code).

Example of Input:

id startTime endTime

1 4 7

2 3 5

3 7 9

CODE

import java.util.Scanner;

import java.util.List;

import java.util.ArrayList;

import java.io.InputStream;

public class JobScheduling {

public static final Strategy chosen = Strategy.EARLIEST_START;

/**

* Returns a non-conflicting selection of jobs from the input list,

* chosen according to the earliest starting time strategy, i.e. jobs are

* considered in order of earliest to latest starting time, each

* job is included if and only if it doesn't conflict with previously

* chosen jobs.

*

* @param jobs the jobs which make up the job scheduling instance

* @return a list containing the selected jobs

*/

public static List<Job> byEarliestStart(List<Job> jobs) {

//TODO : implement this method.

return null;

}

public static void main(String[] args) {

List<Job> jobs = loadJobs(System.in);

System.out.println(byEarliestStart(jobs));

}

/**

* Loads a list of jobs from a specified input stream, such as standard input.

* The input is expected to be a newline-separated sequence of jobs, each given

* by a space-separated triplet of numbers, in order: id, startTime, finishTime.

*

* @param stream the input stream from which to read job data

* @return the loaded list of jobs

*/

public static List<Job> loadJobs(InputStream stream) {

Scanner scanner = new Scanner(stream);

List<Job> jobs = new ArrayList<>();

while (scanner.hasNext()) {

int id = scanner.nextInt();

float startTime = scanner.nextFloat();

float finishTime = scanner.nextFloat();

jobs.add(new Job(id, startTime, finishTime));

}

return jobs;

}

public static enum Strategy {

SHORTEST_INTERVAL,

EARLIEST_FINISH,

FEWEST_CONFLICTS,

EARLIEST_START

}

}

public class Job {

private final int id;

private final float startTime;

private final float finishTime;

public Job(int id, float startTime, float finishTime) {

this.id = id;

this.startTime = startTime;

this.finishTime = finishTime;

}

public int getId() {

return id;

}

public float getStartTime() {

return startTime;

}

public float getFinishTime() {

return finishTime;

}

public String toString() {

return "(" + id + ", " + startTime + ", " + finishTime + ")";

}

}

Answer 1

CODE TO COPY:

import java.io.File;

import java.io.FileNotFoundException;

import java.util.ArrayList;

import java.util.Arrays;

import java.util.Collections;

import java.util.Comparator;

import java.util.Scanner;

class Job{

private int id;

private float startTime;

private float endTime;

/**

* @return the id

*/

public int getId() {

return id;

}

/**

* @param id the id to set

*/

public void setId(int id) {

this.id = id;

}

/**

* @return the startTime

*/

public float getStartTime() {

return startTime;

}

/**

* @param startTime the startTime to set

*/

public void setStartTime(float startTime) {

this.startTime = startTime;

}

/**

* @return the endTime

*/

public float getEndTime() {

return endTime;

}

/**

* @param endTime the endTime to set

*/

public void setEndTime(float endTime) {

this.endTime = endTime;

}

public String toString()

{

return id+" "+startTime+" "+endTime;

}

}

public class JobTest {

public static void main(String[] args) throws FileNotFoundException {

File file=new File("inputJobs.txt");

Scanner obj=new Scanner(file);

ArrayList<Job> jobs=new ArrayList<Job>();

while(obj.hasNext())

{

Job job=new Job();

job.setId(obj.nextInt());

job.setStartTime(obj.nextFloat());

job.setEndTime(obj.nextFloat());

jobs.add(job);

}

Comparator<Job> cmp=new Comparator<Job>()

{

public int compare(Job a, Job b)

{

if(a.getEndTime()<b.getEndTime())

return -1;

else if(a.getEndTime()==b.getEndTime())

return 0;

return 1;

}

};

Collections.sort(jobs, cmp);//sort the jobs list using the comparator

int nonConflict=0;

int curJobIndex=0;

ArrayList<Job> nonConflictJobs=new ArrayList<Job>();

for(int i=0; i<jobs.size(); i++)

{

if(i==0)

{

nonConflictJobs.add(jobs.get(i));

nonConflict=1;

continue;

}

if(jobs.get(i).getStartTime()>=jobs.get(curJobIndex).getEndTime())

{

nonConflictJobs.add(jobs.get(i));

nonConflict++;

curJobIndex=i;

}

}

System.out.println("Number of non conflicting jobs: "+nonConflict);

System.out.println("Non conflicting jobs: "+nonConflictJobs.toString());

}

}

PROGRAM SCREENSHOTS:

OUTPUT:

In case of any doubt, please let me know in the comments section. I'll get it resolved :):) Don't forget to give a THUMBS UP! :)