Activity Selection Problem in Java for Beginners

The Activity Selection Problem is a classic example of using the Greedy Algorithm. In this problem, we aim to select the maximum number of non-overlapping activities from a given set of activities with their start and end times.

In this blog, we will break the problem into simple steps, making it easy for beginners to understand. Let’s dive into it!

Problem Statement

We are given n activities, where each activity has a start time and an end time. The goal is to select as many activities as possible so that no two selected activities overlap.

Example Input

Activity	Start Time	End Time
A1	1	3
A2	2	5
A3	4	7
A4	1	8
A5	5	9
A6	8	10

Expected Output

Maximum number of non-overlapping activities: 3

Selected Activities:
A1 (1–3), A3 (4–7), A6 (8–10)

Step-by-Step Solution

We will solve this problem using a Greedy Algorithm, which always picks the best possible option at each step.

Code and Explanation

1. Import Required Classes

We need the Arrays and Comparator classes to sort the activities by their end times.

import java.util.*; // Import required utilities like Arrays and Comparator

2. Define an Activity Class

We need a way to store the start time and end time of each activity. We’ll create a simple Activity class.

class Activity {
    int start; // Start time of the activity
    int end;   // End time of the activity

    // Constructor to initialize start and end times
    Activity(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

3. Create the Main Class

Now, we’ll define the main class where the program logic will be written.

public class ActivitySelection {
    public static void main(String[] args) {
        // Step 1: Define the activities
        Activity[] activities = {
            new Activity(1, 3),
            new Activity(2, 5),
            new Activity(4, 7),
            new Activity(1, 8),
            new Activity(5, 9),
            new Activity(8, 10)
        };

        // Step 2: Sort the activities by their end times
        Arrays.sort(activities, new Comparator<Activity>() {
            public int compare(Activity a1, Activity a2) {
                return a1.end - a2.end; // Sort by end time in ascending order
            }
        });

        // Step 3: Select activities using a greedy approach
        int count = 1; // We always select the first activity
        int lastEndTime = activities[0].end; // Store the end time of the first activity

        System.out.println("Selected activities:");
        System.out.println("Activity with start: " + activities[0].start + ", end: " + activities[0].end);

        // Loop through the rest of the activities
        for (int i = 1; i < activities.length; i++) {
            if (activities[i].start >= lastEndTime) { // Check if the activity is non-overlapping
                count++; // Increment the count of selected activities
                lastEndTime = activities[i].end; // Update the last end time

                // Print the selected activity
                System.out.println("Activity with start: " + activities[i].start + ", end: " + activities[i].end);
            }
        }

        // Step 4: Print the result
        System.out.println("Maximum number of activities: " + count);
    }
}

Detailed Explanation of Code

Step 1: Define Activities

In this step, we manually create an array of activities, each having a start and end time. This is our input.

Activity[] activities = {
    new Activity(1, 3),
    new Activity(2, 5),
    new Activity(4, 7),
    new Activity(1, 8),
    new Activity(5, 9),
    new Activity(8, 10)
};

Step 2: Sort Activities by End Time

To ensure that we pick the maximum number of non-overlapping activities, we need to process activities in increasing order of their end times. Sorting helps us achieve this.

We use Arrays.sort with a custom comparator that compares the end values.

Arrays.sort(activities, new Comparator<Activity>() {
    public int compare(Activity a1, Activity a2) {
        return a1.end - a2.end;
    }
});

After sorting, the activities will be arranged as:

Activity	Start Time	End Time
A1	1	3
A2	2	5
A3	4	7
A4	1	8
A5	5	9
A6	8	10

Step 3: Select Activities

The first activity is always selected because it ends the earliest.

int count = 1; // First activity is selected
int lastEndTime = activities[0].end; // End time of the first activity

Now, for each activity, check if its start time is greater than or equal to the end time of the last selected activity. If yes, select it and update the lastEndTime.

for (int i = 1; i < activities.length; i++) {
    if (activities[i].start >= lastEndTime) { // Check if activity is non-overlapping
        count++; // Increment count of selected activities
        lastEndTime = activities[i].end; // Update the last end time
    }
}

Step 4: Print the Result

Finally, we print the total number of activities that can be selected along with the details of each selected activity.

System.out.println("Maximum number of activities: " + count);

Correct Selection Process

Let’s walk through the activity selection process step-by-step:

Select A1 (1–3):
- First activity is always selected.
- Last End Time: 3.
Skip A2 (2–5):
- Start time 2 is less than the last end time 3.
Select A3 (4–7):
- Start time 4 is greater than or equal to 3.
- Last End Time: 7.
Skip A4 (1–8):
- Start time 1 is less than the last end time 7.
Skip A5 (5–9):
- Start time 5 is less than the last end time 7.
Select A6 (8–10):
- Start time 8 is greater than or equal to 7.
- Last End Time: 10.

Output

For the given input, the program will output:

Selected activities:
Activity with start: 1, end: 3
Activity with start: 4, end: 7
Activity with start: 8, end: 10
Maximum number of activities: 3

Key Takeaways

Sorting: Sorting the activities by their end times ensures we process them optimally.
Greedy Choice: The greedy algorithm makes a local optimal choice (select the next activity that doesn’t overlap).
Efficiency: This algorithm runs in O(n log n) due to sorting, making it efficient for large inputs.

This program is a great example of how a Greedy Algorithm works in scheduling problems. Try implementing it yourself and experiment with different inputs. If you have any questions, feel free to ask in the comments! 😊