贪心算法3：会议安排

雨点打透心脏的1/2处 2022-05-08 10:40 236阅读 0赞

问题描述：要在有限的时间内安排尽量多的会议。

贪心策略（前提是会议不冲突，也就是两个会议不同时进行）：

1. 每次选择持续时间最短的安排。这样如果开始时间很迟，安排的会议也很少，所以策略不是最优；

2. 每次选择开始时间最早的。这样如果结束时间很迟，那安排的会议也很少，也不是最优策略；

3. 每次选择开始时间最早的并且持续时间最短的来安排。也就是结束时间最早的来安排，这样是最优策略，可以安排尽量多的会议。

![70][]

![70 1][]

排序规则：先按结束时间从小到大排序，如果结束时间相同，就按开始时间从大到小排序（保证持续时间最短）

![70 2][]

![70 3][]

算法设计：

![70 4][]

思路：1. 用结构体记录每个会议的开始时间，结束时间和会议的编号，便于后面进行记录。

2. 对会议进行排序，先按结束时间从小到大排序，如果结束时间相同，就按开始时间从大到小排序。

3. 贪心策略：每次都选择结束时间最早且互不冲突的会议，并记录其编号和选择的会议数。

当下一次开始时间小于上一次结束时间时，说明会议不冲突，可以选择，记录其会议编号，累加其会议数即可。然后更新最新的结束时间。

#include<iostream>
    #define MAXN 1005
    #include<algorithm>
    using namespace std;
    struct Meet{
    	int begt;//每个会议的开始时间 
    	int endt;//每个会议的结束时间 
    	int num;//会议编号 
    };
    Meet a[MAXN];
    
    bool cmp(Meet &a, Meet &b)
    {
    	if(a.endt == b.endt)//结束时间相同时，按开始时间从大到小排序 ，保证持续时间最短 
    		return a.begt > b.begt;
    	return a.endt < b.endt;//结束时间不同时，按照结束时间从小到大排序 
    }
    int main()
    {
    	freopen("a.txt","r",stdin);
    	int n;//会议总数
    	cin >> n;
    	for(int i = 1; i <= n; ++i)
    	{
    		cin >> a[i].begt >> a[i].endt; 
    		a[i].num = i; 
    	}
    	sort(a+1,a+1+n,cmp);
    	for(int i = 1; i <= n; ++i)
    		cout << a[i].num << " " << a[i].begt << " " << a[i].endt << endl; 
    	int last = a[1].endt;
    	int sum = 1;//选择的会议总数 
    	int t = a[1].num;
    	cout << t << endl; //第几个会议 
    	for(int i = 2; i <= n; ++i)
    	{
    		if(a[i].begt >= last)//如果下一次的开始时间>上一次的结束时间,就安排会议 
    		{
    			cout << a[i].num << endl;
    			++sum;
    			last = a[i].endt;//更新结束时间 
    		} 
    	} 
    	cout << sum << endl;
    	return 0;
    }

[70]: /images/20220508/615cb86bf49d4d199aba242f4ca93ce8.png
[70 1]: /images/20220508/e11e7c2a71874f708151ae57934fa4be.png
[70 2]: /images/20220508/af29adb632744db4aef3a7fd6007e359.png
[70 3]: /images/20220508/261f826ff03043068d697904e659dce3.png
[70 4]: /images/20220508/f0b5f66b782941508c955f7aff93d235.png