首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >给出一个时间表,找出医生办公室所有有冲突的预约

给出一个时间表,找出医生办公室所有有冲突的预约
EN

Stack Overflow用户
提问于 2012-09-24 10:48:05
回答 2查看 3.3K关注 0票数 1

您将获得“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),所以这是一个冲突。对于类似的问题,我们真的需要通过创建树或哈希图来使解决方案复杂化吗?

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

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2012-09-24 10:53:53

在链接答案中,未对约会列表进行排序,因此解决方案更为复杂。您说得对,如果对约会进行了排序,您只需遍历列表并跟踪到目前为止看到的最新结束时间。

另外,请注意,对列表进行排序是O(n lg n),因此如果需要O(n)解决方案,则不能只对其进行排序然后遍历它。

票数 1
EN

Stack Overflow用户

发布于 2012-09-24 10:53:12

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

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

https://stackoverflow.com/questions/12558261

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档