Most Efficient Schedule

Talk Scheduling

Imagine you are a conference organizer and you are tasked with scheduling the largest possible subset from a set of talks all in the same room. Each talk in the set has a given start time and end time. These times cannot change. No talks that have times that overlap can be scheduled in the same room. For the sake of this assignment assume that one talk can begin instantly upon completion of the previous talk. Consider the example below with three talks in the set:

Talks:

  1. Fred Flinstone 9:00AM-11AM
  2. Barney Rubble 10:30AM-4PM
  3. Bam Bam Rubble 1PM-1:15PM

The optimal schedule (the one that schedules the most talks) in this example would be to schedule Fred’s talk and Bam Bam’s talk.

This AssignmentStep 1: Come up with an algorithm that will lead to scheduling the greatest number of talks.
Step 2: Implement your algorithm in Java using the design outline below.

Talks file containing a list of 50 talks along with their start and end times. Your application must read a file in this format and schedule the maximium number of talks that can be scheduled in a single room. To do this write the following two classes:

  1. Talk.java- This class is used to model a talk and may be used to provide the title and/or speaker for a talk along with the start and stop times of the talk. This class should implement the Comparable interface.
  2. Scheduler.java – This class will serve as a repository for static methods that you will use to schedule the talks.

Included on Codio is a test class, ScheduleTest.java. Your code must work with our tester.

* You can only define one compareTo method

* You will not need to specify the name of the text file anywhere. The command line argument is the name of the text file, and will be passed to the makeTalks method as such:

// on the command line:

$ javaScheduleTest nameOfTalksFile.txt

// in ScheduleTest (written for you!)

ArrayList<Talk> talks =Scheduler.makeTalks(args[0]);// args[0] will be the name of the file, which here is nameOfTalksFile.txt

* only the methods in Scheduler need to be static.

The methods in Talk do not need to be static.

*You should be able to handle all kinds of weird tab cases and talks.txt contents?

*You can throw as many exceptions as you want in our scheduler class, but you’d need to indicate them in each method header.

Example:

publicvoid foo()throwsFileNotFoundException,IndexOutOfBoundsException{

// code here

}

Example:

publicvoid foo()throwsIndexOutOfBoundsException{

int[]arr={1,2,3,4,5};

// Doing this will throw an IndexOutOfBoundsException

arr[5];

// But so will doing this

throwIndexOutOfBoundsException;

}

*In our scheduleTest class, The IOException contains the FileNotFoundException, and so “catching” IOExceptions accounts for all types of IOExceptions.

*For our scheduleTest class, Try to use try-catch blocks to handle runtime exceptions

* the file name is provided as input argument to one of the static methods of Schedule class.Note that args[0] represent the first word of the command line argument you type after the line “java ScheduleTest” in your terminal. The “makeTalks” static method, then, takes in the input argument and read the file that the argument specifies, and returns a corresponding arraylist of talks.

ArrayList<Talk> talks = Scheduler.makeTalks(args[0]);

// input: command line argument that represents the name of the text file that you are going to read in makeTalks() of // Scheduler class

// output: arraylist of talks

BufferedFileIO.java

/**

* Example of file input/ouput and using try-catch to handle exceptions

* FileInputOutput – Reads in text file from command line then returns a

*                            reversed version of the text file into a new text file

*/

import java.io.*;

importjava.util.Scanner;

importjava.util.ArrayList;

