Activity Selection Problem – Selecting the maximum number of non-overlapping activities from a given set of activities

Problem Statement

Given a set of activities, each with a start time and a finish time, determine the maximum number of activities that can be performed by a single person or machine, assuming that a person or machine can only work on one activity at a time.

Example:

Consider the following activities with their respective start and finish times:

Activity	Start Time	Finish Time
A1	1	2
A2	3	4
A3	0	6
A4	5	7
A5	8	9
A6	5	9

Solution:
To maximize the number of non-overlapping activities, select activities A1, A2, A4, and A5.

Greedy Approach

The Activity Selection Problem can be efficiently solved using a greedy algorithm. The idea is to always choose the next activity that finishes the earliest and is compatible with the already selected activities. This greedy choice ensures that we have the most room for subsequent activities.

Steps to Solve Using Greedy Algorithm

1. Sort Activities: Sort the activities by their finish times in ascending order.
2. Select First Activity: Select the first activity (which has the earliest finish time) and add it to the solution.
3. Iterate and Select: Iterate through the remaining activities and select the next activity if its start time is greater than or equal to the finish time of the last selected activity.
4. Repeat: Continue until all activities are considered.

Java Implementation

Here’s a Java program to solve the Activity Selection Problem using a greedy approach:

import java.util.Arrays;

public class ActivitySelection {

    // Function to perform activity selection
    public static void activitySelection(int[] start, int[] finish) {
        int n = start.length; // Number of activities

        // Create an array of activities
        Activity[] activities = new Activity[n];
        for (int i = 0; i < n; i++) {
            activities[i] = new Activity(start[i], finish[i]);
        }

        // Sort activities by finish time
        Arrays.sort(activities, (a, b) -> a.finish - b.finish);

        // Select the first activity
        System.out.println("Selected activities:");
        System.out.println("(" + activities[0].start + ", " + activities[0].finish + ")");
        int lastFinishTime = activities[0].finish;

        // Iterate over the remaining activities
        for (int i = 1; i < n; i++) {
            // If this activity's start time is >= the last selected activity's finish time
            if (activities[i].start >= lastFinishTime) {
                System.out.println("(" + activities[i].start + ", " + activities[i].finish + ")");
                lastFinishTime = activities[i].finish; // Update the last finish time
            }
        }
    }

    // Activity class to store start and finish time
    static class Activity {
        int start;
        int finish;

        Activity(int start, int finish) {
            this.start = start;
            this.finish = finish;
        }
    }

    public static void main(String[] args) {
        int[] start = {1, 3, 0, 5, 8, 5};
        int[] finish = {2, 4, 6, 7, 9, 9};
        activitySelection(start, finish);
    }
}

Explanation of the Code

1. Main Method:
   • Defines the start and finish times of the activities.
   • Calls the activitySelection method to find and print the maximum number of non-overlapping activities.
2. activitySelection Method:
   • Creates an array of Activity objects from the given start and finish times.
   • Sorts the activities by their finish times.
   • Selects the first activity and iterates through the rest to select the next compatible activity based on the start time.
3. Activity Class:
   • A simple class to store the start and finish times of an activity.

Output

For the input start times {1, 3, 0, 5, 8, 5} and finish times {2, 4, 6, 7, 9, 9}, the output is:

Selected activities:
(1, 2)
(3, 4)
(5, 7)
(8, 9)

Why the Greedy Approach Works

The greedy algorithm works for the Activity Selection Problem because it ensures that:

• By always selecting the activity that finishes earliest, we leave as much room as possible for other activities.
• This approach leads to an optimal solution as it maximizes the number of non-overlapping activities that can be scheduled.

Applications

• Scheduling: Used in job scheduling, resource allocation, and time management problems.
• Operations Research: Helps in optimizing processes and workflows in various industries.
• Computer Systems: Applied in task scheduling for CPUs and managing simultaneous processes.

Conclusion

The Activity Selection Problem is a perfect example to illustrate the effectiveness of greedy algorithms. By making locally optimal choices—selecting activities that finish the earliest while allowing for the maximum room for future activities—we can solve the problem efficiently. The greedy approach is simple to implement and highly efficient for this class of problems, making it a powerful tool in the domain of optimization and scheduling.

---

Feel free to run the provided Java code and try it with different sets of activities to see how the greedy algorithm performs. If you have any questions or need further clarification, leave a comment below!