【程序】会议安排

关于安排会议，利用贪心算法，选择具有最早结束时间且与已安排内容相容的会议安排

参见：《趣学算法》，陈小玉，2.4

运行结果：

代码：

头文件：

#pragma once
#include<algorithm>
#include<iostream>


class setMeet {
public:
    void init();
    void solve();
private:
    int n, ans;   //n:会议总数 ans:最大的安排会议总数
};

源文件：

 1 #include "setMeet.h"
 2 using namespace std;
 3 
 4 struct Meet
 5 {
 6     int beg;    //记录会议的开始时间
 7     int end;
 8     int num;      //会议编号
 9 }meet[1000];    //会议的最大个数为1000
10 
11 
12 void setMeet::init()   //读入数据
13 {
14     int s, e;
15     cout << "输入会议总数： " << endl;
16     cin >> n;
17     int i;
18     cout << "输入会议的开始时间与结束时间，以空格分开：" << endl;
19     for (i = 0; i < n; ++i)
20     {
21         cin >> s >> e;
22         meet[i].beg = s;
23         meet[i].end = e;
24         meet[i].num = i + 1;
25     }
26 }
27 
28 bool cmp(Meet x, Meet y)
29 {
30         if (x.end == y.end)
31             return x.beg > y.beg;
32         return x.end < y.end;
33 }
34 
35 void setMeet::solve()
36 {
37     sort(meet, meet + n, cmp);//对会议按结束时间排序
38     cout << "拍完序的会议时间如下：" << endl;
39     int i;
40     cout << "会议编号" << "  开始时间" << "  结束时间" << endl;
41     for (i = 0; i < n; i++)
42     {
43         cout << "  " << meet[i].num << "		" << meet[i].beg << "	" << meet[i].end << endl;
44     }
45         cout << "----------------------------------------------------------------" << endl;
46         cout << "选择的会议 的过程：" << endl;
47         cout << " 选择第" << meet[0].num << "个会议" << endl;//选中了第一个会议
48         ans = 1;
49         int last = meet[0].end;//记录刚刚选中的会议的结束时间
50         for (i = 1; i < n; i++)
51         {
52             if (meet[i].beg >= last)
53             {
54                 ans++;
55                 last = meet[i].end;
56                 cout << " 选择第" << meet[i].num << "个会议" << endl;
57             }
58         }
59         cout << "最多可以安排" << ans << "个会议" << endl;
60     
61 }

View Code

主文件：

#include"setMeet.h"
using namespace std;

int main()
{
    setMeet sm;
    sm.init();
    sm.solve();

    cin.ignore();
    cin.ignore();
    cin.ignore();

    
    return 0;
}