本文介绍了在 O(n) 时间内找到重叠的约会?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我最近在一次采访中被问到这个问题.即使我能够想出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) 时间内找到重叠的约会?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

06-23 23:42