C++ greedy algorithm (venue arrangement, interval selection) example

The first recording after learning the algorithm course. Gradually, the factors to be considered in program design increased. Program = data structure algorithm. This equation made me deeply understand. From starting with simple C programming to selecting appropriate data structures, now we need to go one step further and consider the efficiency of program execution from the algorithm level. My understanding of the algorithm is to achieve better execution results with less overhead.

The divide and conquer method and dynamic programming have not been recorded before. When I learned the greedy algorithm, I felt that I needed to summarize what I had learned so that I could understand it better. . The design of dynamic programming must satisfy the optimal substructure properties and overlapping subproblems, and adopt a bottom-up strategy to calculate the optimal value and find the overall optimal solution. This process is sometimes quite difficult. The main thing is to write the recursive expression and fill in the table from the bottom up. The greedy strategy is a bit like dynamic programming, but it is different in some aspects. Sometimes the idea of ​​​​a greedy algorithm is easier to think of. Does it satisfy the sub-problem optimality and obtain the overall optimality? Two conditions: optimal substructure property and greedy selection property. Satisfying the greedy selection property must satisfy the optimal substructure property, while satisfying the optimal substructure property does not necessarily satisfy the greedy selection property. For example, the knapsack problem can be solved with a greedy algorithm, while the 0-1 knapsack problem can only be solved with dynamic programming.

Typical greedy problem activity arrangement, there are n activities, the start time and end time are given, and as many activities as possible should be arranged (the time does not conflict with each other). The correct greedy idea to solve this problem is to use the end time of each activity as a comparison variable, sort the activities in ascending order of the end time, and then perform comparison and selection. There are some differences between venue arrangement issues and activities. The following is my problem-solving process.

7-2 Venue Arrangement Issues (20 points)

Suppose you want to arrange a batch of activities in enough venues and want to use as few venues as possible. Design an efficient greedy algorithm for scheduling. (This problem is actually the famous graph coloring problem. If each activity is regarded as a vertex of the graph, incompatible activities are connected by edges. The minimum number of colorings that make adjacent vertices have different colors corresponds to the Minimum number of venues.)

Input format:

The first line contains a positive integer k, indicating that there are k activities to be arranged. In the next k lines, each line has 2 positive integers, representing the start time and end time of k to-be-scheduled activities respectively. Time is measured in minutes starting at 0 o'clock.

Output format:

Output the minimum number of venues.

Input sample:

5
1 23
12 28
25 35
27 80
36 50

Output sample:

3

#include<iostream>
#include<algorithm>
using namespace std;
struct node {
    int begin;
    int end;
    int flag;//标记该活动是否被安排，0表示未安排，1表示已安排 
}t[10001];
int cmp(const node &a,const node &b)//比较规则：以结束时间升序排列 
{ 
    return a.end<b.end;
 } 
int main()
{
    int i,j,n;
    node temp;
    cin>>n;
    for(i=0;i<n;i++) 
    {
        cin>>t[i].begin>>t[i].end;
        t[i].flag=0;
    }
    sort(t,t+n,cmp);
        
    int sum=0;//总共需要的会场数量 
    for(i=0;i<n;i++)//方法2 
    {
        if(!t[i].flag)//找到未安排的活动，进行场地安排 
        {
            sum++;
            int p=i;
            for(j=p+1;j<n;j++)//当前活动结束时间与下一个活动开始不相交 ，则安排到同一个会场 
            {
                if(t[p].end<=t[j].begin&&!t[j].flag)
                {
                    p=j;t[j].flag=1;
                }
            }
            t[i].flag=1;
        }
    }
    cout<<sum;
    return 0;
}

The greedy strategy is: arrange as many non-conflicting activities as possible into one venue. If the activity If the time overlaps, it will be arranged to another venue.

Arrange all activities in ascending order by end time, use the sort function, and customize the cmp method. In the loop body, you can find an unscheduled activity each time, and use this activity to search for other activities that can be accommodated in a venue at the same time (this step is nested in the inner loop). After two layers of loops, all activities are arranged. Okay, now the required number of venues, sum, has been calculated.

A similar problem is interval point selection

7-10 point selection problem (15 points)

There are n closed intervals on the number axis [ai , bi]. Take as few points as possible so that there is at least one point in each interval (the points in different intervals can be the same).

Input format:

A number n in the first line means there are n closed intervals. The following n lines, each line contains 2 numbers, indicating the closed interval [ai, bi]

Output format:

An integer, indicating at least how many points are needed

Input sample:

Give a set of input here. For example:

3
1 3
2 4
5 6

Output sample:

The corresponding output is given here. For example: 2

initially wants to find common segments among several intervals, and record which intervals are included in each common segment, so as to calculate the minimum selected points. Later I found that this idea can actually be simplified. The strategy is: use the right end as the baffle to see if there are other intervals in front of it. If so, do not count. Otherwise, it means that there are no common segments. You need to count and move the baffle position to continue. Look for. The greedy strategy is to select the right endpoint of the interval to ensure that it can contain a larger intersection segment and select the fewest points.

#include<bits/stdc++.h>
using namespace std;
struct dot{
    int l,r;
    bool v[10001];
}dots[10001];
int cmp(const dot &a,const dot &b)//比较规则，按区间右端点升序排列 
{
    return a.r<b.r;
} 
int main()
{
    int n,i,j,count=1,select;
    cin>>n;
    for(i=0;i<n;i++)
        cin>>dots[i].l>>dots[i].r;
    sort(dots,dots+n,cmp);//预处理，将区间按规则排好序，方便后续比较 
    select=dots[0].r;
    //贪心策略是选择区间右端点，保证能够包含更大交叉段，选的点最少 
    for(i=1;i<n;i++)//每次将当前选择的一个区间的右端点与下一个（或者同一区间，可忽略）左端比较 
    {
        if(dots[i].l>select)//如果没有交叉，选点+1,并以此区间右端为新一轮比较的点 
        {
            count++;
            select=dots[i].r;
        }
    }
    cout<<count;
    return 0;
}

After learning the algorithm, I found that solving problems requires a change in thinking. The choice of algorithm before programming is very important. I also need to learn from the big guys. The study and research of typical algorithms is really broad and profound!

This article comes from the C#.Net Tutorial column, welcome to learn!

The above is the detailed content of C++ greedy algorithm (venue arrangement, interval selection) example. For more information, please follow other related articles on the PHP Chinese website!