Type the greedy activity selector (CLRS GREEDY-ACTIVITY-SELECTOR)

Answer

GREEDY-ACTIVITY-SELECTOR(s, f, n) A = {a[1]} k = 1 for m = 2 to n if s[m] >= f[k] A = A union {a[m]} k = m return A

Activities are assumed pre-sorted so f[1] <= f[2] <= ... <= f[n]. k tracks the most recently selected activity; f[k] is the latest finish time chosen so far. The test s[m] >= f[k] checks compatibility with the whole selected set at once. The loop is Theta(n) after the O(n lg n) sort.