区间调度IntervalScheduling · bigrandall.io代码：#
#include <iostream>
#include <vector>
using namespace std;
int _count[100][100]; //构造最优矩阵
int p[100][100];
int numbers[100];
void dp(int start[], int finish[],int TASK_COUNT) {
for (int
总结：#
区间调度的实验采用了结束时间先后为顺序排序。按照排序依次比较看事件是否匹配，如果匹配则加入。贪心算法，优先选择最早结束的需求，确保资源尽可能早地被释放，把留下来满足其他需求的时间最大化。具体伪代码如下所示，算法结束后集合A中会保留所有相容请求，A的大小即是最大相容数量。Aijj为Sij最优解，另其中的任务按照结束时间递增排序,令ak是Aij的第一个结束的任务,如果ak=am,则证明成立。否则我们将ak用am替换，则它成为了另一个解A’ij，同样是最优解。所以即将任务以结束时间递增排序，第一个结束的任务一定在最优解中，依次找出子问题中最先结束，且开始时间在前一个解最后一个任务结束之间之后。复杂度为O(n)。同时很容易得出有递归和递推两种形式，一般采用递推。
len
=
2
; len
<=
TASK_COUNT
+
2
; len
++
) {
for (int begin = 0; begin <= TASK_COUNT + 1; begin++) {
int end = begin + len - 1;
int max = 0;
int slice = 0;
int k;
for (k = begin + 1; k <= end - 1; k++) {
if (start[k] >= finish[begin]&&finish[k]<=start[end]) {
int temp = _count[begin][k] + _count[k][end] + 1;
if (temp > max) {
max = temp;
slice = k;
}
}
}
p[begin][end] = slice;
_count[begin][end] = max;
}
}
}
void printDp( int begin, int end) {
int pos = p[begin][end];
if (pos == 0)
return;
cout << numbers[pos] << " ";
printDp(begin, pos);
printDp(pos, end);
}
int main() {
vector<int> vfinish;
vector<int> vstart;
//插入数组前置数值-1
vstart.push_back(-1);
vfinish.push_back(-1);
int number;
cout << "请分别输入各个事件的开始跟结束时间：" << endl;
while (1){
cin >> number;
vstart.push_back(number);
cin >> number;
vfinish.push_back(number);
if (cin.get() == '\n')
break;
}
//插入数组后置数值255
vstart.push_back(255);
vfinish.push_back(255);
int *start = new int[vstart.size()];
if (!vstart.empty())
memcpy(start, &vstart[0], vstart.size()*sizeof(int));
int *finish = new int[vfinish.size()];
if (!vfinish.empty())
memcpy(finish, &vfinish[0], vfinish.size()*sizeof(int));
int TASK_COUNT = vstart.size()-2;
for(int i=0;i<vstart.size();i++)
numbers[i]=i;
cout << "图例如下：" << endl; //输出图示
for (int i = 0; i <= TASK_COUNT; i++) {
cout << i << ":";
for (int j = 0; j < start[i]; j++) {
cout << " ";
}
for (int j = start[i]; j < finish[i]; j++)
cout << "■";
cout << endl;
}
for(int i=0;i<TASK_COUNT+2;i++){//按照结束时间排序
for(int j=0;j<TASK_COUNT+1;j++){
if(finish[j]>finish[j+1]){
std::swap(finish[j],finish[j+1]);
std::swap(start[j],start[j+1]);
std::swap(numbers[j],numbers[j+1]);
}
}
}
for (int i = 0; i <= TASK_COUNT + 2; i++) {
for (int j = 0; j <= TASK_COUNT + 2; j++) {
_count[i][j] = 0;
p[i][j] = 0;
}
}
dp(start, finish, TASK_COUNT);
cout << "总共可完成的事件个数为：" << _count[0][TASK_COUNT + 1] << endl;
cout << "完成的事件为：";
printDp(0, TASK_COUNT + 1);
return 0;
}