### 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:

• Shortest event first: Repeatedly select the shortest event that does not conflict with previously selected events. For example, given the event options above, the first event to be selected would be Call parents since it only takes 10 minutes. Next would be Power nap (20 minutes) and SportsCenter (30 minutes). The next shortest event, Breakfast with friends (45 minutes), cannot be selected since it conflicts with SportsCenter, so Lunch (1 hour) is selected next.
• Earliest end-time first: Repeatedly select the non-conflicting event that has the earliest end-time. For example, given the options above, the first event to be selected would be Sleep since it ends at 7:30. The event with next earliest end-time, Breakfast with friends (8:45), would be selected next. SportsCenter (9:00) cannot be selected since it conflicts with Breakfast with friends, as does Sleep late (10:20), so the next selection would be Study for class (10:30).

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.