algorithm - 2009 年 ACM-ICPC 世界总决赛的飞机调度挑战

Question

出于好奇，我查看了 2009 年 ACM 国际大学生程序设计竞赛的问题集。这些问题很有趣。它们可在 http://cm.baylor.edu/resources/pdf/2009Problems.pdf 获得.我无法想出解决问题 1 的算法，我将在此处重现。它在办公室引发了热烈的讨论，我们认为我们非常接近答案，但如果有人能找到/制定出完整的解决方案(不需要代码)，我们将不胜感激。

为了您的方便，我将在这里重现问题:

问题1

考虑安排降落在机场的飞机的任务。进来的飞机报告它们的位置、方向和速度，然后管制员必须制定一个着陆计划，使所有飞机安全着陆。一般来说，连续着陆之间的时间越长，着陆计划就越“安全”。这段额外的时间让飞行员有机会对不断变化的天气和其他意外情况使用react。幸运的是，这个调度任务的一部分可以自动化——这就是你进来的地方。你将获得飞机着陆的情景。每架飞机都有一个时间窗口，在此期间它可以安全着陆。您必须计算一个指令，让所有飞机在这些时间窗内着陆。此外，飞机着陆应尽可能延长，以便连续着陆之间的最小时间间隔尽可能大。例如，如果三架飞机分别在上午 10:00、10:05 和 10:15 降落，则最小间隔为五分钟，出现在前两架飞机之间。并非所有间隙都必须相同，但最小间隙应尽可能大。

输入

输入文件包含几个测试用例，其中包含着陆场景的描述。每个测试用例都以包含单个整数 n(2 ≤ n ≤ 8)的行开头，这是场景中的飞机数量。接下来是 n 行，每行包含两个整数 a_i, b_i，它给出闭区间 [a_i, b_i] 的开始和结束，在此期间i飞机可以安全降落。数字 a_i 和 b_i 以分钟为单位指定并满足 0 ≤ a _i ≤ b_i ≤ 1440。输入以包含单个整数零的行终止。

输出

对于输入中的每个测试用例，打印其用例编号(从 1 开始)，然后是连续着陆之间可实现的最小时间间隔。打印分为分钟和秒的时间，四舍五入到最接近的秒。遵循示例输出的格式。

示例输入

3
0 10
5 15
10 15
2
0 10
10 20
0

示例输出

Case 1: 7:30
Case 2: 20:00

Answer 1

我将给出算法的草图。

首先是你binary search通过答案(航类之间的最小间隔)。为此，对于每个选定的间隔 T，您必须能够检查是否有可能实现它。如果有可能实现T，那么你就试着把它变小，如果不行 - 让它变大。

要检查您是否可以达到 T，请尝试所有 n!飞机可能着陆的顺序(8!足够小，可以让这个算法及时工作)。对于每个排列 P1...Pn，您尝试在 greedy manner 中分配时间:

int land = a[0];
for (int i = 1; i < n; i++) {
    land = max(a[i], land + **T**);
    if (land > b[i]) return "CAN NOT ACHIEVE INTERVAL T";
}
return "CAN ACHIEVE";