雁過無痕

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

擴(kuò)展問題一：

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

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

//arr[][0]為面試開始時(shí)間，arr[][1]為面試結(jié)束時(shí)間
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;
}