C++經典演算法題-最大訪客數

• 2020 年 2 月 13 日
• 筆記

21.Algorithm Gossip: 最大訪客數

說明

現將舉行一個餐會，讓訪客事先填寫到達時間與離開時間，為了掌握座位的數目，必須先估計不同時間的最大訪客數。

解法

這個題目看似有些複雜，其實相當簡單，單就計算訪客數這個目的，同時考慮同一訪客的來訪時間與離開時間，反而會使程式變得複雜；只要將來訪時間與離開時間分開處理就可以了，假設訪客 i 的來訪時間為x[i]，而離開時間為y[i]。

在資料輸入完畢之後，將x[i]與y[i]分別進行排序（由小到大），道理很簡單，只要先計算某時之前總共來訪了多少訪客，然後再減去某時之前的離開訪客，就可以輕易的解出這個問題。

程式碼示例

#include <stdio.h>  #include <stdlib.h>  #define MAX 100  #define SWAP(x,y) {int t; t = x; x = y; y = t;}        int partition(int[], int, int);      void quicksort(int[], int, int); // 快速排序法      int maxguest(int[], int[], int, int);        int main(void) {          int x[MAX] = {0};          int y[MAX] = {0};          int time = 0; int count = 0;            printf("n輸入來訪與離開125;時間(0~24)："); printf("n範例：10 15");          printf("n輸入-1 -1結束"); while(count < MAX) {                printf("n>>");              scanf("%d %d", &x[count], &y[count]); if(x[count] < 0)                  break; count++;          }            if(count >= MAX) {              printf("n超出最大訪客數(%d)", MAX); count--;          }            //  預先排序          quicksort(x, 0, count);          quicksort(y, 0, count);            while(time < 25) {              printf("n%d 時的最大訪客數：%d",                      time, maxguest(x, y, count, time));              time++;          }            printf("n");            return 0;      }        int maxguest(int x[], int y[], int count, int time) { int i, num = 0;            for(i = 0; i <= count; i++) { if(time > x[i])              num++; if(time > y[i])              num--;          }            return num;      }        int partition(int number[], int left, int right) {            int i, j, s;            s = number[right]; i = left - 1;            for(j = left; j < right; j++) { if(number[j] <= s) {              i++;              SWAP(number[i], number[j]);          }          }            SWAP(number[i+1], number[right]); return i+1;      }        void quicksort(int number[], int left, int right) { int q;            if(left < right) {              q = partition(number, left, right); quicksort(number, left, q-1); quicksort(number, q+1, right);          }      }