课程安排

问题引入

抄一下题目..

算法解释

之所以按结束时间来排列，是通过数学归纳法来确定的;

通过数学归纳法可以比较出：以开始时间排列 ，以课程时间长度排列，以结束时间排列中，按结束时间排列可以得出最优解;

按这种方法选择相容课程为未安排活动留下尽可能多的时间，即局部最优;

换一种说法
我们直接来考虑算法部分的问题吧，如果从一组课程数据中算出课室安排的最优解，我们需要好好的分析问题，抽取问题的实质才行。比如这个课程安排问题，怎么才能尽可能多的活动呢？自然是活动的时间尽可能短，并且不同的活动能够进行衔接，那么举办的活动数量就最多的了。

代码

#include<cstdio>  //包含输入输出头文件
#include<algorithm>   //包含排序算法头文件
struct classInfo//定义一个结构体
{
    int start;  //储存开始时间
    int end;  //储存结束时间
}a[100010];  //储存所有的课程
bool cmp(classInfo a,classInfo b)               //按会议结束时间排列
{
    return a.end<b.end;    //定义排序方法，按照结束时间排序
}
using namespace std;
int main()
{
    int x;  //定义一个变量储存要执行几次程序
    printf("请输入要执行多少次程序:");
    scanf("%d",&x);  //输入想要程序执行多少次
    while(x--)  //while循环，当减到x为0就不再执行
    {
    int i;//定义i后面用
    int n;//定义n表示当前一共会输入几个课程
    printf("请输入待安排课程数数量:");
    scanf("%d",&n);//输入课程总数
    for(i=1;i<=n;i++){
        printf("请输入第%d节课的开始和结束时间，以空格间隔:",i);
        scanf("%d %d",&a[i].start,&a[i].end);  //输入每一个课程的开始结束时间
    }
    a[0].start=-1; //第一个是空的随便设置
    a[0].end=-1;  //第一个是空的随便设置
    sort(a+1,a+n+1,cmp);                           //按照结束时间排列第1-n个
    int sum=1;//最少可以排一个，所以答案至少为一
    int j=1;//储存上一个选用的课程（一开始的时候为1）
    for(i=2;i<=n;i++)                      //从第二个会场开始从与前一个会场比较
    {
        if(a[i].start>a[j].end)        //如果相隔时间大于1（输入都为整数），则活动数+1
        {
            j=i;    //把上一个选用的课程记录为当前课程
            sum++;    //能够安排的课程数量+1
        }
    }
    printf("一共可以安排%d节课\n",sum);//输出一共可以安排几个课程
    }
    return 0;//返回0，程序结束
}