Greedy problem 01_ Activity arrangement code analysis

The corresponding code content of this blog ：https://blog.csdn.net/qq_43468008/article/details/105927468

One 、 How to express activities ？

• 1、 Starting time
• 2、 End time
• 3、 Activity number

struct action{
    
    int a,b; 	//  start 、 End time 
    int index;  //  Activity number 
};

action s[1025];  //  Store active content 

---

Two 、 Data processing

Such a pile of activities are randomly input and stored in s[1025] in , It needs to be sorted to facilitate processing .
Sorting rules ：
Sort by activity end time in ascending order .

bool cmp(const action &x,const action &y){
    
    if(x.b<=y.b)
        return true;
    return false;
}

 sort(s,s+n+1,cmp);  //  Subscript from 1 Start sorting 

Then input data according to the previous case , Activities after sorting ：
Activities 1: 1 4
Activities 2: 3 5
Activities 3: 0 6
Activities 4: 5 7
Activities 5: 3 8
Activities 6: 5 9
Activities 7: 6 10
Activities 8: 8 11
Activities 9: 8 12
Activities 10: 2 13
Activities 11: 12 14

---

3、 ... and 、 Core code

Provide the required parameters ：

• int n; // Indicates that there are several activities
• action s[]; // Activity list
• bool l[]; // Subgroup array , Used to record which activities were finally selected

void GreedySelector(int n,action s[],bool l[]){
    
    l[1] = true;   //  The first activity is required 
    
    int preEnd = 1;   //  Used to record “ The latest selected activity number ”
    
    for(int i=2; i<=n; i++){
       //  Start the cycle from the second activity 
        if(s[i].a>=s[preEnd].b){
      
            l[i] = true;
            preEnd = i;
        }
    }
}