在 O(n) 时间内找到重叠的约会? [英] FInd overlapping appointments in O(n) time?

问题描述

我最近在一次采访中被问到这个问题.即使我能够想出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

Person: 1,2, 3, 4, 5
App Start: 2, 4, 29, 10, 22
App End: 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

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, 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) 时间内找到重叠的约会?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！