Activity Selection Problem

The problem, simply

You get n activities. Each one has a start time and a finish time. One person can do only one activity at a time, and cannot leave an activity halfway.

Give back the largest number of activities that person can do. Two activities fit together when the second one starts at or after the moment the first one finishes.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every possible group of activities. For each group, check that no two of them clash. Keep the biggest group that has no clash.

1. For each activity, choose "take it" or "leave it". That makes 2^n groups.
2. For a finished group, compare every pair. Two activities clash if one starts before the other ends, both ways.
3. Remember the biggest group with no clash.

class Solution {
    private int best = 0;

    public int activitySelection(int[] start, int[] finish) {
        best = 0;
        tryAll(start, finish, 0, new ArrayList<>());
        return best;
    }

    private void tryAll(int[] s, int[] f, int i, List<Integer> chosen) {
        if (i == s.length) {
            if (noClash(s, f, chosen)) best = Math.max(best, chosen.size());
            return;
        }
        chosen.add(i);                    // take activity i
        tryAll(s, f, i + 1, chosen);
        chosen.remove(chosen.size() - 1);
        tryAll(s, f, i + 1, chosen);      // leave activity i
    }

    private boolean noClash(int[] s, int[] f, List<Integer> chosen) {
        for (int x = 0; x < chosen.size(); x++) {
            for (int y = x + 1; y < chosen.size(); y++) {
                int a = chosen.get(x), b = chosen.get(y);
                boolean apart = f[a] <= s[b] || f[b] <= s[a];
                if (!apart) return false;
            }
        }
        return true;
    }
}

How long it takes: 2^n groups, and each check compares up to n^2 pairs, so O(2^n * n^2). Extra room: the chosen list and the recursion, O(n). Fine for 15 activities, hopeless for 50.

Way 2: the clever way

Do what the swing helper does. Sort the activities by finish time. Walk down the sorted list and keep a note of when the last kept activity ends.

1. Sort by finish time, earliest first.
2. Set lastEnd to minus infinity. Nothing is kept yet.
3. For each activity in that order: if it starts at or after lastEnd, keep it and set lastEnd to its finish. Otherwise skip it.
4. The number kept is the answer.

Why is this safe? Take any best plan. Its first activity ends at some time. The activity that ends earliest of all ends no later, so you can swap it in and nothing after it breaks. Repeat the same swap for the second pick, the third, and so on. This is called an exchange argument.

class Solution {
    public int activitySelection(int[] start, int[] finish) {
        int n = start.length;
        int[][] acts = new int[n][2];
        for (int i = 0; i < n; i++) {
            acts[i][0] = start[i];
            acts[i][1] = finish[i];
        }
        // whoever finishes first goes first
        Arrays.sort(acts, (a, b) -> Integer.compare(a[1], b[1]));

        int count = 0;
        long lastEnd = Long.MIN_VALUE;   // nothing kept yet
        for (int[] a : acts) {
            if (a[0] >= lastEnd) {       // starts after the last one ended
                count++;
                lastEnd = a[1];
            }
        }
        return count;
    }
}

How long it takes: sorting is O(n log n) and the walk is O(n), so O(n log n) in total. Extra room: the pairs array, O(n). If the input already comes sorted by finish time, the walk alone is O(n) with O(1) room.

Watch out for

• Touching rule. Check whether an activity that starts exactly when the last one ends is allowed. This page says yes (>=). Some judges, like the meetings version, say no (>).
• Subtracting in the comparator, a[1] - b[1], can overflow for big times. Use Integer.compare.
• Starting lastEnd at 0 breaks when an activity starts at a negative time or at 0 with the strict rule. Start it below every possible time.
• If you need the chosen activities and not only the count, keep their original numbers in the pairs before sorting.

What interviewers ask next

• Prove it is optimal. Exchange argument: the earliest finishing activity can replace the first pick of any best plan without breaking it, and the rest of the problem is the same problem on a smaller set.
• What if each activity has a value and you want the most value? Greedy breaks. Sort by finish, then use dynamic programming: best[i] = max(best[i-1], value[i] + best[p]), where p is the last activity that ends before i starts, found by binary search. O(n log n).
• How many rooms do you need to run all activities? Sort by start and keep a min heap of end times. The biggest size the heap reaches is the answer.
• Fewest activities to remove so the rest do not overlap? It is n minus this answer (LeetCode 435).
• Fewest arrows to burst balloons on a line? Same greedy: sort by end, shoot at the end of the first balloon, skip everything that arrow hits.

Remember this

Grown-up words: the swing turns are intervals, "ends soonest first" is the earliest finish time greedy rule, the swap proof is an exchange argument, and this whole problem is called interval scheduling.