高效见面会

来自计算思维百科
跳转至: 导航搜索
高效见面会1.png

某一天,在微软亚洲研究院有N个面试要进行,它们的时间分别为(B[i], E[i])(B[i]为面试开始时间,E[i]为面试结束时间)。假设一个面试者一天只参加一个面试。为了给面试者提供一个安静便于发挥的环境,我们希望将这N个面试安排在若干个面试点。不同的面试在同一个时间不能被安排在同一个面试点。如果你是微软亚洲研究院的HR,现在给定这N个面试的时间之后,你能计算出至少需要多少个面试点吗?请给出一个可行的方案。

解决方案

方案一

我们已经很清楚,时间段上出现重叠的面试,一定会被安排在不同的面试点。i与j的时间段重叠,那么E[i] > B[j]。也就是说把i与j的起始结束时刻排序,将得到顺序为B[i],B[j],E[i],E[j],而对于不重叠,排序的结果应该是B[i],E[i],B[j],E[j]。这一个很重要的信息——对于重叠,必然存在BBEE的情况,那么我们先将所有的时刻排序,然后依次遍历,遇到B就+1,遇到E就-1,因此,只有BEBEBEBE……的情况下,我们的计数器始终为0,如果有BB情况,那么就会出现2的情况,BBB则会出现3。BB代表两个时间段的重叠,BBB代表3个时间段的重叠,利用这种方法,重叠次数就是最小的地点数。

运用的计算思维

这种精妙算法将问题转化为用计数器计算时间段重叠次数,体现了转化的计算思维。

方案二-贪心算法

要使面试的地点最少,就必须尽可能的把面试时间互相不重叠的面试安排在同一个面试点。即将不重叠的面试安排到一个面试点!即将不重叠的面试安排到一个面试点!

步骤如下:

  1. 把面试集合S中的元素按其结束时间的递增顺序排列;
  2. 求其最大相互兼容面试集合M,并从原始集合S中删除之;
  3. 求集合S-M的最大相互兼容面试集合Q,并从集合S-M中删除之。重复此过程直到原始面试集合S中为空集为止;
  4. 统计求出的最大相互兼容面试集合的个数,即是面试集合S所需的最少面试点个数。

下图中用矩形框起来的面试为所属集合的最大相互兼容集合,一共有5个,即至少需要5个面试点。

高效见面会2.png

运用的计算思维

贪心算法则运用的是优化的计算思维。、

参考文献

《编程之美》小组.《编程之美》.电子工业出版社.2008