问确定区间的成员约束子区间的算法
EN

Stack Overflow用户

提问于 2017-04-08 00:34:09

回答 1查看 40关注 0票数 0

给定有开始时间和结束时间的项目列表(例如，直到但不包括在日历月内的开始日和结束日)，在任何一个间隔内成员可以构造的跨越间隔的最小数目是多少，以及在上述间隔中存在哪些成员？我认为一个例子会让这个问题变得更清楚(我觉得我没有合适的词汇来描述这个问题)：

输入：A，B，C，D，E

A: 1,3
B: 2,4
C: 1,10
D: 5,7
E: 5,10

输出

1-2: A,C
2-3: A,B,C
3-4: B,C
4-5: C
5-7: C,D,E
7-10: C,E

如果有一个缺口，我也想知道(比如说4-5没有被任何项目覆盖)。

我已经考虑了每个项目的基本过程，以及最小-最大的考虑，特别是BSTs，特别是区间树，但是对于这里的最佳方法，我有点不知所措。谢谢!

发布于 2017-04-08 06:21:03

(注意:由于所有的日子都在一个月内，你事先就知道所有可能的日子是什么--而且不多--所以你可以通过使用最多31个桶的桶排序将上述所有三个步骤组合成一个简单的传递。)

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/43288923

复制

相似问题

问确定区间的成员约束子区间的算法EN