您将获得“n”个约会。每个约会都包含开始时间和结束时间。您必须高效地恢复所有冲突的约会,开始时间和结束时间从几分钟到几年不等。我看到了一个帖子:FInd overlapping appointments in O(n) time?,和这个非常相似。但仍有疑问。
我的问题是,如果我们给出了一个排序的时间表,比如:(6:30-6:35),(6:40-7:10) (7:25-7:40),(7:35-7:50)等等。
我们能不能不遍历日程表,确保下一个约会只在前一个约会结束后才开始?在这种情况下,我们对安排预约的可能时间施加了非常严格的限制。在这个例子中,我们知道从7:35开始的约会是在最后一个约会结束之前(7:40),所以这是一个冲突。对于类似的问题,我们真的需要通过创建树或哈希图来使解决方案复杂化吗?
请指出可以绕过此检查的情况,并证明此条件无效。
发布于 2012-09-24 10:53:53
在链接答案中,未对约会列表进行排序,因此解决方案更为复杂。您说得对,如果对约会进行了排序,您只需遍历列表并跟踪到目前为止看到的最新结束时间。
另外,请注意,对列表进行排序是O(n lg n),因此如果需要O(n)解决方案,则不能只对其进行排序然后遍历它。
发布于 2012-09-24 10:53:12
当然,解决方案可以在O(n)时间内执行,如果正如您所说的“我们有一个已排序的时间表”。您提到的问题是假设时间没有排序。
https://stackoverflow.com/questions/12558261
复制相似问题