贪心问题01_活动安排代码分析

本博客对应的代码内容：https://blog.csdn.net/qq_43468008/article/details/105927468

一、怎么表示活动？

• 1、起始时间
• 2、结束时间
• 3、活动编号

struct action{
    
    int a,b; 	// 起始、结束时间
    int index;  // 活动编号
};

action s[1025];  // 存储活动内容

---

二、数据处理

这么一堆活动随机输入并存储到 s[1025] 中，需要对其排序方便处理。
排序规律：
按活动的结束时间升序排序。

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

 sort(s,s+n+1,cmp);  // 下标从1开始排序

那么按照之前给的案例输入数据，排序过后的活动：
活动1: 1 4
活动2: 3 5
活动3: 0 6
活动4: 5 7
活动5: 3 8
活动6: 5 9
活动7: 6 10
活动8: 8 11
活动9: 8 12
活动10: 2 13
活动11: 12 14

---

三、核心代码

需要提供的参数：

• int n; // 表示有几个活动
• action s[]; // 活动列表
• bool l[]; // 辅组数组，用来记录哪些活动被最后选中

void GreedySelector(int n,action s[],bool l[]){
    
    l[1] = true;   // 第一个活动时必选的
    
    int preEnd = 1;   // 用来记录“最新选中的活动编号”
    
    for(int i=2; i<=n; i++){
       // 从第二个活动开始循环
        if(s[i].a>=s[preEnd].b){
      
            l[i] = true;
            preEnd = i;
        }
    }
}