Pattern visualizer

Activity Selection Problem

Among all activities that don't conflict with what's already picked, the one that ends soonest always leaves the most room for future picks — it can never do worse than any other valid choice. So sort by end time once, then greedily take any activity whose start doesn't collide with the last one taken; no backtracking is ever needed. Animated on: activities = (1,2),(3,4),(0,6),(5,7),(5,9),(8,9) — pick the maximum number of non-overlapping activities..

Sort by end time, always take what finishes soonest

time O(n log n)space O(n)step 1 / 8

(1,2)

[0]

(3,4)

[1]

(0,6)

[2]

(5,7)

[3]

(5,9)

[4]

(8,9)

[5]

line 2

Sort activities by END time: (1,2), (3,4), (0,6), (5,7), (5,9), (8,9). Picking whichever finishes earliest always leaves the most room for what's left.

Pseudocode

1FUNCTION activitySelection(activities):
2  sort activities by end time
3  selected = empty list, lastEnd = negative infinity
4  FOR each activity with start and end in activities:
5    IF start >= lastEnd:
6      add [start, end] to selected   (no overlap)
7      lastEnd = end
8  RETURN selected

← / → step · space play · Home restart

Where to practice Greedy

Practice Greedy problems All Greedy problems Back to roadmap