雁過無痕

《編程之美》讀書筆記05： 1.9 高效率的安排見面會

擴展問題一：

實際上就是求區間的最大重疊次數。書上P57的算法，比較巧妙，但要注意的是：排序時要用到雙關鍵字比較，當兩個值相等時，屬于時間段開始的一定要排在屬于時間段結束的后面，只有這樣才能保證結果的正確性。（假設[3, 4）和[4, 5)能在同一個地方舉行。書上區間段都是用閉區間，本文采用前閉后開。）

考慮到面試安排的時間一般安排在某個整點、半點或者某刻，可以采用計數的方法，如果都安排在整點，每處理一個區間[a, b)，就對[a, b)間的所有整數計數一次。最后從計數結果中找出最大值即可。時間復雜度為O(n)（準確的講，應該是O(k*n)，k為區間的最大間隔，k<=24）。如果面試安排時間在某個半點、刻，可以對原來的時間乘以一個整數（比如2或4，這實際上就是桶排序設置桶間隔為0.5或0.25）。

//arr[][0]為面試開始時間，arr[][1]為面試結束時間
int max_places (int arr[][2], size_t sz)
{
  if (arr==NULL || sz<1) return 0; 
  const size_t MAX_HOURS=24;
  int count[MAX_HOURS]={0}; 
  int max=0, j=0; 
  size_t i=0;
  for (i=0; i<sz; ++i)
    for (j=arr[i][0]; j<arr[i][1]; ++j) ++count[j];
  for (i=0; i<MAX_HOURS; ++i)
    if (count[i]>max) max=count[i];
  return max;
}