Challenge - 5 Problems
Activity Selection Master
Get all challenges correct to earn this badge!
Test your skills under time pressure!
❓ Predict Output
intermediate2:00remaining
Output of Activity Selection Algorithm
What is the output of the following JavaScript code that selects the maximum number of non-overlapping activities?
DSA Javascript
function activitySelection(start, end) {
const n = start.length;
let selected = [];
let i = 0;
selected.push(i);
for (let j = 1; j < n; j++) {
if (start[j] >= end[i]) {
selected.push(j);
i = j;
}
}
return selected;
}
const start = [1, 3, 0, 5, 8, 5];
const end = [2, 4, 6, 7, 9, 9];
console.log(activitySelection(start, end));Attempts:
2 left
💡 Hint
Remember the greedy approach selects the first activity and then picks the next activity whose start time is greater or equal to the last selected activity's end time.
✗ Incorrect
The code selects activities by earliest finishing time. It starts with activity 0, then picks activity 1 (start 3 >= end 2), then activity 3 (start 5 >= end 4), then activity 4 (start 8 >= end 7). So selected indices are [0,1,3,4].
🧠 Conceptual
intermediate1:30remaining
Understanding the Greedy Choice in Activity Selection
Why does the greedy algorithm for the Activity Selection Problem always pick the activity with the earliest finishing time first?
Attempts:
2 left
💡 Hint
Think about how finishing early affects the possibility of selecting more activities later.
✗ Incorrect
Selecting the activity that finishes earliest frees up time to select more activities afterward, maximizing the total number of non-overlapping activities.
❓ Predict Output
advanced2:00remaining
Output with Unsorted Activities
What will be the output of this code when the activities are not sorted by their finishing times?
DSA Javascript
function activitySelectionUnsorted(start, end) {
const n = start.length;
let activities = [];
for (let i = 0; i < n; i++) {
activities.push({start: start[i], end: end[i], index: i});
}
let selected = [];
let i = 0;
selected.push(activities[i].index);
for (let j = 1; j < n; j++) {
if (activities[j].start >= activities[i].end) {
selected.push(activities[j].index);
i = j;
}
}
return selected;
}
const start = [1, 3, 0, 5, 8, 5];
const end = [2, 4, 6, 7, 9, 9];
console.log(activitySelectionUnsorted(start, end));Attempts:
2 left
💡 Hint
The activities are not sorted by finishing time, so the greedy approach may fail to select the maximum set.
✗ Incorrect
Without sorting by finishing time, the code picks activities in input order. It selects activity 0, then activity 3 (start 5 >= end 2), then activity 4 (start 8 >= end 7). So selected indices are [0,3,4].
🔧 Debug
advanced2:00remaining
Identify the Bug in Activity Selection Code
What error will this code produce when run, and why?
DSA Javascript
function activitySelectionBug(start, end) {
const n = start.length;
let selected = [];
let i = 0;
selected.push(i);
for (let j = 1; j < n; j++) {
if (start[j] > end[i]) {
selected.push(j);
i = j;
}
}
return selected;
}
const start = [1, 3, 0, 5, 8, 5];
const end = [2, 4, 6, 7, 9, 9];
console.log(activitySelectionBug(start, end));Attempts:
2 left
💡 Hint
Check the condition for selecting the next activity carefully.
✗ Incorrect
The condition uses '>' instead of '>=' so it misses activities starting exactly at the previous end time. Activity 1 starts at 3, previous end is 2, so selected. Activity 3 starts at 5, previous end is 4, so selected. Activity 4 starts at 8, previous end is 7, selected. Activity 5 starts at 5, previous end is 9, not selected. So selected are [0,1,4].
🚀 Application
expert3:00remaining
Maximum Number of Activities with Additional Constraints
Given activities with start and end times, and a mandatory rest time of 1 unit after each activity, which code modification correctly selects the maximum number of activities?
DSA Javascript
function activitySelectionWithRest(start, end) {
const n = start.length;
let selected = [];
let i = 0;
selected.push(i);
for (let j = 1; j < n; j++) {
if (start[j] >= end[i] + 1) {
selected.push(j);
i = j;
}
}
return selected;
}
const start = [1, 3, 0, 5, 8, 5];
const end = [2, 4, 6, 7, 9, 9];
console.log(activitySelectionWithRest(start, end));Attempts:
2 left
💡 Hint
Remember the greedy algorithm requires sorting by finishing time and the rest time affects the selection condition.
✗ Incorrect
To handle rest time, the condition must ensure the next activity starts at least 1 unit after the previous ends. Also, sorting by finishing time is necessary for the greedy approach to work correctly.