Activity Selection: Maximize Non-overlapping Tasks

Description

The Activity Selection Problem is a classic greedy algorithm problem that involves selecting the maximum number of activities that can be performed by a single person, given that the person can only work on a single activity at a time. Each activity has a start time and a finish time, and activities cannot overlap.

How It Works

Sort all activities in ascending order of finish time
Select the first activity (with earliest finish time)
For each remaining activity:
- If the start time of the current activity is greater than or equal to the finish time of the last selected activity:
  - Select this activity
  - Update the last selected activity
Return the selected activities

The greedy choice is to always select the activity with the earliest finish time among the remaining compatible activities. This ensures that we have maximum time left for other activities.

Visualization

Speed:

Generate random activities and click Start to begin visualization

Complexity Analysis

Time Complexity

Sorting: O(n log n)
- Sorting activities by finish time
Selection: O(n)
- Iterating through sorted activities once
Overall: O(n log n)
- Dominated by the sorting step

Space Complexity

Storage: O(n)
- Space to store the selected activities
- Space for sorting (implementation dependent)

Advantages and Disadvantages

Advantages

Simple and efficient implementation
Optimal solution guaranteed
Works well for large datasets
No backtracking required

Disadvantages

Requires activities to be sorted by finish time
Not applicable if activities have different weights/values
Cannot handle overlapping activities with priorities
Limited to single-resource scheduling

Implementation


def activity_selection(activities):
    """
    Selects the maximum number of non-overlapping activities.
    
    Parameters:
        activities: list of tuples - Each tuple contains (start_time, finish_time)
    
    Returns:
        list of indices - Indices of selected activities
    """
    # Sort activities by finish time
    sorted_activities = sorted(enumerate(activities), key=lambda x: x[1][1])
    
    # Select first activity
    selected = [sorted_activities[0][0]]
    last_finish_time = sorted_activities[0][1][1]
    
    # Consider rest of the activities
    for i in range(1, len(sorted_activities)):
        index, (start_time, finish_time) = sorted_activities[i]
        
        # If this activity starts after the finish time of last selected activity
        if start_time >= last_finish_time:
            selected.append(index)
            last_finish_time = finish_time
    
    return selected

# Example usage
if __name__ == "__main__":
    # Activities as (start_time, finish_time)
    activities = [
        (1, 4),   # Activity 0
        (3, 5),   # Activity 1
        (0, 6),   # Activity 2
        (5, 7),   # Activity 3
        (3, 9),   # Activity 4
        (5, 9),   # Activity 5
        (6, 10),  # Activity 6
        (8, 11),  # Activity 7
        (8, 12),  # Activity 8
        (2, 14),  # Activity 9
        (12, 16)  # Activity 10
    ]
    
    selected_indices = activity_selection(activities)
    
    print("Selected activities:")
    for idx in selected_indices:
        print(f"Activity {idx}: ({activities[idx][0]}, {activities[idx][1]})")


#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

class ActivitySelection {
public:
    // Function to select maximum number of activities
    std::vector<int> selectActivities(const std::vector<std::pair<int, int>>& activities) {
        int n = activities.size();
        
        // Create a vector of pairs where first element is the original index
        // and second element is the activity (start time, finish time)
        std::vector<std::pair<int, std::pair<int, int>>> indexedActivities;
        for (int i = 0; i < n; i++) {
            indexedActivities.push_back({i, activities[i]});
        }
        
        // Sort activities by finish time
        std::sort(indexedActivities.begin(), indexedActivities.end(), 
                 [](const auto& a, const auto& b) {
                     return a.second.second < b.second.second;
                 });
        
        // Select first activity
        std::vector<int> selected;
        selected.push_back(indexedActivities[0].first);
        int lastFinishTime = indexedActivities[0].second.second;
        
        // Consider rest of the activities
        for (int i = 1; i < n; i++) {
            int index = indexedActivities[i].first;
            int startTime = indexedActivities[i].second.first;
            int finishTime = indexedActivities[i].second.second;
            
            // If this activity starts after the finish time of last selected activity
            if (startTime >= lastFinishTime) {
                selected.push_back(index);
                lastFinishTime = finishTime;
            }
        }
        
        return selected;
    }
};

int main() {
    // Activities as (start_time, finish_time)
    std::vector<std::pair<int, int>> activities = {
        {1, 4},   // Activity 0
        {3, 5},   // Activity 1
        {0, 6},   // Activity 2
        {5, 7},   // Activity 3
        {3, 9},   // Activity 4
        {5, 9},   // Activity 5
        {6, 10},  // Activity 6
        {8, 11},  // Activity 7
        {8, 12},  // Activity 8
        {2, 14},  // Activity 9
        {12, 16}  // Activity 10
    };
    
    ActivitySelection selector;
    std::vector<int> selected = selector.selectActivities(activities);
    
    std::cout << "Selected activities:" << std::endl;
    for (int idx : selected) {
        std::cout << "Activity " << idx << ": (" 
                  << activities[idx].first << ", " 
                  << activities[idx].second << ")" << std::endl;
    }
    
    return 0;
}


using System;
using System.Collections.Generic;
using System.Linq;

public class ActivitySelection
{
    public List<int> SelectActivities(List<(int start, int finish)> activities)
    {
        int n = activities.Count;
        
        // Create a list of tuples with original indices
        var indexedActivities = activities
            .Select((activity, index) => (index, activity))
            .OrderBy(item => item.activity.finish)
            .ToList();
        
        // Select first activity
        var selected = new List<int> { indexedActivities[0].index };
        int lastFinishTime = indexedActivities[0].activity.finish;
        
        // Consider rest of the activities
        for (int i = 1; i < n; i++)
        {
            int index = indexedActivities[i].index;
            int startTime = indexedActivities[i].activity.start;
            int finishTime = indexedActivities[i].activity.finish;
            
            // If this activity starts after the finish time of last selected activity
            if (startTime >= lastFinishTime)
            {
                selected.Add(index);
                lastFinishTime = finishTime;
            }
        }
        
        return selected;
    }
    
    public static void Main()
    {
        // Activities as (start_time, finish_time)
        var activities = new List<(int start, int finish)>
        {
            (1, 4),   // Activity 0
            (3, 5),   // Activity 1
            (0, 6),   // Activity 2
            (5, 7),   // Activity 3
            (3, 9),   // Activity 4
            (5, 9),   // Activity 5
            (6, 10),  // Activity 6
            (8, 11),  // Activity 7
            (8, 12),  // Activity 8
            (2, 14),  // Activity 9
            (12, 16)  // Activity 10
        };
        
        var selector = new ActivitySelection();
        var selected = selector.SelectActivities(activities);
        
        Console.WriteLine("Selected activities:");
        foreach (int idx in selected)
        {
            Console.WriteLine($"Activity {idx}: ({activities[idx].start}, {activities[idx].finish})");
        }
    }
}

Quick Info

Activity Selection Problem