问题描述
我最近在一次采访中被问到这个问题.即使我能够想出O(n²) 解决方案，面试官还是痴迷于O(n) 解决方案.我还检查了我理解的 O(n logn) 的其他几个解决方案，但是 O(n) 解决方案仍然不是我的那杯茶，它假设约会按开始时间排序.
I was recently asked this question in an interview. Even though I was able to come up the O(n²) solution, the interviewer was obsessed with an O(n) solution. I also checked few other solutions of O(n logn) which I understood, but O(n) solution is still not my cup of tea which assumes appointments sorted by start-time.
谁能解释一下?
问题陈述:您有n次约会.每个约会都包含开始时间和结束时间.您必须有效地重新调整所有冲突的约会.
Problem Statement: You are given n appointments. Each appointment contains a start time and an end time. You have to retun all conflicting appointments efficiently.
人:1,2,3,4,5
应用开始:2、4、29、10、22
应用结束:5、7、34、11、36
答案:2x1 5x3
O(n logn) 算法: 像这样分离起点和终点:
O(n logn) algorithm: separate start and end point like this:
2s, 4s, 29s, 10s, 22s, 5e, 7e, 34e, 11e, 36e
然后对所有这些点进行排序(为简单起见，我们假设每个点都是唯一的):
then sort all of this points (for simplicity let's assume each point is unique):
2s, 4s, 5e, 7e, 10s, 11e, 22s, 29s, 34e, 36e
如果我们有连续的开始而没有结束，那么它是重叠的:2s, 4s相邻所以有重叠
if we have consecutive starts without ends then it is overlapping:2s, 4s are adjacent so overlapping is there
我们会保留s"的计数，每次遇到它时+1，遇到e时我们将计数减1.
We will keep a count of "s" and each time we encounter it will +1, and when e is encountered we decrease count by 1.
推荐答案
这个问题的一般解决方案是不可能在O(n).
The general solution to this problem is not possible in O(n).
至少需要按预约开始时间排序，这需要O(n log n).
At a minimum you need to sort by appointment start time, which requires O(n log n).
如果列表已经排序，则有一个 O(n) 解决方案.该算法主要涉及检查下一个约会是否与之前的约会重叠.这个有点微妙，因为当你运行它时，你实际上需要两个指向列表的指针:
There is an O(n) solution if the list is already sorted. The algorithm basically involves checking whether the next appointment is overlapped by any previous ones. There is a bit of subtlety to this one as you actually need two pointers into the list as you run through it:
- 正在检查的当前约会
- 目前遇到的最晚结束时间的约会(可能不是之前的约会)
O(n) 未排序情况的解决方案只有在您有其他约束的情况下才能存在，例如固定数量的约会时间段.如果是这种情况，那么您可以使用 HashSets 来确定每个时间段覆盖哪些约会，算法大致如下:
O(n) solutions for the unsorted case could only exist if you have other constraints, e.g. a fixed number of appointment timeslots. If this was the case, then you can use HashSets to determine which appointment(s) cover each timeslot, algorithm roughly as follows:
- 为每个时隙创建一个 HashSet - O(1) 因为时隙号是一个固定的常量
- 对于每个约会，将其 ID 号存储在它涵盖的时隙的 HashSets 中 - O(n) 因为更新时间段的恒定数量是 O(1) 每个约会
- 遍历槽，检查重叠 - O(1)(或者 O(n) 如果你想迭代重叠约会以将它们作为结果返回)
- Create a HashSet for each timeslot - O(1) since timeslot number is a fixed constant
- For each appointment, store its ID number in HashSets of slot(s) that it covers - O(n) since updating a constant number of timeslots is O(1) for each appointment
- Run through the slots, checking for overlaps - O(1) (or O(n) if you want to iterate over the overlapping appointments to return them as results)
这篇关于在 O(n) 时间内找到重叠的约会?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！