public class BufferedFileIO {

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

try{

// Reads in file from text file given via command line

FileReaderinputFile = new FileReader(args[0]);

BufferedReader reader = new BufferedReader(inputFile);

ArrayList<String>poemList = new ArrayList<>();

// Add contents of text file into ArrayList

String line;

while((line = reader.readLine()) != null) {

poemList.add(line);

}

// Prints out the ArrayList using enhanced for loop

for(String poemLine : poemList) {

System.out.println(poemLine);

}

// Creates new file to be written in

// File outputFile = new File(“reversed_poem.txt”);

// PrintWriter printer = new PrintWriter(outputFile);

// // Write text file lines in reverse order into outputFile

// for(int i = poemList.size() – 1; i >= 0; i–) {

//    String toPrint = new String(poemList.get(i));

//    printer.println(toPrint);

// }

FileWriteroutputFile = new FileWriter(“reversed_poem2.txt”);

BufferedWriter writer = new BufferedWriter(outputFile);

// Write text file lines in reverse order into outputFile

for(int i = poemList.size() – 1; i >= 0; i–) {

line = poemList.get(i);

writer.write(line, 0, line.length());

writer.newLine();

}

// Close your scanner and printer!!

inputFile.close();

outputFile.close();

reader.close();

writer.close();

}

catch (IOException e) {

System.out.println(“File not found.”);

return;

}

}

} 

ExampleA.java

importjava.util.Scanner;

import java.io.*;

public class ExampleA

{

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

{

File inFile = new File(args[0]);

Scanner input = new Scanner(inFile);

String word;

PrintWriter output = new PrintWriter(args[1]);

while(input.hasNext())

{

word=input.next();

output.println(word);

}

output.close();

}

}

 ExampleB.java

importjava.util.Scanner;

import java.io.*;

public class ExampleB

{

public static void main(String[] args)

{

try{

File inFile = new File(args[0]);

Scanner input = new Scanner(inFile);

String word;

PrintWriter output = new PrintWriter(args[1]);

while(input.hasNext())

{

word=input.nextLine();

output.println(word);

}

output.close();

}

catch(FileNotFoundExceptionfred){

System.out.println(“Please try again with correct input file name”);

System.out.println(fred);

}

catch(ArrayIndexOutOfBoundsException e){

System.out.println(“At least two command line arguments “);

}

}

}

ExampleC.java

importjava.util.Scanner;

import java.io.*;

public class ExampleC

{

public static void main(String[] args)

{

boolean again=true;

while(again){

try{

File inFile = new File(args[0]);

Scanner input = new Scanner(inFile);

String word;

PrintWriter output = new PrintWriter(args[1]);

while(input.hasNext())

{

word=input.next();

output.println(word);

}

output.close();

again=false;

}//end try

catch(IOException e){

System.out.println(“Please try again with correct input file name”);

Scanner scan = new Scanner(System.in);

args[0]=scan.next();

}

catch(ArrayIndexOutOfBoundsException e) {

System.out.println(“Specify a command-line argument you idiot”);

again=false;

}

}//end while

}

} 

ExampleD.java

importjava.util.Scanner;

import java.io.*;

public class ExampleD

{

public static void main(String[] args)

{

try{

File inFile = new File(“/usr/dict/words”);

Scanner input = new Scanner(inFile);

String word;

PrintWriter output = new PrintWriter(“output.txt”);

while(input.hasNext())

{

word=input.nextLine();

output.println(word);

}

output.close();

}

catch(IOException e){

System.out.println(“Please try again with correct input file name”);

}

catch(Exception e){

System.out.println(“dude you messed up”);

System.out.println(e);

}

}

}

 FileInputOutput.java

/**

* Example of file input/ouput and using try-catch to handle exceptions

* FileInputOutput – Reads in text file from command line then returns a

*                            reversed version of the text file into a new text file

*/

import java.io.*;

importjava.util.Scanner;

importjava.util.ArrayList;

public class FileInputOutput {

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

try{

// Reads in file from text file given via command line

File inputFile = new File(args[0]);

Scanner myScanner = new Scanner(inputFile);

ArrayList<String>poemList = new ArrayList<>();

// Add contents of text file into ArrayList

while(myScanner.hasNextLine()) {

poemList.add(myScanner.nextLine());

}

// Prints out the ArrayList using enhanced for loop

for(String poemLine : poemList) {

System.out.println(poemLine);

}

// Creates new file to be written in

File outputFile = new File(“reversed_poem.txt”);

PrintWriter printer = new PrintWriter(outputFile);

// Write text file lines in reverse order into outputFile

for(int i = poemList.size() – 1; i >= 0; i–) {

String toPrint = new String(poemList.get(i));

printer.println(toPrint);

}

// Close your scanner and printer!!

myScanner.close();

printer.close();

}

catch (FileNotFoundException e) {

System.out.println(“File not found.”);

return;

}

}

} 

