活動安排問題
問題描述
設有n個活動的集合E={1，2，…，n}，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內只有一個活動能使用這一資源，每個活動i都有要求使用該資源的起始時間si和結束時間fi，且si<fi，如果選擇了活動i，則它在半開時間區間[si，fi)內占用資源，若區間[si，fi)與區間[sj，fj)不相交，則稱活動i和活動j是相容的，也就是說，當 s i ≥ f j s_i \geq f_j si?≥fj? 或 s j ≥ f i s_j \geq f_i sj?≥fi? 時，活動i與活動j相容，活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合，
舉例說明
例如，設待安排的11個活動的開始時間和結束時間按結束時間的非遞減排列如下：
| i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| s[i] | 1 | 3 | 0 | 5 | 3 | 5 | 6 | 8 | 8 | 2 | 12 |
| f[i] | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
因為問題比較簡單，下面直接上代碼
C++代碼實作
#include<iostream>
using namespace std;
//貪心選擇演算法
void GreedySelector(int n, int s[], int f[], bool A[]) {
A[1] = true;
int j = 1;
for (int i = 2; i <= n ; i++) {
if (s[i] > f[j]) {
A[i] = true;
j = i;
} else {
A[i] = false;
}
}
}
int main() {
bool A[12];
int n = 11;
int s[] = {0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12};
int f[] = {0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};
GreedySelector(n, s, f, A);
for (int i = 1; i <= 11; i++) {
cout << A[i] << " ";
}
cout << endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/249896.html
標籤：其他
上一篇：前端日志監控 - Nodejs 通過 ElasticSearch 查詢資料流程
下一篇：JavaScript基礎1