GreedyProblem 1 of 35

Activity Selection Problem

Brute Force
Time: O(2^n)
Space: O(n)
Optimal
Time: O(n log n)
Space: O(1)

Problem Statement

Given n activities with their start and finish times, 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.

Constraints:

  • 1 ≤ n ≤ 10^5
  • 0 ≤ start[i] < finish[i] ≤ 10^9

Example:

  • Input: start = [1, 3, 0, 5, 8, 5], finish = [2, 4, 6, 7, 9, 9]
  • Output: 4
  • Explanation: Activities 0, 1, 3, and 4 can be selected (indices based on sorted order by finish time).

Example 2:

  • Input: start = [10, 12, 20], finish = [20, 25, 30]
  • Output: 1
  • Explanation: Only one activity can be performed as all overlap.

Approach 1: Brute Force (Recursion)

Intuition

Try all possible subsets of activities and find the maximum subset where no two activities overlap.

Algorithm

  1. Generate all possible subsets of activities
  2. For each subset, check if activities are non-overlapping
  3. Track the maximum size of valid subsets
  4. Two activities are compatible if one finishes before the other starts
java
import java.util.*;

public class Solution {
    private int maxCount = 0;
    
    private boolean isCompatible(int[][] activities, List<Integer> subset) {
        for (int i = 0; i < subset.size(); i++) {
            for (int j = i + 1; j < subset.size(); j++) {
                int a = subset.get(i), b = subset.get(j);
                // Check if activities overlap
                if (!(activities[a][1] <= activities[b][0] || 
                      activities[b][1] <= activities[a][0])) {
                    return false;
                }
            }
        }
        return true;
    }
    
    private void solve(int[][] activities, int idx, List<Integer> current) {
        if (idx == activities.length) {
            if (isCompatible(activities, current)) {
                maxCount = Math.max(maxCount, current.size());
            }
            return;
        }
        
        // Include current activity
        current.add(idx);
        solve(activities, idx + 1, current);
        current.remove(current.size() - 1);
        
        // Exclude current activity
        solve(activities, idx + 1, current);
    }
    
    public int activitySelection(int[] start, int[] finish) {
        int n = start.length;
        int[][] activities = new int[n][2];
        for (int i = 0; i < n; i++) {
            activities[i][0] = start[i];
            activities[i][1] = finish[i];
        }
        
        maxCount = 0;
        solve(activities, 0, new ArrayList<>());
        return maxCount;
    }
}

Complexity Analysis

  • Time Complexity: O(2^n) - We generate all possible subsets
  • Space Complexity: O(n) - Recursion stack and current subset storage

Approach 2: Greedy (Sort by Finish Time) - Optimal

Intuition

The greedy choice is to always select the activity that finishes earliest and is compatible with previously selected activities. This leaves maximum room for remaining activities.

Key Insight: By selecting the activity with the earliest finish time, we maximize the remaining time for other activities.

Algorithm

  1. Sort activities by finish time
  2. Select the first activity (earliest finish time)
  3. For each subsequent activity, if its start time >= last selected finish time, select it
  4. Count selected activities
java
import java.util.*;

public class ActivitySelection {
    public int maxActivities(int[] start, int[] finish) {
        int n = start.length;
        
        // Create activities array: [finish, start, index]
        int[][] activities = new int[n][3];
        for (int i = 0; i < n; i++) {
            activities[i][0] = finish[i];
            activities[i][1] = start[i];
            activities[i][2] = i;
        }
        
        // Sort by finish time
        Arrays.sort(activities, (a, b) -> a[0] - b[0]);
        
        int count = 1;  // First activity is always selected
        int lastFinish = activities[0][0];
        
        for (int i = 1; i < n; i++) {
            int currentStart = activities[i][1];
            int currentFinish = activities[i][0];
            
            // If current activity starts after last selected finishes
            if (currentStart >= lastFinish) {
                count++;
                lastFinish = currentFinish;
            }
        }
        
        return count;
    }
    
    public List<Integer> getSelectedActivities(int[] start, int[] finish) {
        int n = start.length;
        
        int[][] activities = new int[n][3];
        for (int i = 0; i < n; i++) {
            activities[i][0] = finish[i];
            activities[i][1] = start[i];
            activities[i][2] = i;
        }
        
        Arrays.sort(activities, (a, b) -> a[0] - b[0]);
        
        List<Integer> selected = new ArrayList<>();
        selected.add(activities[0][2]);
        int lastFinish = activities[0][0];
        
        for (int i = 1; i < n; i++) {
            if (activities[i][1] >= lastFinish) {
                selected.add(activities[i][2]);
                lastFinish = activities[i][0];
            }
        }
        
        return selected;
    }
    
    public static void main(String[] args) {
        ActivitySelection as = new ActivitySelection();
        int[] start = {1, 3, 0, 5, 8, 5};
        int[] finish = {2, 4, 6, 7, 9, 9};
        System.out.println(as.maxActivities(start, finish));  // Output: 4
    }
}

Dry Run Example

Activities: Index: 0 1 2 3 4 5 Start: 1 3 0 5 8 5 Finish:2 4 6 7 9 9 After sorting by finish time: Activity: (1,2) (3,4) (0,6) (5,7) (8,9) (5,9) Index: 0 1 2 3 4 5 Step 1: Select activity 0 (1,2). last_finish = 2, count = 1 Step 2: Activity 1 (3,4). start=3 >= 2. Select! last_finish = 4, count = 2 Step 3: Activity 2 (0,6). start=0 < 4. Skip. Step 4: Activity 3 (5,7). start=5 >= 4. Select! last_finish = 7, count = 3 Step 5: Activity 4 (8,9). start=8 >= 7. Select! last_finish = 9, count = 4 Step 6: Activity 5 (5,9). start=5 < 9. Skip. Result: 4 activities selected Timeline: [1-2] [3-4] [5-7] [8-9] 0 1 3 4

Complexity Analysis

  • Time Complexity: O(n log n) - Dominated by sorting
  • Space Complexity: O(n) for storing activities (can be O(1) if we sort in place)

Why Greedy Works

Proof by Exchange Argument:

  1. Let OPT be any optimal solution
  2. Let G be our greedy solution
  3. If the first activity in G differs from OPT, we can replace OPT's first activity with G's (which finishes earlier), without losing any activities
  4. This exchange doesn't reduce the number of activities
  5. By induction, greedy solution is optimal

Greedy Choice Property: The activity with earliest finish time is always part of some optimal solution.

Key Takeaways

  1. Greedy by Finish Time: Sort by finish time, not start time or duration
  2. Why Finish Time? Earliest finish leaves maximum room for other activities
  3. Compatibility Check: Activity is compatible if start >= last finish
  4. First is Free: First activity (earliest finish) is always selected
  5. Classic Interval Scheduling: This is the foundation for many scheduling problems
  6. Similar Problems: Meeting Rooms, Non-overlapping Intervals, Maximum Meetings
  7. Extension: Can be extended to weighted activities using DP
Next
Job Sequencing Problem