Cover Image for Activity Selection Program in C++
114 views

Activity Selection Program in C++

The Activity Selection Problem is a classic scheduling problem in which you are given a list of activities, each with a start time and an end time. The goal is to select the maximum number of non-overlapping activities. Here’s a C++ program to solve the Activity Selection Problem using a greedy algorithm:

C++
#include <iostream>
#include <vector>
#include <algorithm>

// Structure to represent an activity with start and end times
struct Activity {
    int start;
    int end;
};

// Function to compare activities based on their end times
bool compareActivities(const Activity& a, const Activity& b) {
    return a.end < b.end;
}

// Function to solve the Activity Selection Problem
void activitySelection(std::vector<Activity>& activities) {
    // Sort the activities based on their end times
    std::sort(activities.begin(), activities.end(), compareActivities);

    // The first activity is always selected
    int n = activities.size();
    std::cout << "Selected Activities: ";
    int i = 0;
    std::cout << "(" << activities[i].start << ", " << activities[i].end << ") ";

    // Consider the rest of the activities
    for (int j = 1; j < n; j++) {
        // If this activity has a start time greater than or equal to the end time of the previously selected activity,
        // then select it
        if (activities[j].start >= activities[i].end) {
            std::cout << "(" << activities[j].start << ", " << activities[j].end << ") ";
            i = j;
        }
    }
    std::cout << std::endl;
}

int main() {
    std::vector<Activity> activities = {
        {1, 2},
        {3, 4},
        {0, 6},
        {5, 7},
        {8, 9},
        {5, 9}
    };

    std::cout << "Activities: " << std::endl;
    for (const Activity& activity : activities) {
        std::cout << "(" << activity.start << ", " << activity.end << ") ";
    }
    std::cout << std::endl;

    activitySelection(activities);

    return 0;
}

In this program:

  • We define a struct called Activity to represent each activity with start and end times.
  • We implement a function compareActivities to compare activities based on their end times. This function is used for sorting.
  • The activitySelection function solves the Activity Selection Problem using a greedy approach. It first sorts the activities by their end times, selects the first activity, and then iterates through the remaining activities, selecting each one that doesn’t overlap with the previously selected activity.
  • In the main function, we define a vector of activities, print the original list of activities, and then call activitySelection to find the selected activities.

This program will output the selected non-overlapping activities.

YOU MAY ALSO LIKE...

The Tech Thunder

The Tech Thunder

The Tech Thunder


COMMENTS