出于好奇，我正在检查2009 ACM国际大学编程竞赛的问题。这些问题很有趣。可在http://cm.baylor.edu/resources/pdf/2009Problems.pdf上找到它们。我无法提出解决问题1的算法，我将在这里重现。它在办公室引起了热烈的讨论，我们认为我们已经很接近答案了，但是如果有人可以找到/制定出完整的解决方案（不需要代码），我们将不胜感激。
为了方便起见，我将在此处重现问题：
考虑安排在机场降落的飞机的任务。进来的飞机报告其位置，方向和速度，然后管制员必须制定着陆时间表，以使所有飞机安全着陆。通常，连续降落之间的时间越长，降落时间表越“安全”。这些额外的时间使飞行员有机会对天气变化和其他意外做出反应。幸运的是，可以自动执行此计划任务的一部分- 这就是您要进入的地方。您将获得飞机着陆的场景。每架飞机都有一个可以安全着陆的时间窗。您必须计算遵守这些时间窗口的所有飞机着陆的命令。此外，飞机的着陆区应尽可能伸展，以使连续着陆之间的最小时间间隔尽可能大。例如，如果三架飞机分别在上午10:00，上午10:05和上午10:15降落，则最小间隔为五分钟，这是前两架飞机之间的间隔。并非所有间隙都必须相同，但最小的间隙应尽可能大。
输入文件包含几个测试用例，其中包含着陆方案的描述。每个测试用例开始于包含单个整数的线 Ñ （2≤ Ñ ≤8），这是在场景中的飞机的数量。接下来是 n 条线，每条线包含两个整数 a i， b i，给出了第 i 个平面可以安全着陆的闭合间隔[ a i， b i ] 的开始和结束。数字 一个 我 和 b 我 以分钟指定和满足0≤ 一个 我 ≤ b 我 ≤1440。输入终止与含有单个整数零的线。
对于输入中的每个测试用例，请打印其用例编号（以1开头），然后打印连续着陆之间可达到的最小时间间隔。打印时间分为分钟和秒，四舍五入到最接近的秒。遵循示例输出的格式。
样本输入
3 0 10 5 15 10 15 2 0 10 10 20 0
样本输出
Case 1: 7:30 Case 2: 20:00
我会做这样的事情：
#include <stdio.h> #include <stdlib.h> #include <string.h> typedef uint MASK; #define INPUT_SCALE 60 #define MAX_TIME (1440 * 60) void readPlaneData(int& endTime, MASK landingMask[MAX_TIME], int index) { char buf[128]; gets(buf); int start, end; sscanf(buf, "%d %d", &start, &end); for(int i=start * INPUT_SCALE; i<=end * INPUT_SCALE; i++) landingMask[i] |= 1 << index; if(end * INPUT_SCALE > endTime) endTime = end * INPUT_SCALE; } int findNextLandingForPlane(MASK landingMask[MAX_TIME], int start, int index) { while(start < MAX_TIME) { if(landingMask[start] & (1 << index)) return start; start++; } return -1; } bool canLandPlanes(int minTime, MASK landingMask[MAX_TIME], int planeCount) { int next = 0; for(int i=0; i<planeCount; i++) { int nextForPlane = findNextLandingForPlane(landingMask, next, i); if(nextForPlane == -1) return false; next = nextForPlane + minTime; } return true; } int main(int argc, char* argv[]) { while(true) { char buf[128]; gets(buf); int count = atoi(buf); if(count == 0) break; MASK landingMask[MAX_TIME]; memset(landingMask, 0, sizeof(landingMask)); int endTime = 0; for(int i=0; i<count; i++) readPlaneData(endTime, landingMask, i); while((endTime > 0) && !canLandPlanes(endTime, landingMask, count)) endTime--; printf("%d:%02d\n", endTime / 60, endTime % 60); } }
