1

你有'n'个约会。每个约会都包含开始时间和结束时间。您必须有效地重新调整所有有冲突的约会，开始时间和结束时间可以从几分钟到几年不等。我看到了帖子：在 O(n) 时间内找到重叠的约会？这与此非常相似。但仍有一个疑问。

我的问题是，如果我们有一个排序的时间表，比如说：（6：30-6：35），（6：40-7：10）（7：25-7：40），（7：35-7： 50）等等。

我们可以不遍历日程表并确保下一个约会应该在前一个约会结束后才开始吗？在这种情况下，我们对安排约会的可能时间施加了非常严格的限制。在这个例子中，我们知道从 7:35 开始的约会在最后一个约会结束 (7:40) 之前，所以这是一个冲突。我们是否真的需要通过创建树或哈希映射来使解决方案复杂化，如类似问题的链接中评价最高的解决方案中提到的那样？

请指出可以绕过此检查并证明此条件无效的情况。

4

2 回答 2

1

在链接的答案中，列表约会未排序，因此解决方案更复杂。您是正确的，如果约会已排序，您只需遍历列表并跟踪迄今为止看到的最新结束时间。

另外，请注意，列表的排序是O(n lg n)，所以如果你想要一个解决方案，你不能只是对它进行排序然后遍历它O(n)。

于 2012-09-24T02:53:52.610 回答
0

当然，如果您说“我们有一个已排序的时间表”，则可以在 O(n) 时间内执行该解决方案。您引用的问题是假设时间没有排序。

于 2012-09-24T02:53:11.860 回答