算法—會議最大合理安排問題

參考：趣學(xué)算法

代碼：

#include <stdio.h> #include <stdlib.h> typedef struct meet {int beg;//開始int end;//結(jié)束int num;//會議編號 }meet; int cmp44(meet m1,meet m2) {//越早結(jié)束的越優(yōu)先，一樣早結(jié)束的越晚開始的越優(yōu)先if (m1.end == m2.end) {if (m1.beg > m2.beg) {return 1;}}else if (m1.end < m2.end) {return 1;}return 0; } int quickSort(meet a[], int l, int h) {//快速排序int i = l, j = h;meet p = a[l];while (i < j) {while (i<j&&cmp44(p,a[j])) {//從右往左遍歷查找與p相比，滿足會議的結(jié)束時間從小到大排序，會議開始時間從大到小j--;}if (i < j) {a[i++] = a[j];}while (i < j&&cmp44(a[i],p)) {//從左往右遍歷查找與p相比，滿足會議的結(jié)束時間從小到大排序，會議開始時間從大到小i++;}if (i < j) {a[j--] = a[i];}}a[i] = p;//分界的值，左邊小于等于p，右邊大于preturn i; } void fenZhi(meet a[], int l, int h) {//分治if (l < h) {int mid = quickSort(a, l, h);//以mid為分界線，進(jìn)行分治，然后遞歸下去排序fenZhi(a, l, mid - 1);fenZhi(a, mid + 1, h);} } void meetSelect(meet Meet[],int n) {int last = Meet[0].end;int ans = 0;//統(tǒng)計(jì)會議總數(shù)ans++;printf("選擇的會議%d,開始時間為%d,結(jié)束時間為%d\n", Meet[0].num, Meet[0].beg, Meet[0].end);for (int i = 1; i < n; i++) {if (Meet[i].beg >= last) {ans++;last = Meet[i].end;printf("選擇的會議%d,開始時間為%d,結(jié)束時間為%d\n",Meet[i].num,Meet[i].beg,Meet[i].end);}}printf("會議總數(shù)為%d\n",ans); } int main() {meet Meet[100];int n;printf("輸入會議數(shù):");scanf_s("%d", &n);for (int i = 0; i < n; i++) {scanf_s("%d%d", &Meet[i].beg, &Meet[i].end);Meet[i].num = i + 1;}fenZhi(Meet, 0, n - 1);printf("會議編號 會議開始時間 會議結(jié)束時間\n");for (int i = 0; i < n; i++) {printf("%d %d %d\n", Meet[i].num, Meet[i].beg, Meet[i].end);}meetSelect(Meet, n);printf("\n");system("pause");return 0; }

測試截圖：

時間復(fù)雜度O(nlogn)，空間復(fù)雜度O(1)

如果存在什么問題，歡迎批評指正！謝謝！

總結(jié)

以上是生活随笔為你收集整理的算法---会议最大安排问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。