25-实战演练

2.4.5　实战演练

//program 2-3
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
struct Meet
{
     int beg;   //会议的开始时间
     int end;   //会议的结束时间
     int num;   //记录会议的编号
}meet[1000];    //会议的最大个数为1000
class setMeet{
  public:
    void init();
    void solve();
  private:
    int n,ans; // n:会议总数 ans: 最大的安排会议总数
};
//读入数据
void setMeet::init()
{
     int s,e;
     cout <<"输入会议总数："<<endl;
     cin >> n;
     int i;
     cout <<"输入会议的开始时间和结束时间，以空格分开："<<endl;
     for(i=0;i<n;++i)
     {
         cin>>s>>e;
         meet[i].beg=s;
         meet[i].end=e;
         meet[i].num=i+1;
     }
}
bool cmp(Meet x,Meet y)
{
     if (x.end == y.end)
           return x.beg > y.beg;
     return x.end < y.end;
}
void setMeet::solve()
{
     sort(meet,meet+n,cmp);    //对会议按结束时间排序
     cout <<"排完序的会议时间如下："<<endl;
     int i;
     cout <<"会议编号"<<"  开始时间 "<<" 结束时间"<<endl;
     for(i=0; i<n;i++)
     {
       cout<< "   " << meet[i].num<<"\t\t"<<meet[i].beg <<"\t"<< meet[i].end << endl;
     }
     cout <<"-------------------------------------------------"<<endl;
     cout << "选择的会议的过程：" <<endl;
     cout <<"  选择第"<< meet[0].num<<"个会议" << endl;//选中了第一个会议
     ans=1;
     int last = meet[0].end;  //记录刚刚被选中会议的结束时间
     for( i = 1;i < n;++i)
     {
          if(meet[i].beg>=last)
          {            //如果会议i开始时间大于等于最后一个选中的会议的结束时间
             ans++;
             last = meet[i].end;
             cout <<"  选择第"<<meet[i].num<<"个会议"<<endl;
          }
     }
     cout <<"最多可以安排" <<ans << "个会议"<<endl;
}
int main()
{
  setMeet sm;
  sm.init();//读入数据
  sm.solve();//贪心算法求解
  return 0;
}

算法实现和测试

（1）运行环境

Code::Blocks

（2）输入

输入会议总数：
10
输入会议的开始时间和结束时间，以空格分开：
3 6
1 4
5 7
2 5
5 9
3 8
8 11
6 10
8 12
12 14

（3）输出

排完序的会议时间如下：
会议编号    开始时间    结束时间
   2           1          4
   4           2          5
   1           3          6
   3           5          7
   6           3          8
   5           5          9
   8           6          10
   7           8          11
   9           8          12
   10          12         14
-------------------------------------------------
选择的会议的过程：
  选择第2个会议
  选择第3个会议
  选择第7个会议
  选择第10个会议
最多可以安排4个会议

使用上面贪心算法可得，选择的会议是第2、3、7、10个会议，输出最优值是4。