Activity Selection Problem
Greedy strategy: Always select the next activity that finishes earliest.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#0(1 - 4)
#1(3 - 5)
#2(0 - 6)
#3(5 - 7)
#4(3 - 9)
#5(5 - 9)
#6(6 - 10)
#7(8 - 11)
#8(8 - 12)
#9(2 - 14)
#10(12 - 16)
Status: Ready
Speed
Algorithm Logic
1function activitySelection(activities):
2 // 1. Sort by finish time
3 activities.sort((a,b) => a.end - b.end)
4
5 last_end = activities[0].end
6 selected = [activities[0]]
7
8 for i from 1 to n:
9 if activities[i].start >= last_end:
10 selected.push(activities[i])
11 last_end = activities[i].end
12
13 return selected
Visualizing the selection process. Notice how activities are first sorted by their end times.