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.