ScheduleTest.java

/* Your code must work with test class.

Do not alter this class.

*/

importjava.util.ArrayList;

import java.io.*;

public class ScheduleTest{

public static void main(String[] args){

// First, use a command line argument to speicify the f

// name of the file containing the talks.

// Then write a static method makeTalks that returns

// an ArrayList of talks. This method must handle any exceptions.

if (args.length>0)

{

try

{

ArrayList<Talk> talks = Scheduler.makeTalks(args[0]);

// Next, pass the ArrayList of talks to the staic method

// scheduleTalks to schedule the maximum number of talks in

// the ArrayList.

ArrayList<Talk>scheduledTalks=Scheduler.scheduleTalks(talks);

// Finally, print the list of scheduled talks. Notice this requires a

// toString method in the Talk class. You will have to provide one.

for (Talk talk:scheduledTalks){

System.out.println(talk);

}

}

catch(IOException e)

{

System.out.println(“There is a problem with the file you specified”);

}

}

else

{

System.out.println(“You must specify a file name at the command line”);

}

}

} 

Solution

Scheduler.java

// Scheduler.java

import java.io.*;

importjava.util.*;

public class Scheduler

{

public static ArrayList<Talk>makeTalks(String filename) throws IOException

{

// define and create array list

ArrayList<Talk>makeTalkList = new ArrayList<Talk>();

try

{

// define the file object

File openFile = new File(filename);

// define the scanner class object by pointing to the

// text file

Scanner inputFile = new Scanner(openFile);

booleanemtptyFile = true;

// while loop through the text file

while (inputFile.hasNextLine())

{

emtptyFile = false;

booleancorrectLine = true;

String currentLine = inputFile.nextLine();

String linetokens[] = currentLine.split(“\t”);

// define a talk class object

Talk talks = new Talk();

// by the use of set method set the values into the

// talk class object

int index = 0;

correctLine = index <linetokens.length;

if (correctLine)

{

talks.setNameOfTalker(linetokens[index]);

}

index++; // go to next record token (‘start time’)

// skip excess ‘\t’ characters from record string

while (linetokens[index].isEmpty() &&

index<linetokens.length) {

index++;

}

correctLine = index <linetokens.length;

if (correctLine)

{

try {

Integer.parseInt(linetokens[index]);

} catch (NumberFormatException e) {

correctLine = false;

}

if (correctLine)

{

talks.setStartingTime(linetokens[index]);

}

}

index++;

correctLine = index <linetokens.length;

if (correctLine)

{

try {

Integer.parseInt(linetokens[index]);

} catch (NumberFormatException e) {

correctLine = false;

}

if (correctLine)

{

talks.setEndingTime(linetokens[index]);

}

}

if (correctLine)

{

// add the talk class object to makeTalkList object

makeTalkList.add(talks);

}

else

{

System.out.println(“Bad format”);

makeTalkList.clear();

returnmakeTalkList;

}

}

// close the file

inputFile.close();

if (emtptyFile)

{

System.out.println(“Empty data”);

returnmakeTalkList;

}

if (makeTalkList.size() < 3)

{

System.out.println(“Index out of bounds”);

makeTalkList.clear();

returnmakeTalkList;

}

}

catch(ArrayIndexOutOfBoundsException e)

{

System.out.println(“Index out of bounds”);

}

// return the created list

returnmakeTalkList;

}

// sortTalksByStartTime() method: Accepts an array list and returns the

// array list of talks.

private static ArrayList<Talk>sortTalksByStartTime(ArrayList<Talk> talks)

{

// define a new array list

ArrayList<Talk>newSortedList = new ArrayList<Talk>();

// loop through each value of the talks object

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

{

// add the value at index i of talks to newSortedList

newSortedList.add(talks.get(i));

}

// define the comparator to sort with respect to the start time

// if the both the start times are equal and then sort by end time

Collections.sort(newSortedList, new Comparator<Talk>()

{

@Override

publicint compare(Talk talk1, Talk talk2)

{

if (Integer.parseInt(talk1.getStartingTime()) == Integer.parseInt(talk2.getStartingTime()))

{

if (Integer.parseInt(talk1.getEndingTime()) >Integer.parseInt(talk2.getEndingTime()))

return 1;

else if (Integer.parseInt(talk1.getEndingTime()) <Integer.parseInt(talk2.getEndingTime()))

return -1;

else

return 0;

}

else if (Integer.parseInt(talk1.getStartingTime()) >Integer.parseInt(talk2.getStartingTime()))

return 1;

else

return -1;

}

});

// return the sorted list

returnnewSortedList;

}

// getTalksWithoutOverlappingByStartTime() method: Accepts an array list and returns the

// array list of talks.

private static ArrayList<Talk>getTalksWithoutOverlappingByStartTime(ArrayList<Talk>starttalks)

{

// define a new list

ArrayList<Talk>newList = new ArrayList<Talk>();

// append the starting talks object at index 0

newList.add(starttalks.get(0));

// define an index value

int index = 0;

// loop through each value in the start talks list

for (int i = 1; i <starttalks.size(); i++)

{

// check the condition whether the newList’s last added talks objects

// end time is less than the start time start talks list

if (Integer.parseInt(newList.get(index).getEndingTime()) < Integer

.parseInt(starttalks.get(i).getStartingTime()))

{

// if so, add the start talks value at index i to the newList

newList.add(starttalks.get(i));

// increment the index

index++;

}

}

// return the newList

returnnewList;

}

// getTalksWithoutOverlappingByShortTime() method: Accepts an array list and returns the

// array list of talks.

private static ArrayList<Talk>getTalksWithoutOverlappingByShortTime(ArrayList<Talk>starttalks)

{

// define a new list

ArrayList<Talk>newList = new ArrayList<Talk>();

// append the starting talks object at index 0

newList.add(starttalks.get(0));

// define a boolean value

boolean flag = false;

// loop through each value in the starttalks

for (int i = 1; i <starttalks.size(); i++)

{

// reset the flag to true

flag = true;

// get the integer format of the start and end time of the starttalks object

// at index i

intendTimeCurrent = Integer.parseInt(starttalks.get(i).getEndingTime());

intstartTimeCurrent = Integer.parseInt(starttalks.get(i).getStartingTime());

// loop each value in the newList

for (int j = 0; j <newList.size(); j++)

{

// get the integer format of the start and end time of the newList object

// at index j

intendTimeNew = Integer.parseInt(newList.get(j).getEndingTime());

intstartTimeNew = Integer.parseInt(newList.get(j).getStartingTime());

// check the condition whether the current talks time’s start time and end time

// lies within the range of newlist’s start and end time

if ((endTimeCurrent>= startTimeNew&&endTimeCurrent<= endTimeNew)

|| (startTimeCurrent>= startTimeNew&&startTimeCurrent<= endTimeNew))

{

// if so, set the flag to false

flag = false;

// break the loop

break;

}

}

// if flag is true then add the starttalks’s object at

// index i to newList

if(flag)

{

newList.add(starttalks.get(i));

}

}

// return new list

returnnewList;

}

// scheduleTalks() method: Accepts an array list and returns the

// array list of talks.

public static ArrayList<Talk>scheduleTalks(ArrayList<Talk>makeTalkList)

{

// define the required arraylist

ArrayList<Talk>scheduledTalks = new ArrayList<Talk>();

ArrayList<Talk>sortedTalksStartTime = new ArrayList<Talk>();

ArrayList<Talk>talksByShortestTime = new ArrayList<Talk>();

ArrayList<Talk>sortedTalksbyShortestTime = new ArrayList<Talk>();

ArrayList<Talk>timeDifferenceTalks = new ArrayList<Talk>();

ArrayList<Talk>startTimeTalks = new ArrayList<Talk>();

if (makeTalkList.size() < 1)

{

returnscheduledTalks;

}

// To get the copy of the makeTalkList

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

{

timeDifferenceTalks.add(makeTalkList.get(i));

}

// call the sort method of the timeDiffenece object

// to sort the list by the shortest time

Collections.sort(timeDifferenceTalks);

// call sortTalksByStartTime() method by passing the makeTalkList

// store the return arraylist in startTimeTalks

startTimeTalks = sortTalksByStartTime(makeTalkList);

// getTalksWithoutOverlappingByStartTime() method by passing the

// startTimeTalks and store the return value into sortedTalksStartTime

sortedTalksStartTime = getTalksWithoutOverlappingByStartTime(startTimeTalks);

// getTalksWithoutOverlappingByShortTime() method by passing the

// timeDifferenceTalks and store the return value into talksByShortestTime

talksByShortestTime = getTalksWithoutOverlappingByShortTime(timeDifferenceTalks);

// sort the arraylisttalksByShortestTime by calling the

// method sortTalksByStartTime() and store the return value in

// sortedTalksbyShortestTime

sortedTalksbyShortestTime = sortTalksByStartTime(talksByShortestTime);

// now check both the sizes of the talks that are obtained

// who-ever size is more set those arraylist into scheduledTalks

// arraylist

if(sortedTalksStartTime.size() >sortedTalksbyShortestTime.size())

scheduledTalks = sortedTalksStartTime;

else

scheduledTalks = sortedTalksbyShortestTime;

// return the list

returnscheduledTalks;

}

} 

