Given activities with start/end times, the greedy strategy that maximizes the number of activities selects activities sorted by which attribute? (1 = start time, 2 = end time)
Given activities with start/end times, the greedy strategy that maximizes the number of activities selects activities sorted by which attribute? (1 = start time, 2 = end time)
Answer
2
Theory
Activity selection: pick the activity that finishes first, then recursively solve the rest.
Solution
Sorting by end time and greedily picking compatible activities is optimal.