Activity Selection

Intuition

Greedy: among all activities compatible with the last selected one, always pick the one that finishes earliest. This leaves maximum room for future activities. Sort by end time first.

Algorithm

1Sort activities by end time.
2Select activity 0. lastEnd = end[0], count = 1.
3For i from 1 to nâˆ’1: if start[i] >= lastEnd: select it, count++, lastEnd = end[i].
4Return count.

Example Walkthrough

Input: start=[1,3,0,5,8,5], end=[2,4,6,7,9,9]

1.Sort by end: (1,2),(3,4),(0,6),(5,7),(8,9),(5,9). Select (1,2). lastEnd=2.
2.Select (3,4). lastEnd=4. Skip (0,6): 0<4. Select (5,7). lastEnd=7. Select (8,9). count=4.

Output: 4

Common Pitfalls

•Sort by END time, not start time â€” a greedy on start times is incorrect.

Activity Selection.java

Java

// Approach: Greedy. Sort activities by finish time.
// Always pick the next activity that starts after the last selected one ends.
// Time: O(n log n) Space: O(1)
import java.util.*;

class Solution {
    public int activitySelection(int[] start, int[] finish) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);

        for (int i = 0; i < start.length; ++i)
            pq.offer(new int[] { start[i], finish[i] });

        int cnt = 1;
        int ans = pq.peek()[1];

        while (!pq.isEmpty()) {
            if (pq.peek()[0] > ans) {
                cnt++;
                ans = pq.peek()[1];
            }
            pq.poll();
        }
        return cnt;
    }
}

Was this solution helpful?