面试调度算法

Question

我正在尝试考虑一种算法，该算法总是在最佳可能的时间内产生最佳解决方案来解决这个问题：

有 n 个求职者，他们在 k 个房间里安排了一天中不同时间的面试。每个房间的采访都有特定的时间表，每次采访都有指定的开始时间 (s_i)、结束时间 (f_i)，以及面试室（r_i）。所有时间单位总是整数。此外，我们需要全天安排与当前正在接受采访的人的合影。这些照片并不能有效地拍摄任何时间，但在一天中的某个时间点，每个受访者都必须在照片中。如果我们在时间 t 安排一张图片，则当前正在接受采访的所有人员都会出现在该图片中。拍照不影响其余每次访谈起止时间。所以问题是这样的：有一个无序列表的采访，每个都有变量 (s_i, f_i, r_i)，你如何确保每个面试候选人都在照片中，同时尽可能少拍照片？

所以理想情况下我们会在有尽可能多的人在场时拍照，以尽量减少拍照数量。我最初的想法是一种蛮力，但这将是一个非常糟糕的大 O 运行时。在返回尽可能少的照片的同时尽量减少该算法的运行时间非常重要。话虽这么说，如果你能想到一个不能完美解决问题的快速贪婪算法，我也很想听听。

我确信我在这里的描述远非完美无缺，所以如果您希望我澄清任何内容，请随时发表评论，我会尽快回复您。

Answer 1

从以下观察开始：

每次采访必须至少拍一张照片，因为我们无法在受访者到达之前或他们离开之后给他们拍照。
仅在时间 s_i 和 f_i.
在一个到达事件s_i之后，如果下一个事件j是到达，则不需要在s_{之间拍照i} 和 s_j，因为在 s_i 可用的每个人在 s_{j[=60 仍然可用=].}
因此，您可以让一组可用的受访者 "build up" 通过到达事件（最多 k 个）并等到有人即将离开时拍照。

因此我认为以下算法应该可行：

将到达和离开时间放入列表中并排序（时间应保持标记为 "arrival" 或 "departure" 以及受访者的索引）。
创建一个大小为 n 的布尔数组 A 以跟踪每个受访者是否有空（采访正在进行中）。
创建一个大小为 n 的布尔数组 P 以跟踪每个受访者是否已被拍照。
循环排序的时间列表（索引变量i）：

一个。如果遇到到达，将A[i]设置为true。

b。如果遇到离开j，请检查P[j]以查看离开的人是否已被拍照。如果没有，请立即拍照并记录其效果（对于所有 A[k] = true 集 P[k] = true）。最后将A[i]设置为false.

排序是 O(n log n)，循环有 2n 次迭代，检查数组是 O(1)。但是由于在每次拍照事件中，你可能需要循环 A，总的运行时间在最坏的情况下是 O(n²)（如果没有采访在时间上重叠，就会发生。

Answer 2

这是一个 O(n log n) 解决方案：

第一步：将所有访谈的起止时间分别排序，同时记录排序到的位置（即原始索引和排序后的索引）。这导致下面的 4 个数组

sst[]（sst = 排序开始时间）
sft[]（sft = 排序完成时间）
sst2orig[] (sst index to original index)
sft2orig[] (sst index to original index)

注：根据以上4个数组的定义， “sst2orig[j] = i & sst2orig[k] = i”表示 interview [i] 有开始时间 sst[j] 和结束时间 sft[k]

第 2 步：定义一个布尔数组 p_taken[] 来表示面试的候选人是否已经被照相。数组中的所有元素最初都将设置为 false。

第 3 步：循环

std::vector<int> photo_time;
int last_p_not_taken_sst_index = 0;
for (int i=0; i<sft.size; i++) {
  // ignore the candidate already photographed
  if (p_taken[sft2orig[sft[i]]]) continue;
    
  // Now we found the first leaving candidate not phtographed, we
  // must take a photo now.
  photo_time.push_back(sft[i]);
    
  // So we can now mark all candidate having prior sst[] time as
  // already photographed.  So, we search for the first elm. in
  // sst[] that is greater than sft[i], and returns the index.   
  // If all elm. in sst[] is smaller than sft[i], we return sst.size().
  // This could be done via a binary search
  int k = upper_inequal_bound_index(sst, sft[i]);
  
  // now we can mark all candidate with starting time prior than sst[k]
  // to be "photographed".  This will include the one corresponding to
  // sft[i]
  for (int j=last_p_not_taken_sst_index; j<k; j++)
     p_taken[sst2orig[j]] = true;
  last_p_not_taken_sst_index = k;
}

最终答案保存在photo_time，照片数量photo_time.size()。

时间复杂度：

第 1 步：排序：O(n log n)

第二步：初始化p_taken[]: O(n)

第 3 步：我们循环 n 次，并且在每个循环中

3-1 检查 p_taken: O(1)

3-2 二分查找：O(log n)

3-3 标记候选人：聚合 O(n)，因为我们只标记一次，每个候选人。

因此，第 3 步的总体情况：O(n x ( 1 + log n) + n) = O(n log n)

第 1 ~ 3 步，总计：O(n log n)

请注意，第 3 步可以进一步优化：我们可以缩小以排除那些已经在 binary-searched 之前的范围。但最坏的情况仍然是每个循环 O(log n)。因此总数仍然是 O(n log n)

面试调度算法

Interview Scheduling Algorithm

algorithm

dynamic-programming

greedy

divide-and-conquer