Talk.java

// class to hold the name of the talker and start time and end time

// this class implements the Comparable interface

public class Talk  implements Comparable<Talk>

{

// define the class variables

private String nameOfTalker;

private  StringstartingTime, endingTime;

// default constructor

public Talk()

{

}

// getNameOfTalker() method to retrieve the name of the talker

public String getNameOfTalker()

{

returnnameOfTalker;

}

// setNameOfTalker() method to set the name of the talker

public void setNameOfTalker(String nameOfTalker)

{

this.nameOfTalker = nameOfTalker;

}

// getNameOfTalker() method to retrieve the starting time

public String getStartingTime()

{

returnstartingTime;

}

// setStartingTime() method to set the starting time

public void setStartingTime(String startingTime)

{

this.startingTime = startingTime;

}

// getEndingTime() method to retrieve the end time

public String getEndingTime()

{

returnendingTime;

}

// setEndingTime() method to set the end time

public void setEndingTime(String endingTime)

{

this.endingTime = endingTime;

}

// getTimeDifference() method to retrieve the time difference(duration of talks)

publicintgetTimeDifference()

{

returnInteger.parseInt(endingTime) – Integer.parseInt(startingTime);

}

// getFormatedTime() method sets the given time to the

// AM and PM format and returns the string

public String getFormatedTime(String time)

{

// get the hours and minutes from the time parameter

String hours = time.substring(0,2);

String minutes = time.substring(2);

// convert the hours to int format

int hour = Integer.parseInt(hours);

// set the time in hh:minutes format

String timeForm = hours+”:”+minutes;

// append AM or PM depending on the hours

if(hour < 12)

timeForm +=”AM”;

else

timeForm += “PM”;

// return the string

returntimeForm;

}

// toString() method to return the formated talk details

public String toString()

{

String result = “”;

result += getNameOfTalker()+” “+getFormatedTime(startingTime)+” – “+getFormatedTime(endingTime);

return result;

}

// compareTo() method which returns the shortest time

@Override

publicintcompareTo(Talk anotherTalk)

{

returngetTimeDifference() – anotherTalk.getTimeDifference();

}

}