Activity Selection

Given activities with start and finish times, select the maximum number of non-overlapping activities. The classic greedy solution sorts by earliest finish time and greedily picks compatible activities. This lesson covers the algorithm, proof sketch, LeetCode 435 variant, and implementations in C, Java, and Python with trace tables.

Overview

Each activity occupies a half-open interval [start, finish) on a timeline. Two activities overlap if one starts before the other finishes. The goal is to pack as many activities as possible into the schedule.

Timeline (example):

  0    1    2    3    4    5    6    7    8    9
  |----A----|
       |--B--|
  |--------C--------|
                 |--D--|
                          |-E-|

Greedy (sort by finish): pick A, D, E → 3 activities

Problem Statement

Input: n activities, each with start[i] and finish[i] where start[i] < finish[i].

Output: Maximum count of activities that can be performed by a single person (no two selected activities overlap).

Overlap rule: Activities i and j are compatible if start[j] >= finish[i] (assuming we process in order and the previous activity finished first).

Complexity target: O(n log n) time for sorting + O(n) scan; O(n) extra space if storing selected activities.

Greedy Algorithm

1. Sort activities by increasing finish time.
2. Select the first activity (earliest finish).
3. For each remaining activity, if start >= last_selected_finish, select it and update last_selected_finish.

Why Greedy Works

Exchange argument (sketch): Let g be the first activity in the greedy solution (minimum finish time). Let O be any optimal solution. If O does not include g, replace its first activity with g — since g finishes no later, nothing else is blocked. Repeat on the remaining subproblem. Hence greedy is optimal.

Code (C, Java, Python)

Python

def activity_selection(activities):
    """Max non-overlapping activities — sort by finish time. O(n log n)."""
    activities = sorted(activities, key=lambda x: x[1])
    count = 0
    last_end = float('-inf')
    selected = []

    for start, finish in activities:
        if start >= last_end:
            count += 1
            last_end = finish
            selected.append((start, finish))

    return count, selected


if __name__ == "__main__":
    acts = [(1, 4), (3, 5), (0, 6), (5, 7), (8, 9)]
    c, sel = activity_selection(acts)
    print(f"count = {c}, selected = {sel}")  # 3, [(1,4), (5,7), (8,9)]

Java

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

public class ActivitySelection {

    /** Sort by finish time; greedily pick compatible activities. */
    public static int maxActivities(int[][] activities) {
        Arrays.sort(activities, Comparator.comparingInt(a -> a[1]));
        int count = 0;
        int lastEnd = Integer.MIN_VALUE;

        for (int[] act : activities) {
            int start = act[0], finish = act[1];
            if (start >= lastEnd) {
                count++;
                lastEnd = finish;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[][] acts = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {8, 9}};
        System.out.println(maxActivities(acts)); // 3
    }
}

C

#include <stdio.h>
#include <stdlib.h>

typedef struct { int start, finish; } Activity;

int cmp_finish(const void *a, const void *b) {
    return ((Activity *)a)->finish - ((Activity *)b)->finish;
}

int activity_selection(Activity acts[], int n) {
    qsort(acts, n, sizeof(Activity), cmp_finish);
    int count = 0, i, last_end = -1000000;

    for (i = 0; i < n; i++) {
        if (acts[i].start >= last_end) {
            count++;
            last_end = acts[i].finish;
        }
    }
    return count;
}

int main(void) {
    Activity acts[] = {{1, 4}, {3, 5}, {0, 6}, {5, 7}, {8, 9}};
    printf("%d\n", activity_selection(acts, 5)); /* 3 */
    return 0;
}

Output & Trace

Program output

Greedy trace — [(1,4), (3,5), (0,6), (5,7), (8,9)]

LeetCode 435 — Non-overlapping Intervals

Problem: Given intervals, find the minimum number of intervals to remove so the rest are non-overlapping.

Reduction: removals = n - max_non_overlapping. Use the same greedy (sort by end, pick compatible).

def erase_overlap_intervals(intervals):
    """LeetCode 435 — min removals for non-overlapping set."""
    if not intervals:
        return 0
    intervals.sort(key=lambda x: x[1])
    kept = 1
    last_end = intervals[0][1]
    for start, finish in intervals[1:]:
        if start >= last_end:
            kept += 1
            last_end = finish
    return len(intervals) - kept

Example: [[1,2],[2,3],[3,4],[1,3]] → keep 3, remove 1.

Variants & Related Problems

Approach Comparison

Real-Life Applications

Interview Tips

1. State upfront: sort by finish time, then greedy scan.
2. Clarify overlap: is [1,2] and [2,3] overlapping? Usually no if condition is start >= last_end.
3. For LeetCode 435, say answer = n - max_kept using the same loop.
4. Mention exchange argument in one sentence if asked for proof.
5. If weights are given, switch to DP — greedy by finish alone fails.
6. Connect to greedy introduction and job sequencing (deadline-based variant).