//ActivitySelectionDemo.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

class ActivityFinishTimeComparator implements Comparator<Activity>
{
    public int compare(Activity activity1, Activity activity2)
    {
        return activity1.finishTime - activity2.finishTime;
    }
}

public class ActivitySelectionDemo
{
    public static ArrayList<Activity> activitySelection(Activity[] activities)
    {
        // Start with an empty list of selected activities
        ArrayList<Activity> chosenActivities = new ArrayList<Activity>();

        // Sort the list of activities in increasing order of finishTime
        Arrays.sort(activities, new ActivityFinishTimeComparator());

        // Add the first activity to the chosenActivities list
        Activity current = activities[0];
        chosenActivities.add(current);

        // Process all the remaining activities, in order
        for (int i = 1; i < activities.length; i++)
        {
            // If the next activity does not conflict with
            // the most recently selected activity, select the
            // next activity
            if (!activities[i].conflictsWith(current))
            {
                chosenActivities.add(activities[i]);
                current = activities[i];
            }
        }

        // The chosenActivities list is an optimal list of
        // activities with no conflicts
        return chosenActivities;
    }

    public static void main(String[] args)
    {
        // Program to test Activity Selection greedy algorithm. The
        // startTime and finishTime are represented with integers
        // (ex: "20" is 20:00, or 8:00 PM).
        Activity[] activities =
        {
            new Activity("Fireworks show", 20, 21),
            new Activity("Morning mountain hike", 9, 12),
            new Activity("History museum tour", 9, 10),
            new Activity("Day mountain hike", 13, 16),
            new Activity("Night movie", 19, 21),
            new Activity("Snorkeling", 15, 17),
            new Activity("Hang gliding", 14, 16),
            new Activity("Boat tour", 11, 14)
        };

        // Use the activitySelection() method to get a list of optimal
        // activities with no conflicts.
        ArrayList<Activity> itinerary = activitySelection(activities);
        for (Activity activity : itinerary)
        {
            // Output the activity's information.
            System.out.printf
            (
                "%s - start time: %d, finish time: %d%n",
                activity.name,
                activity.startTime,
                activity.finishTime
            );
        }
    }
}