Activity selection
Medium TimeO(n log n) SpaceO(n)
Each activity is a pair of times, its start before its end, and one person has to attend them. Two clash when they overlap, though one ending exactly as another begins is fine. Given activities, in no particular order, return the largest set that can all be attended.
Examples
Example 1
- Input
- activities = [[1, 4], [3, 5], [0, 6], [5, 7], [8, 9], [5, 9]]
- Output
- Three fit:
[[1,4],[5,7],[8,9]][1, 4]then[5, 7]starting after 4, then[8, 9]starting after 7.
Example 2
- Input
- activities = [[1, 4], [2, 5], [3, 6]]
- Output
- All three overlap each other, so only one of them can be attended.
[[1,4]]
The Code
function selectActivities(activities) {
const sorted = activities.slice().sort((a, b) => a[1] - b[1]);
const chosen = [];
let lastEnd = -Infinity;
for (let i = 0; i < sorted.length; i++) {
const start = sorted[i][0];
const end = sorted[i][1];
if (start >= lastEnd) {
chosen.push(sorted[i]);
lastEnd = end;
}
}
return chosen;
}
selectActivities([[1, 4], [3, 5], [0, 6], [5, 7], [8, 9], [5, 9]]);Done