Interval Scheduling Algorithm: Earliest Finish Time

Question

I'm trying to simulate a interval scheduling algorithm detecting the earliest finishing time using greedy technique. My problem is that what are the inputs if it will be created in a console application? What are the approaches? Thank you very much.

Answer 1

The inputs for each task are the start time and the end time (e.g. 10:00 start time and 14:00 end time). You can parse the console inputs into Dates or something along those lines, but if this is just a simulation then you might as well just have the console inputs be non-negative integers (e.g. 4 start time and 9 end time) since it will make your job of parsing the input easier.

There are several greedy approaches you can take, such as always selecting the shortest task (meaning the task with the shortest interval); the optimal approach is to always select the task that finishes first (e.g. you could sort the tasks according to ending time and select the next task that doesn't conflict, although there may be a linear-time algorithm to accomplish this).