24-伪代码详解

2.4.4　伪代码详解

（1）数据结构定义

以下C++程序代码中，结构体meet中定义了beg表示会议的开始时间，end表示会议的结束时间，会议meet的数据结构：

struct Meet
{
     int beg;   //会议的开始时间
     int end;   //会议的结束时间
} meet[1000]；

（2）对会议按照结束时间非递减排序

我们采用C++中自带的sort函数，自定义比较函数的办法，实现会议排序，按结束时间从小到大排序（非递减），结束时间相等时，按开始时间从大到小排序（非递增）：

bool cmp(Meet x,Meet y)
{
     if(x.end==y.end)  //结束时间相等时 
        return x.beg>y.beg; //按开始时间从大到小排序
     return x.end<y.end; //按结束时间从小到大排序
}
sort(meet,meet+n,cmp);

（3）会议安排问题的贪心算法求解

在会议按结束时间非递减排序的基础上，首先选中第一个会议，用last变量记录刚刚被选中会议的结束时间。下一个会议的开始时间与last比较，如果大于等于last，则选中。每次选中一个会议，更新last为最后一个被选中会议的结束时间，被选中的会议数ans加1；如果会议的开始时间不大于等于last，继续考查下一个会议，直到所有会议考查完毕。

int ans=1;     //用来记录可以安排会议的个数，初始时选中了第一个会议
int last = meet[0].end;  //last记录第一个会议的结束时间
for( i = 1;i < n; i++)   //依次检查每个会议
{
    if(meet[i].beg > =last) 
    {     //如果会议i开始时间大于等于最后一个选中的会议的结束时间
       ans++;
       last = meet[i].end; //更新last为最后一个选中会议的结束时间
    }
}
return ans; //返回可以安排的会议最大数

上面介绍的程序中，只是返回了可以安排的会议最大数，而不知道安排了哪些会议，这显然是不满足需要的。我们可以改进一下，在会议结构体meet中添加会议编号num变量，选中会议时，显示选中了第几个会议。