Published by Dimitris Kougioumtzis · Updated
Select the earliest finishing compatible activity.
Choose compatible intervals by earliest finish time, preserving the most room for later choices.
When to use Activity selection
Maximum-count scheduling with equal-value activities.
Choosing an alternative
Weighted interval scheduling optimizes reward and needs a different method.
Worked example: input and state changes
Example input
1,4; 3,5; 0,6; 5,7; 8,9; 5,9
These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.
Step 0: Initial state.
State at this checkpoint
{ "values": [ "1–4", "3–5", "0–6", "5–7", "8–9", "5–9" ], "active": [] }Step 2: Skip overlapping activity 3–5.
State at this checkpoint
{ "values": [ "1–4", "3–5", "0–6", "5–7", "8–9", "5–9" ], "active": [ 1 ], "selected": [ 0 ] }Step 4: Accept activity 5–7.
State at this checkpoint
{ "values": [ "1–4", "3–5", "0–6", "5–7", "8–9", "5–9" ], "active": [ 3 ], "selected": [ 0, 3 ] }Step 5: Accept activity 8–9.
State at this checkpoint
{ "values": [ "1–4", "3–5", "0–6", "5–7", "8–9", "5–9" ], "active": [ 4 ], "selected": [ 0, 3, 4 ] }Step 7: Selected 3 mutually compatible activities.
State at this checkpoint
{ "values": [ "1–4", "3–5", "0–6", "5–7", "8–9", "5–9" ], "active": [ 0, 3, 4 ] }
Expected final state
Selected 3 mutually compatible activities.
Complexity and input bounds
Family: Greedy. Time complexity: O(n log n).
Implementation detail: The trace uses a comparison sort. The portable reference orders activities by insertion sorting, so its worst-case preparation is O(n squared).
Space complexity: O(n) interval ordering and result storage.
Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.
Up to 16 start,end pairs separated by semicolons; 0 ≤ start < end ≤ 99.
The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.
Common mistakes and limitations
Touching endpoints follow the stated compatibility rule; weighted rewards break this greedy objective.
Further reading
For background on algorithm analysis and the JavaScript function interface:
- MIT OpenCourseWare: algorithm design and analysis foundations
- MDN: JavaScript function parameters and return values
Editorial and testing approach · Browse all algorithm guides
Complete JavaScript implementation
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 | // Nonnegative starts < ends. Sorts both arrays by finish time; selected receives sorted indices. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation. function algorithm(starts, ends, n, selected) { for (let i = 1; i < n; i++) { let j = i; while (j > 0 && ends[j - 1] > ends[j]) { let t = ends[j]; ends[j] = ends[j - 1]; ends[j - 1] = t; t = starts[j]; starts[j] = starts[j - 1]; starts[j - 1] = t; j--; } } let last = -1; let count = 0; for (let i = 0; i < n; i++) { if (starts[i] >= last) { selected[count++] = i; last = ends[i]; } } return count; } |
Source
No original paper has been verified for this entry. This source is a reference text or teaching reference, not an asserted original publication.
- Overview and Interval Scheduling (Lecture 1, 6.046J)
MIT OpenCourseWare (2015). Teaching reference.