The Activity Selection Problem is a classic example of optimization using greedy algorithms. The problem is simple: given a list of activities with a start and finish time, the goal is to select the maximum number of non-overlapping activities. This is a typical problem that can be efficiently solved using a greedy strategy.

 

Problem Statement

You are given a list of activities, each with a start time l and finish time r. Your task is to select the maximum number of non-overlapping activities. The solution must be efficient, meaning we need to find the optimal solution without testing every possible combination.

 

Greedy Approach

The goal is to select the maximum number of non-overlapping activities from a list, each defined by a start time and finish time. The greedy approach works by making the optimal choice at each step, ensuring a globally optimal solution.

The process begins by sorting the activities based on their finish times. The first activity, which finishes the earliest, is always selected. Then, for each subsequent activity, we select it if its start time is greater than or equal to the finish time of the last selected activity. This ensures no overlap.

The key to the greedy approach is the greedy choice property: always choose the activity that finishes first to leave room for future activities. This guarantees the maximum number of activities can be selected.

 

Implementation 

  struct activity {
    int l;
    int r; 
};

bool compare(const activity &a, const activity &b) {
    return a.r < b.r;
}

vector<activity> solveActivitySelectionProblem(vector<activity> &activities) {
    if (activities.size() <= 1)
        return activities;

    // Sort activities so the one that finishes earliest comes first.
    sort(activities.begin(), activities.end(), compare);

    // Container for the chosen non-overlapping activities.
    vector<activity> selected_activities;
    // Always select the first (earliest-finishing) activity.
    selected_activities.push_back(activities[0]);
    // Keep track of when the last selected activity finishes.
    int last_finish_time = activities[0].r;

    for (size_t i = 1; i < activities.size(); ++i) {
        // If the next activity starts at or after the last finish time, select it.
        if (activities[i].l >= last_finish_time) {
            selected_activities.push_back(activities[i]);
            last_finish_time = activities[i].r;
        }
    }

    return selected_activities;
}
  
  class Activity {
    int l;
    int r;

    public Activity(int l, int r) {
        this.l = l;
        this.r = r;
    }
}

public class ActivitySelection {

    public static Comparator<Activity> compareByFinishTime = new Comparator<Activity>() {
        @Override
        public int compare(Activity a, Activity b) {
            return Integer.compare(a.r, b.r);
        }
    };

    public static List<Activity> solveActivitySelectionProblem(List<Activity> activities) {
        if (activities.size() <= 1)
            return activities;

        // Sort activities by finish time
        Collections.sort(activities, compareByFinishTime);

        List<Activity> selectedActivities = new ArrayList<>();
        selectedActivities.add(activities.get(0)); // Select the first activity
        int lastFinishTime = activities.get(0).r;

        for (int i = 1; i < activities.size(); i++) {
            // If the next activity starts at or after the last finish time, select it.
            if (activities.get(i).l >= lastFinishTime) {
                selectedActivities.add(activities.get(i));
                lastFinishTime = activities.get(i).r;
            }
        }

        return selectedActivities;
    }
}
  
  class Activity:
    def __init__(self, l, r):
        self.l = l
        self.r = r

def solve_activity_selection_problem(activities):
    if len(activities) <= 1:
        return activities

    # Sort activities by finish time
    activities.sort(key=lambda activity: activity.r)

    selected_activities = []
    selected_activities.append(activities[0])  # Select the first activity
    last_finish_time = activities[0].r

    for i in range(1, len(activities)):
        # If the next activity starts at or after the last finish time, select it.
        if activities[i].l >= last_finish_time:
            selected_activities.append(activities[i])
            last_finish_time = activities[i].r

    return selected_activities

 

Time Complexity

Sorting the activities takes $O(n \log n)$, where n is the number of activities. The selection step involves a single pass through the sorted activities, which takes $O(n)$. Therefore, the overall time complexity of the algorithm is $O(n \log n)$, dominated by the sorting step.

 

Code on GitHub

See the implementation code for Activity Selection Problem.

Last updated 09 May 2025, 23:43 +0500 . history