Activity Selection Problem in Java with Examples

The Activity Selection Problem in Java is a fascinating algorithm topic worth diving into. Why? Because understanding it helps in efficiently scheduling activities or tasks—think meeting room allocations or job scheduling. By mastering this, you can tackle various optimisation issues. Curious to know more? Keep reading to unravel its real-world applications!

What is ‘Activity Selection Problem in Java’?

So, what on earth is the “Activity Selection Problem in Java”? It’s actually a fascinating concept in computer science, which deals with selecting the maximum number of non-overlapping activities from a set. The idea is pretty simple: given a list of activities with their start and end times, the goal is to schedule the maximum number of activities without clashes. In the realm of Java programming, this problem is typically tackled using greedy algorithms. You’ll start by sorting activities based on their finish times and then iteratively pick them if they don’t overlap. Simple yet incredibly useful, isn’t it?

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

public class ActivitySelection {
    public static void main(String[] args) {
        int[][] activities = {{1, 3}, {2, 5}, {4, 6}};
        Arrays.sort(activities, Comparator.comparingInt(a -> a[1]));
        // Perform activity selection algorithm and print selected activities
    }
}

Java Code Example

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

public class ActivitySelection {

    public static void printMaxActivities(int[] start, int[] finish, int n) {
        Activity[] activities = new Activity[n];
        for (int i = 0; i < n; i++) {
            activities[i] = new Activity(start[i], finish[i]);
        }

        Arrays.sort(activities, Comparator.comparingInt(a -> a.finish));

        System.out.println("Selected activities:");

        int i = 0;
        System.out.print("(" + activities[i].start + ", " + activities[i].finish + ")");
        
        for (int j = 1; j < n; j++) {
            if (activities[j].start >= activities[i].finish) {
                System.out.print(", (" + activities[j].start + ", " + activities[j].finish + ")");
                i = j;
            }
        }
    }
    
    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};
        int n = start.length;

        printMaxActivities(start, finish, n);
    }
}

Explanation of the Code

You create an array of Activity objects to store start and finish times.
The activities are sorted by their finishing time in ascending order.
The first activity (earliest finish) is always selected.

You loop through the remaining activities, and each time you check if the current activity’s start time is greater than or equal to the finish time of the last selected one.
If it is, you select it and update the tracker to the current activity.
Finally, the program prints all selected activities.

This step-by-step selection process demonstrates the greedy method, since it always picks the activity that leaves maximum room for upcoming tasks.

Output

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

Real-life Applications of the Activity Selection Problem in Java

Event Scheduling at Netflix
Netflix uses the Activity Selection Problem in Java to plan content release schedules. By efficiently choosing the most profitable time slots for shows and movies, they maximise viewer engagement and subscription retention.
```
// Java code snippet
    List activities = Arrays.asList(
        new Activity(1, 4), new Activity(2, 6),
        new Activity(5, 7), new Activity(8, 9)
    );
    // Call function to select activities
    ActivitySelection.selectActivities(activities);
    
```
Output: Optimal schedule with selected shows timings.

Task Management at Uber
Uber applies the Activity Selection Problem to allocate drivers and cars for overlapping ride requests efficiently. By optimizing the selection of jobs, they maximise the number of rides completed per day.

// Java code snippet
    List activities = Arrays.asList(
        new Activity(0, 3), new Activity(4, 5),
        new Activity(6, 8), new Activity(9, 11)
    );
    // Call function to select activities
    ActivitySelection.selectActivities(activities);

Output: List of time slots for ride completion.

Classroom Scheduling at Google
Google uses it to optimise the scheduling of internal training sessions. By selecting non-overlapping training sessions, they ensure that employees can attend maximum programs without conflicts.

// Java code snippet
    List activities = Arrays.asList(
        new Activity(1, 5), new Activity(5, 6),
        new Activity(6, 9), new Activity(7, 10)
    );
    // Call function to select activities
    ActivitySelection.selectActivities(activities);

Output: List of maximised training sessions.

Interview Questions Guide

What is the Activity Selection Problem?
It’s a classic problem in computer science where you need to choose the maximum number of activities that don’t overlap, given a set of activities with start and end times.

Why is the Activity Selection Problem considered a greedy algorithm?
The greedy algorithm is used because by always selecting the next possible activity that ends the earliest, you can maximize the number of activities.

How do you handle activities with the same end time?
When activities have the same end time, you can choose any one of them, as their start times determine the next possible selections.

Can this problem be solved using dynamic programming?
Although dynamic programming could solve it, it’s less efficient, as the greedy approach suffices for this problem’s linear structure.

What real-world problems can the Activity Selection Problem solve?
It’s useful in scenarios like scheduling meetings, events, or tasks where resources are restricted to non-overlapping time frames.

Discover the future of coding with our AI-powered java online compiler. Instantly write, run, and test your Java code with the aid of our intelligent algorithms. Save time and see results immediately, enhancing your learning experience and coding efficiency like never before. Embrace innovation in your programming journey.

Conclusion

Activity Selection Problem in Java enhances logical thinking, boosts problem-solving abilities, and offers insightful practice in algorithms and data structures. Tackle it yourself and witness the sense of achievement firsthand. For more programming insights, explore Newtum. Embrace the coding journey; it’s rewarding and enriching!

Edited and Compiled by

This article was compiled and edited by @rasikadeshpande, who has over 4 years of experience in writing. She’s passionate about helping beginners understand technical topics in a more interactive way.