Activity_Selection 活動選擇

#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(")");
}