class ActivityFinishTimeComparator implements Comparator
public class ActivitySelectionDemo
1: //ActivitySelectionDemo.java
3: import java.util.ArrayList;
4: import java.util.Arrays;
5: import java.util.Comparator;
6: import java.util.Scanner;
8: class ActivityFinishTimeComparator implements Comparator<Activity>
9: {
10: public int compare(Activity activity1, Activity activity2)
11: {
12: return activity1.finishTime - activity2.finishTime;
13: }
14: }
16: public class ActivitySelectionDemo
17: {
18: public static ArrayList<Activity> activitySelection(Activity[] activities)
19: {
20: // Start with an empty list of selected activities
21: ArrayList<Activity> chosenActivities = new ArrayList<Activity>();
23: // Sort the list of activities in increasing order of finishTime
24: Arrays.sort(activities, new ActivityFinishTimeComparator());
26: // Add the first activity to the chosenActivities list
27: Activity current = activities[0];
28: chosenActivities.add(current);
30: // Process all the remaining activities, in order
31: for (int i = 1; i < activities.length; i++)
32: {
33: // If the next activity does not conflict with
34: // the most recently selected activity, select the
35: // next activity
36: if (!activities[i].conflictsWith(current))
37: {
38: chosenActivities.add(activities[i]);
39: current = activities[i];
40: }
41: }
43: // The chosenActivities list is an optimal list of
44: // activities with no conflicts
45: return chosenActivities;
46: }
48: public static void main(String[] args)
49: {
50: // Program to test Activity Selection greedy algorithm. The
51: // startTime and finishTime are represented with integers
52: // (ex: "20" is 20:00, or 8:00 PM).
53: Activity[] activities =
54: {
55: new Activity("Fireworks show", 20, 21),
56: new Activity("Morning mountain hike", 9, 12),
57: new Activity("History museum tour", 9, 10),
58: new Activity("Day mountain hike", 13, 16),
59: new Activity("Night movie", 19, 21),
60: new Activity("Snorkeling", 15, 17),
61: new Activity("Hang gliding", 14, 16),
62: new Activity("Boat tour", 11, 14)
63: };
65: // Use the activitySelection() method to get a list of optimal
66: // activities with no conflicts.
67: ArrayList<Activity> itinerary = activitySelection(activities);
68: for (Activity activity : itinerary)
69: {
70: // Output the activity's information.
71: System.out.printf
72: (
73: "%s - start time: %d, finish time: %d%n",
74: activity.name,
75: activity.startTime,
76: activity.finishTime
77: );
78: }
79: }
80: }