Maximizing Activities with a Greedy Algorithm in Java

Explore a classic problem in computer science known as the Activity Selection Problem. We’ll solve it using a Greedy Algorithm approach in Java. This problem is a great example of how greedy algorithms can be used to find an optimal solution efficiently.

Problem Statement

Given a set of activities with their start and end times, we need to select the maximum number of activities that can be performed by a single person, assuming that a person can only work on a single activity at a time.

The Greedy Approach

The greedy approach to solving this problem involves selecting the activity that finishes the earliest and then selecting the next activity that starts after the current one finishes. This ensures that we can maximize the number of activities selected.

Java Implementation

Here’s a Java implementation of the greedy algorithm for the Activity Selection Problem:

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

public class GreedyAlog_maxActivity {

    public static int maxActivity(int start[], int end[]) {
        int ans[][] = new int[start.length][3];
        for (int i = 0; i < ans.length; i++) {
            ans[i][0] = i;
            ans[i][1] = start[i];
            ans[i][2] = end[i];
        }
        Arrays.sort(ans, Comparator.comparingDouble(o -> o[2]));

        int maxAct = 0;
        ArrayList<Integer> arr = new ArrayList<>();

        arr.add(ans[0][0]);
        int lastEnd = ans[0][2];
        maxAct = 1;

        for (int i = 0; i < end.length; i++) {
            if (ans[i][1] >= lastEnd) {
                maxAct++;
                lastEnd = ans[i][2];
                arr.add(ans[i][0]);
            }
        }
        return maxAct;
    }

    public static void main(String[] args) {
        int start[] = {5, 39, 5, 27, 50};
        int end[] = {24, 60, 28, 40, 90};

        int ans = maxActivity(start, end);
        System.out.println(ans);
    }
}

Explanation

1. Initialization: We start by creating a 2D array ans to store the index, start time, and end time of each activity.
2. Sorting: We sort the activities based on their end times using Arrays.sort and a custom comparator.
3. Selection: We initialize the maximum number of activities (maxAct) to 1 and add the first activity to our list. We then iterate through the sorted activities and select the next activity if its start time is greater than or equal to the end time of the last selected activity.
4. Output: Finally, we return the maximum number of activities that can be performed.

Time and Space Complexity Analysis

Let’s analyze the time and space complexity of the provided Java code for the Activity Selection Problem.

Time Complexity

1. Initialization:

   • Creating the ans array and populating it with start and end times takes (O(n)) time, where (n) is the number of activities.

2. Sorting:

   • Sorting the ans array based on end times using Arrays.sort takes (O(n \log n)) time.

3. Selection:

   • Iterating through the sorted activities to select the maximum number of non-overlapping activities takes (O(n)) time.

Combining these steps, the overall time complexity is dominated by the sorting step, resulting in: [ O(n \log n) ]

Space Complexity

1. Auxiliary Space:
   • The ans array requires (O(n)) space to store the start and end times of the activities.
   • The arr ArrayList used to store the indices of selected activities also requires (O(n)) space in the worst case.

Therefore, the overall space complexity is: [ O(n) ]

In summary, the time complexity of the code is (O(n \log n)) and the space complexity is (O(n)). This makes the algorithm efficient for solving the Activity Selection Problem with a large number of activities.

Conclusion

The greedy algorithm is a powerful tool for solving optimization problems like the Activity Selection Problem. By always choosing the next activity that finishes the earliest, we ensure that we can perform the maximum number of activities. This approach is both efficient and easy to implement.

Feel free to try out the code and see how it works with different sets of activities. Happy coding! 🚀

---

I hope this helps! If you have any questions or need further clarification, feel free to ask.