Activity Selection Problem

You are given N activities with their start and finish times. Select the maximum number of activities that can be performed by a single person, assuming that a person can only work on a single activity at a time.

The Greedy Choice Principle

The greedy choice is to always pick the next activity whose finish time is least among the remaining activities, and whose start time is greater than or equal to the finish time of the previously selected activity.

Why does this work?

By choosing the activity that finishes earliest, we leave the maximum possible room/time window for subsequent activities to be scheduled.

Step-by-Step Approach

Case 1: When Activities are Already Sorted by Finish Time

Select the first activity from the sorted array (it always finishes first).
For the remaining activities, if the start time of the activity is greater than or equal to the finish time of the previously selected activity, select it.

Case 2: When Activities are Unsorted

Group each activity's start time, finish time, and original index.
Sort the activities in ascending order of their finish times.
Apply the same selection logic as Case 1.

Visual Trace (Example 2)

Consider the following 6 activities:

Start times: [1, 3, 0, 5, 8, 5]
Finish times: [2, 4, 6, 7, 9, 9]

Initially sorted by finish times:
Activity 0: (1, 2)  <-- Selected (first finishes earliest)
Activity 1: (3, 4)  <-- Selected (start 3 >= prev finish 2)
Activity 2: (0, 6)  <-- Skipped  (start 0 < prev finish 4)
Activity 3: (5, 7)  <-- Selected (start 5 >= prev finish 4)
Activity 4: (8, 9)  <-- Selected (start 8 >= prev finish 7)
Activity 5: (5, 9)  <-- Skipped  (start 5 < prev finish 9)

Output Selected Indices: 0, 1, 3, 4 (total of 4 activities).

JavaScript Code Implementation

class Activity {
    constructor(start, finish, index) {
        this.start = start;
        this.finish = finish;
        this.index = index;
    }
}
 
// Function to print the maximum activities
function selectMaxActivities(start, finish) {
    const n = start.length;
    const activities = [];
 
    // 1. Create activity objects with original index
    for (let i = 0; i < n; i++) {
        activities.push(new Activity(start[i], finish[i], i));
    }
 
    // 2. Sort activities according to finish time
    activities.sort((a, b) => a.finish - b.finish);
 
    console.log("Selected Activities (Original Indices):");
    
    // 3. The first activity always gets selected
    let i = 0;
    const selected = [activities[i].index];
    
    // 4. Check remaining activities
    for (let j = 1; j < n; j++) {
        // If this activity has a start time greater than or equal
        // to the finish time of the previously selected activity
        if (activities[j].start >= activities[i].finish) {
            selected.push(activities[j].index);
            i = j; // Update to currently selected activity
        }
    }
 
    return selected;
}
 
// Driver code
const start = [1, 3, 0, 5, 8, 5];
const finish = [2, 4, 6, 7, 9, 9];
 
const result = selectMaxActivities(start, finish);
console.log(result.join(", "));
// Output: 0, 1, 3, 4

Complexity Analysis

Time Complexity:
- O(N) if the activities are already sorted by finish time.
- O(N log N) if the activities are unsorted, due to the sorting step.
Space Complexity: O(N)
- To store the list of activity structures for sorting.

Introduction to Greedy Fractional Knapsack