Activity Selection Algorithm
The Activity Selection Problem arises in various scenarios, such as scheduling tasks, managing resources, and organizing events. The goal is to select a maximum number of activities that do not overlap, maximizing efficiency and utilization of resources.
The Activity Selection Problem can be efficiently solved using a greedy approach. At each step, the algorithm selects the activity with the earliest finish time that does not conflict with previously selected activities.
function activitySelection(startTimes, finishTimes) {
const activities = [];
const n = startTimes.length;
// Sort activities by finish time
const sortedActivities = [];
for (let i = 0; i < n; i++) {
sortedActivities.push({ start: startTimes[i], finish: finishTimes[i] });
}
sortedActivities.sort((a, b) => a.finish - b.finish);
// Select activities greedily
let prevFinish = 0;
for (const activity of sortedActivities) {
if (activity.start >= prevFinish) {
activities.push(activity);
prevFinish = activity.finish;
}
}
return activities;
}
// Example usage:
const startTimes = [1, 3, 0, 5, 8, 5];
const finishTimes = [2, 4, 6, 7, 9, 9];
console.log("Selected Activities:", activitySelection(startTimes, finishTimes));The Activity Selection Problem has real-world applications in scheduling meetings, organizing conferences, and optimizing resource allocation in project management, where maximizing productivity and minimizing conflicts are essential.