How to use activity selection algorithm in C++

How to use the activity selection algorithm in C

The activity selection algorithm (Activity Selection Algorithm) is a classic greedy algorithm used to solve activity scheduling problems. Given a set of start and end times for activities, the goal of the algorithm is to select the largest set of compatible activities, that is, the maximum number of activities that do not conflict with each other and can be performed simultaneously. This article will introduce how to implement the activity selection algorithm using C, with specific code examples.

Algorithm idea:

The basic idea of ​​the activity selection algorithm is to first sort the activities according to their end time. Then select the activity with the earliest end time, excluding other activities that conflict with it. The specific steps are as follows:

1. First, you need to define a structure to represent each activity. The structure contains the start time and end time of the activity.

struct Activity
{
    int start;
    int end;
};

2. Then, define a function to implement the activity selection algorithm. The input of the function is an array of activities and the size of the array, and the output is a maximum consistent set of activities.

vector<Activity> activitySelection(Activity arr[], int n)
{
    // 根据结束时间对活动进行排序
    sort(arr, arr + n, [](Activity a, Activity b) {
        return a.end < b.end;
    });

    vector<Activity> selectedActivities;
    selectedActivities.push_back(arr[0]); //选择第一个活动

    int lastSelected = 0;
    //遍历剩余的活动
    for (int i = 1; i < n; i++)
    {
        if (arr[i].start >= arr[lastSelected].end)
        {
            selectedActivities.push_back(arr[i]);
            lastSelected = i;
        }
    }

    return selectedActivities;
}

3. Finally, construct an activity array in the main function and call the activity selection function to print out the maximum consistent activity set.

int main()
{
    Activity arr[] = {{1, 2}, {3, 4}, {0, 6}, {5, 7}, {8, 9}, {5, 9}};
    int n = sizeof(arr) / sizeof(arr[0]);

    vector<Activity> selectedActivities = activitySelection(arr, n);

    cout << "最大相容活动集合：" << endl;
    for (int i = 0; i < selectedActivities.size(); i++)
    {
        cout << "(" << selectedActivities[i].start << ", " << selectedActivities[i].end << ")" << endl;
    }

    return 0;
}

Code sample analysis:

First, in the defined structure, use the start time (start) and end time (end) of each activity as the structure's member.

Then, in the implemented activity selection function, the activity array is first sorted according to the end time of the activity, so that the subsequent activities can be easily selected in the order of the end time.

Next, define a vector container selectedActivities to save the maximum consistent set of activities and add the first activity to it.

Then, start from the second activity and traverse the remaining activities. If the start time of the current activity is greater than or equal to the end time of the last selected activity, the activity is added to the maximum compatible activity set and set as the last currently selected activity.

Finally, create an activity array in the main function, call the activity selection function, and print out the maximum consistent activity set.

Summary:

Through the above sample code, we can see how to implement the activity selection algorithm in C. A greedy strategy is used to select the largest set of compatible activities based on their end times. Activity selection algorithms are widely used in real life, such as meeting arrangements, project management, etc.

[References]

[1] Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd edition). MIT Press .

The above is the detailed content of How to use activity selection algorithm in C++. For more information, please follow other related articles on the PHP Chinese website!