CSC 421: Algorithm Design & Analysis
Spring 2018

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 in
7:45 8:00 Shower
8:00 8:45 Breakfast with friends
8:10 8:40 YouTube
8:50 10:30 Study for class
11:00 12:15 *CSC 581
12:30 13:45 Lunch
12:30 13:30 Exercise
13:30 13:50 Power nap
14:00 15:15 *CSC 421
15:15 15:25 Call parents

In general, two events are in conflict if one is entirely contained with the other (e.g., Exercise is contained within Lunch) or the end of the earlier event is after the start of the later event (e.g., Study for class overlaps with Sleep in). Events that are required, i.e., must be included in any schedule, are preceded with an asterisk. You may assume that required events cannot be in conflict with each other.

You are to implement four 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 the four schedules generated using the above greedy strategies. Each schedule should list the selected events in chronological order (one event per line) and should clearly identify the approach used. Asterisks should NOT appear when displaying required events and times should be properly aligned. For example:

Shortest event first: --------------------- 0:00 7:30 Sleep 7:45 8:00 Shower 8:10 8:40 YouTube ... Longest event first: -------------------- 0:00 10:20 Sleep in 11:00 12:15 CSC 581 12:30 13:45 Lunch ... Earlist start-time first: ------------------------- 0:00 7:30 Sleep 7:45 8:00 Shower 8:00 8:45 Breakfast with friends ... Earlist end-time first: ----------------------- 0:00 7:30 Sleep 7:45 8:00 Shower 8:10 8:40 YouTube ...

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. Likewise, avoid duplicate and redundant code wherever possible.