程序填空题：求解活动安排问题（回溯法）

假设有一个需要使用某一资源的n个活动所组成的集合S，S={1，…，n}。该资源任何时刻只能被一个活动所占用，活动i有一个开始时间bi和结束时间ei（bi一旦某个活动开始执行，中间不能被打断，直到其执行完毕。若活动i和活动j有bi≥ej或bj≥ei，则称这两个活动兼容。
设计算法求一种最优活动安排方案，使得所有安排的活动个数最多。

```c++
#include
#include
#include
#define MAX 51
using namespace std;
//问题表示
struct Action
{
int b; //活动起始时间
int e; //活动结束时间
};
int n=4;
Action A[MAX]={{0,0}}; //下标0不用
//求解结果表示
int x[MAX]; //解向量
int bestx[MAX]; //最优解向量
int laste=0; //一个方案中最后兼容活动的结束时间
int sum=0; //一个方案中所有兼容活动个数
int maxsum=0; //最优方案中所有兼容活动个数

void swap(int &x,int &y) //交换x、y
{ int tmp=x; x=y; y=tmp;}

void dispasolution() //输出一个解
{
int laste=0;
for (int j=1;j<=n;j++)
{
if (A[bestx[j]].b>=laste) //选取活动bestx[j]
{
printf("[%d,%d)\n",A[bestx[j]].b,A[bestx[j]].e);
laste=A[bestx[j]].e;
}
}
printf("%d",maxsum);
}

void action(int i)
{
if (i>n)
{
if (sum>maxsum)
{
;
for (int k=1;k<=n;k++)
;
}
}
else
{
for(int j=i; j<=n; j++)
{
int sum1=sum;
int laste1=laste;
if (A[x[j]].b>=laste)
{
;
;
}
swap(x[i],x[j]);
;
swap(x[i],x[j]);
sum=sum1;
laste=laste1;
}
}
}

int main()
{
cin>>n;
for (int i=1;i<=n;i++)
cin>>A[i].b>>A[i].e;
for (int i=1;i<=n;i++)
x[i]=i;
; //i从1开始搜索
dispasolution(); //输出结果
return 0;
}

```

### 输入格式:

第一行是一个整数n，接着的n行中每一行包括两个整数b和e，其中b是一个订单开始时间，e是的结束时间。。

### 输出格式:
若count表示最大兼容活动集合数，先输出count行，每行为活动的开始时间和结束时间。最后输出count。

### 输入样例1:

```in
4
1 3
2 5
4 8
6 10
```

### 输出样例1:

```out
[1,3)
[4,8)
2
```






答案：
第1空：maxsum=sum

第2空：bestx[k]=x[k]

第3空：sum++

第4空：laste=A[x[j]].e

第5空：action(i+1)

第6空：action(1)