The Activity Selection Problem is a classic optimization problem that aims to select the maximum number of activities that don't overlap, given their start and end times.

Greedy Approach

The basic greedy approach involves sorting activities by their end times and iteratively selecting the next activity that starts after the last selected one ends.


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

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

public class ActivitySelection {
    public static void main(String[] args) {
        Activity[] activities = {new Activity(1, 3), new Activity(2, 4), new Activity(3, 5), new Activity(0, 6), new Activity(5, 7), new Activity(8, 9)};
        
        Arrays.sort(activities, Comparator.comparingInt(a -> a.end));
        
        int lastEndTime = -1;
        for (Activity activity : activities) {
            if (activity.start >= lastEndTime) {
                System.out.println("Activity selected: (" + activity.start + ", " + activity.end + ")");
                lastEndTime = activity.end;
            }
        }
    }
}

Output

The selected activities are those that maximize the number of non-overlapping activities:

Console Output:

(1, 3)
(3, 5)
(5, 7)
(8, 9)

Activity Selection with Weighted Intervals

Weighted Interval Scheduling

In this variant, each activity has a weight (or value), and the goal is to maximize the total weight of selected activities.


import java.util.Arrays;

class WeightedActivity {
    int start, end, weight;
    WeightedActivity(int start, int end, int weight) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }
}

public class WeightedActivitySelection {
    public static void main(String[] args) {
        WeightedActivity[] activities = {new WeightedActivity(1, 3, 5), new WeightedActivity(2, 5, 6), new WeightedActivity(4, 6, 5), new WeightedActivity(6, 7, 4), new WeightedActivity(5, 8, 11), new WeightedActivity(7, 9, 2)};
        
        Arrays.sort(activities, (a, b) -> a.end - b.end);
        
        int n = activities.length;
        int[] dp = new int[n];
        dp[0] = activities[0].weight;
        
        for (int i = 1; i < n; i++) {
            int includeWeight = activities[i].weight;
            int l = findNonConflictingActivity(activities, i);
            if (l != -1) {
                includeWeight += dp[l];
            }
            dp[i] = Math.max(includeWeight, dp[i - 1]);
        }
        
        System.out.println("Maximum weight of selected activities: " + dp[n - 1]);
    }
    
    private static int findNonConflictingActivity(WeightedActivity[] activities, int index) {
        for (int i = index - 1; i >= 0; i--) {
            if (activities[i].end <= activities[index].start) {
                return i;
            }
        }
        return -1;
    }
}

Output

The maximum weight of selected non-overlapping activities is computed using dynamic programming:

Console Output:

Maximum weight of selected activities: 17

Activity Selection with Time Slots

Time Slot Allocation

This type of problem involves selecting activities that fit into specific time slots, which may not be contiguous.


import java.util.Arrays;

class SlotActivity {
    int start, end;
    SlotActivity(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

public class SlotActivitySelection {
    public static void main(String[] args) {
        SlotActivity[] activities = {new SlotActivity(1, 4), new SlotActivity(3, 5), new SlotActivity(0, 6), new SlotActivity(5, 7), new SlotActivity(8, 9)};
        
        Arrays.sort(activities, (a, b) -> a.end - b.end);
        
        int lastEndTime = -1;
        for (SlotActivity activity : activities) {
            if (activity.start >= lastEndTime) {
                System.out.println("Activity selected: (" + activity.start + ", " + activity.end + ")");
                lastEndTime = activity.end;
            }
        }
    }
}

Output

Activities are selected based on fitting into available time slots without overlap:

Console Output:

(1, 4)
(5, 7)
(8, 9)

Activity Selection with Multiple Resources

Handling Multiple Resources

In scenarios where multiple resources are available, the problem involves assigning activities to resources such that the maximum number of activities are completed.


import java.util.PriorityQueue;
import java.util.Arrays;

class MultiResourceActivity {
    int start, end;
    MultiResourceActivity(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

public class MultiResourceActivitySelection {
    public static void main(String[] args) {
        MultiResourceActivity[] activities = {new MultiResourceActivity(1, 3), new MultiResourceActivity(2, 5), new MultiResourceActivity(4, 6), new MultiResourceActivity(6, 8), new MultiResourceActivity(5, 7)};
        
        Arrays.sort(activities, (a, b) -> a.start - b.start);
        
        PriorityQueue resourceQueue = new PriorityQueue<>();
        
        for (MultiResourceActivity activity : activities) {
            if (!resourceQueue.isEmpty() && resourceQueue.peek() <= activity.start) {
                resourceQueue.poll();
            }
            resourceQueue.add(activity.end);
            System.out.println("Resource allocated for activity: (" + activity.start + ", " + activity.end + ")");
        }
        
        System.out.println("Total resources used: " + resourceQueue.size());
    }
}

Output

The number of resources used is minimized by efficiently scheduling activities:

Console Output:

Resource allocated for activity: (1, 3)
Resource allocated for activity: (2, 5)
Resource allocated for activity: (4, 6)
Resource allocated for activity: (5, 7)
Resource allocated for activity: (6, 8)
Total resources used: 3

Activity Selection with Variable Durations

Variable Duration Activities

When activities have variable durations, the goal is to select a combination that fits within a given time frame while maximizing the number of activities.


import java.util.Arrays;

class VariableDurationActivity {
    int start, end, duration;
    VariableDurationActivity(int start, int end) {
        this.start = start;
        this.end = end;
        this.duration = end - start;
    }
}

public class VariableDurationActivitySelection {
    public static void main(String[] args) {
        VariableDurationActivity[] activities = {new VariableDurationActivity(1, 4), new VariableDurationActivity(3, 5), new VariableDurationActivity(0, 6), new VariableDurationActivity(5, 7), new VariableDurationActivity(8, 9)};
        
        Arrays.sort(activities, (a, b) -> a.duration - b.duration);
        
        int lastEndTime = -1;
        for (VariableDurationActivity activity : activities) {
            if (activity.start >= lastEndTime) {
                System.out.println("Activity selected: (" + activity.start + ", " + activity.end + ")");
                lastEndTime = activity.end;
            }
        }
    }
}

Output

Activities are selected based on minimizing overlaps and fitting within the available time:

Console Output:

(1, 4)
(5, 7)
(8, 9)