Activity Selection — The Canonical Greedy Proof

The algorithm

Arrays.sort(activities, (a, b) -> a[1] - b[1]);
int count = 0, lastEnd = -1;
for (int[] a : activities) {
  if (a[0] >= lastEnd) {
    count++;
    lastEnd = a[1];
  }
}

Why earliest-ending is optimal

Exchange argument: any optimal solution's first activity can be replaced with earliest-ending without loss. Repeat.

Complexity

O(N log N) for sort. O(N) for scan. Beat DP's O(N²) or O(N × time) approaches.

Weighted variant

Activities have values. Now greedy fails — need DP with binary search.