查找O（n）时间重叠的约会呢？ [英] FInd overlapping appointments in O(n) time?

问题描述

我最近问这个问题进行了采访。即使我能想出的为O（n ^ 2）的解决方案，面试官迷恋一个O（n）的解决方案。我还检查了O（n日志n）的，我明白了一些其他的解决方案，但为O（n）解决方案仍然不是我杯茶它假定预约排序的启动时间。

I was recently asked this question in an interview. Even though I was able to come up the O(n^2) solution, the interviewer was obsessed with an O(n) solution. I also checked few other solutions of O(nlog n) which I understood, but O(n) solution is still not my cup of tea which assumes appointments sorted by start-time.

谁能解释一下吗？

问题描述：

您给予'N'约会。每个约会包含开始时间和结束时间。你必须能够有效地retun所有冲突的约会。

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

Person: 1,2,3,4,5 App St: 2,4,29,10,22 App End: 5,7,34,11,36

答：2X1 5X3

O（n日志n）的算法：不同的起点和终点是这样的：

O(nlog n) algorithm: separate start and end point like this:

2S，4S，29S，10S，22S，5E，7E，34E，11E，36E

2s,4s,29s,10s,22s,5e,7e,34e,11e,36e

然后进行排序所有这些点（为简单起见让我们假设每个点是唯一的）：

then sort all of this points (for simplicity lets assume each point is unique):

2S，4S，5E，7E，10秒，11e上，22S，29S，34E，36E

2s,4s,5e,7e,10s,11e,22s,29s,34e,36e

它，我们已经连续启动，而两端则是重叠的： 2S，4S相邻所以重叠有

it 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).

在最低限度，你需要预约开始时间，这就要求 0排序（N日志N）。

At a minimum you need to sort by appointment start time, which requires O(n log n).

有一个 O（N）解决方案如果该列表已经按。该算法主要包括检查任何previous的人下一个约会是否重叠。有一点微妙的这一个，你实际上需要两个指针到列表中，你通过它运行：

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:

• 在所检查的当前预约
• 在迄今所遇到的最晚结束时间预约（这可能不是previous预约）

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），因为时隙数是固定不变
• 对于每一个约会，存储插槽（S），它涵盖了HashSets它的ID号 - O（N）自更新时隙的恒定数是 0（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）时间重叠的约会呢？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！