Skip to main content
Interval Scheduling

Activity Selection

Sort intervals by end time. Always pick the earliest-ending interval that doesn't overlap with the last picked one. This leaves maximum room for future intervals. Proven optimal by exchange argument.

O(n log n)
·
O(1)

How It Works

Activity Selection maximizes the number of non-overlapping intervals. Sort by end time and greedily take every interval that starts at or after the last selected interval's end. The exchange argument proves optimality: among all remaining compatible intervals, the earliest-ending one leaves the most room afterward, so any optimal solution can be rewritten to include it without losing activities.

Sorting dominates at O(n log n); the selection pass is a single O(n) sweep with O(1) extra state. Contrast this with weighted interval scheduling, where intervals have values and the greedy rule fails — that version needs DP with binary search. The complement view also matters: minimum intervals to remove for a conflict-free set equals n minus the maximum kept.

Step-by-Step Visualization

Select max non-overlapping activities
1
0
4
1
3
2
5
3
0
4
6
5
5
6
7
7
5
8
9
9
8
10
9
11
Sorted by end[1,4],[3,5],[0,6],[5,7],[5,9],[8,9]
1/3

Code

Java
static List<int[]> activitySelection(int[][] activities) {
  Arrays.sort(activities, (a, b) -> a[1] - b[1]);
  List<int[]> result = new ArrayList<>();
  result.add(activities[0]);
  int lastEnd = activities[0][1];

  for (int i = 1; i < activities.length; i++) {
    if (activities[i][0] >= lastEnd) {
      result.add(activities[i]);
      lastEnd = activities[i][1];
    }
  }
  return result;
}

Tips & Gotchas

1Sort by end time (greedy: earliest finish leaves most room)
2Always pick the earliest-ending activity that doesn't conflict
3This greedy choice is provably optimal

Practice Problems

  • 1Non-overlapping Intervals
  • 2Maximum Length of Pair Chain
  • 3Minimum Number of Arrows to Burst Balloons
  • 4Maximum Number of Events That Can Be Attended

About the Interval Scheduling Pattern

Choose the maximum number of non-overlapping intervals, or schedule activities with minimum resources. The key insight: sorting by end time lets you make optimal local choices that are globally correct.

Key insight

Greedy is NOT 'try the obvious thing'. It works only when local optimality guarantees global optimality. Sort first (by end time, deadline, ratio), then pick greedily. If greedy fails, try DP.

Common Greedy Interview Problems

  • Jump Game
  • Activity Selection
  • Meeting Rooms II
  • Gas Station
  • Candy
  • Task Scheduler
  • Partition Labels

Frequently Asked Questions

Why sort by end time and not by start time or duration?

Finishing earliest preserves the maximum remaining timeline for future picks, and an exchange argument makes this rigorous. Sorting by start time or by shortest duration both admit counterexamples where a long early interval or a centrally placed short one blocks two others.

What breaks when intervals carry weights?

With values attached, taking the earliest-ending interval can sacrifice a single high-value interval for several low-value ones. Weighted interval scheduling requires DP: sort by end time and choose max(skip, value + best among intervals ending before this start), found via binary search.

How should ties and touching endpoints be handled?

Decide whether [1,3] and [3,5] conflict — most problems treat a shared endpoint as non-overlapping, so use start >= lastEnd. Misreading this convention flips comparisons from >= to > and produces off-by-one answers on adjacent intervals.