雁过无痕

《编程之美》读书笔记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;
}