CSC 421: Algorithm Design & Analysis
Spring 2015

HW4: Greedy Scheduling


Consider the challenge of constructing a daily schedule given a (potentially large) set of event options. For example, a student planning his or her day might choose from the following possible events:

StartEndEvent
0:00 7:30 Sleep
0:00 10:20 Sleep late
8:00 8:45 Breakfast with friends
8:30 9:00 SportsCenter
8:50 10:30 Study for class
11:00 12:15 CSC 421
12:30 13:30 Lunch
13:00 17:00 Golf
13:20 13:40 Power nap
14:00 15:15 CSC533
15:10 15:20 Call parents

You are to implement two different greedy approaches for constructing a schedule:

Your program should read in a text file, with each line specifying the start and end times (in military notation) and a description of a single event. For example, see events.txt. Your program should display two possible schedules, one generated using the Shortest event first approach and one using the Earliest end-time first approach. Each schedule should list the selected events in chronological order (one event per line) and should clearly identify the approach used. For example:

Shortest event first: --------------------- 00:00 07:30 Sleep 08:30 09:00 SportsCenter ... Earlist end-time first: ----------------------- 00:00 07:30 Sleep 08:00 08:45 Breakfast with friends ...

In completing this assignment, you are free to use classes in the official Java libraries, but you may not utilize any other classes that you did not write yourself. You should follow good object-oriented practices in completing the program, defining highly-cohesive and loosely-coupled classes as needed.