Greedy Algorithms – Optimal Solutions with Simple Approaches

Day 27: Greedy Algorithms – Optimal Solutions with Simple Approaches

Greedy algorithms are designed to make the optimal choice at each step, aiming for an overall optimal solution.

Activity Selection Problem (Greedy Approach)

javaCopy codeimport java.util.*;

public class ActivitySelection {
    public static List<Integer> selectActivities(int[] start, int[] finish) {
        int n = start.length;
        List<Integer> selectedActivities = new ArrayList<>();
        
        // Sort activities based on their finish time
        Integer[] indices = new Integer[n];
        for (int i = 0; i < n; i++) {
            indices[i] = i;
        }
        Arrays.sort(indices, (i, j) -> finish[i] - finish[j]);

        int lastFinishTime = -1;
        for (int i : indices) {
            if (start[i] >= lastFinishTime) {
                selectedActivities.add(i);
                lastFinishTime = finish[i];
            }
        }
        return selectedActivities;
    }

    public static void main(String[] args) {
        int[] start = {1, 3, 0, 5, 8, 5};
        int[] finish = {2, 4, 6, 7, 9, 9};
        List<Integer> selectedActivities = selectActivities(start, finish);
        System.out.println("Selected activities: " + selectedActivities);
    }
}