# Activity_Selection 活動選擇

user_3763047219
c_cpp
2 years ago
1.2 kB
3
Indexable
Never
```#include <iostream>

int main()
{
int n = 0;
int s[1001] = {0}, f[1001] = {0};
int anum[1001] = {0};
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", &s[i]);
}
for (int i = 1; i <= n; i++) {
scanf("%d", &f[i]);
}
for (int i = 1; i <= n; i++) {//多設一個array 紀錄活動順序
anum[i] = i;
}

for (int i = 1; i < n; i++) { //對活動進行排序
for (int j = n; j >= i ; j--) {//從n排回來比較不會出錯
if (s[j] < s[j - 1]) {
int temp = s[j];
s[j] = s[j - 1];
s[j - 1] = temp;

int temp2 = f[j];
f[j] = f[j - 1];
f[j - 1] = temp2;

int temp3 = anum[j];
anum[j] = anum[j - 1];
anum[j - 1] = temp3;
}
}
}

int n2 = n;
int ans[1001] = {0};
ans[1] = anum[n];//先放入起始時間最大的活動

int sum = 1;//活動數量
for (int i = n-1; i > 0; i--) {//取起始時間最大活動 vs 結束時間第二大
if (f[i] <= s[n2]) {
sum++;
ans[sum] = anum[i];
n2 = i;
}
}

printf("%d\n", sum);
printf("(%d",ans[sum]);// 先印出起始時間最小活動
for (int i = sum-1; i >= 1; i--) {
printf(",%d", ans[i]);
}
printf(")");
}```