DSA Tracker

Visualize

Activity Selection

Sort by end time, always take what finishes soonest

time O(n log n)space O(n)

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.

Details

Animated on: activities = (1,2),(3,4),(0,6),(5,7),(5,9),(8,9) — pick the maximum number of non-overlapping activities.

Problem:Activity SelectionMedium

Sort by end time, always take what finishes soonest

step 1 / 8

(1,2)
[0]
(3,4)
[1]
(0,6)
[2]
(5,7)
[3]
(5,9)
[4]
(8,9)
[5]

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

Every step in words

Show all 8 steps
  1. 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.
  2. (1,2): starts at 1 >= lastEnd(none yet) — no overlap, pick it. lastEnd = 2.
  3. (3,4): starts at 3 >= lastEnd(2) — no overlap, pick it. lastEnd = 4.
  4. (0,6): starts at 0 < lastEnd(4) — overlaps the last pick, skip it.
  5. (5,7): starts at 5 >= lastEnd(4) — no overlap, pick it. lastEnd = 7.
  6. (5,9): starts at 5 < lastEnd(7) — overlaps the last pick, skip it.
  7. (8,9): starts at 8 >= lastEnd(7) — no overlap, pick it. lastEnd = 9.
  8. Selected 4 non-overlapping activities: (1,2), (3,4), (5,7), (8,9).

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Activity Selection in the editorAll Greedy problemsBack to roadmap