请用贪心算法解决以下活动安排问题。某处举办活动，仅

[问答题]

请用贪心算法解决以下活动安排问题。

某处举办活动，仅有一个会场，有 11 个活动需要安排，开始时间和结束时间如下表，要求该会场能够尽可能多的满足活动。（注：只考虑满足活动的个数，不考虑占用时间）

开始时间 s[i]

结束时间

f[i]

一城烟雨柳色青

因为只存在一个会场，所以要满足足够多的活动必须保证每个活动所占用的时间都是不相容的，即i活动的开始时间si必须大于等于j活动的结束时间ej，或者j活动的开始时间sj大于等于i活动而的结束时间ei。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


int main()
{
    vector<int> a = {12,2,8,8,6,5,3,5,0,3,1};  //开始时间
        vector<int> b = {14,13,12,11,10,9,8,7,6,5,4};  //结束时间
        vector<pair<int,int>> v;
        for(int i = 0; i < (int)a.size(); ++i)
            v.push_back({b[i],a[i]});
        sort(v.begin(),v.end());
     
        //vv[i].first 是结束时间，second是开始时间
        int count = 1;   //默认选最早结束的，也就是vv[0]
        int endFlag = vv[0].first;
        for(int i = 1; i < (int）v.size(); ++i)
        {
            //如果i开始时间大于endFlag就ok，然后更新endFlag
            if(vv[i].second >= endFlag)
            {
                ++count;
                endFlag = vv[i].first;
            }
        }
        return count;
        
}

发表于 2022-01-04 11:49:46 回复(0)