Activity Selection
The activity selection problem selects the maximum number of non-overlapping activities given start and finish times. It is a classic greedy problem where we always pick the activity with the earliest finish time.
Algorithm: Sort activities by finish time. Then iterate, picking an activity if its start time ≥ finish time of last picked.
Java implementation:
public static int activitySelection(int[] start, int[] finish) {
// Assume activities are sorted by finish time
int count = 1;
int lastFinish = finish[0];
for (int i = 1; i < start.length; i++) {
if (start[i] >= lastFinish) {
count++;
lastFinish = finish[i];
}
}
return count;
}
Time complexity: O(n log n) for sorting, O(n) for selection.
Two Minute Drill
- Activity selection maximizes number of non-overlapping activities.
- Greedy: pick activity with earliest finish time.
- Sort by finish time, then iterate.
- Time O(n log n).
Need more clarification?
Drop us an email at career@quipoinfotech.com