给定两个已排序的间隔列表，返回两个列表之间的重叠间隔
您将获得两个间隔列表，A和B。
在A中，间隔按起点排序。A中的所有间隔均不重叠。
同样，在B中，间隔按其起点排序。B中的任何间隔都没有重叠。
返回两个列表之间重叠的间隔。
示例：
A: {[0,4], [7,12]}
B: {[1,3], [5,8], [9,11]}
退货：
{[1,3], [7,8], [9,11]}
我在一次采访中得知这一点，被难住了。
我想比较两个列表之间的间隔。如果两者之间有重叠，请将重叠添加到结果列表中。然后，我以较小的起始间隔推进列表的指针，但在面试结束时无法得到有效的解决方案。
解决这个问题的最好方法是什么？
共有3个答案
下面是我在apache spark程序中用作复杂reduce步骤组件的算法实现：链接到另一个相关答案。奇怪的是，它也在斯卡拉。
以下是独立的算法：
type Gap = (Int, Int)
/** The `merge`-step of a variant of merge-sort
* that works directly on compressed sequences of integers,
* where instead of individual integers, the sequence is
* represented by sorted, non-overlapping ranges of integers.
*/
def mergeIntervals(as: List[Gap], bs: List[Gap]): List[Gap] = {
require(!as.isEmpty, "as must be non-empty")
require(!bs.isEmpty, "bs must be non-empty")
// assuming that `as` and `bs` both are either lists with a single
// interval, or sorted lists that arise as output of
// this method, recursively merges them into a single list of
// gaps, merging all overlapping gaps.
@annotation.tailrec
def mergeRec(
gaps: List[Gap],
gapStart: Int,
gapEndAccum: Int,
as: List[Gap],
bs: List[Gap]
): List[Gap] = {
as match {
case Nil => {
bs match {
case Nil => (gapStart, gapEndAccum) :: gaps
case notEmpty => mergeRec(gaps, gapStart, gapEndAccum, bs, Nil)
}
}
case (a0, a1) :: at => {
if (a0 <= gapEndAccum) {
mergeRec(gaps, gapStart, gapEndAccum max a1, at, bs)
} else {
bs match {
case Nil => mergeRec((gapStart, gapEndAccum) :: gaps, a0, gapEndAccum max a1, at, bs)
case (b0, b1) :: bt => if (b0 <= gapEndAccum) {
mergeRec(gaps, gapStart, gapEndAccum max b1, as, bt)
} else {
if (a0 < b0) {
mergeRec((gapStart, gapEndAccum) :: gaps, a0, a1, at, bs)
} else {
mergeRec((gapStart, gapEndAccum) :: gaps, b0, b1, as, bt)
}
}
}
}
}
}
}
val (a0, a1) :: at = as
val (b0, b1) :: bt = bs
val reverseRes =
if (a0 < b0)
mergeRec(Nil, a0, a1, at, bs)
else
mergeRec(Nil, b0, b1, as, bt)
reverseRes.reverse
}
它的工作原理与合并排序的合并步骤非常相似，但您必须查看整个间隔，而不是查看单个数字。原则保持不变，只是区分大小写变得非常讨厌。
编辑：不完全是这样。你想要交集，这里的算法会产生并集。你要么必须翻转相当多的if-其他-条件和min-max-函数，要么你必须使用de-Morgan定律进行预处理/后处理。原理仍然相同，但我绝对不想对交集重复整个练习。不要把它视为缺点，而是作为答案的一个特征：没有剧透；）
以下是一个实现，遵循罗马原则divide et impera：
首先，找到一个方法，对于给定的间隔对，该方法找到重叠（如果有的话）。
/* Cases: A behind B, A overlap at start, A part of B, B part of A,
overlap at end, B starts after A ended:
A: 2..3..4..5
Bs: | |
0..1 | |
0..1..2..3 |
0..1..2..3..4..5..6
| 3..4 |
| 4..5..6
| | 6..7
*/
case class Interval (lower: Int, upper: Int) {
def overlap (other: Interval) : Option [Interval] = {
if (lower > other.upper || upper < other.lower) None else
Some (Interval (Math.max (lower, other.lower), Math.min (upper, other.upper)))
}
}
这是有限责任的方法，决定两个间隔。
如果您不熟悉Scala： Interval是一个类，第一行可以作为构造函数读取。下层和上层应该是自解释的（Int类型）。该类有一个方法重叠，它接受类的第二个实例（其他）并返回重叠的新Interval。但包装到一个Option中，这意味着：如果没有找到重叠，我们返回无。如果我们找到一个，它是一些（Interval）。您可以帮助自己将此构造理解为List，它要么为空，要么仅包含一个元素。这是一种避免NullpointerException的技术，通过使用Type发出信号，表明可能没有结果。
如果一个间隔的上端低于另一个间隔的下端，则不能有重叠，因此我们返回无。
对于重叠，我们将两个下界中的最大值作为下界，将两个上界中的最小值作为新的上界。
数据：
val a = List (Interval (0, 4), Interval (7, 12))
val b = List (Interval (1, 3), Interval (5, 8), Interval (9, 11))
幼稚的方法：气泡重叠（首先使其工作，然后使其快速）：
scala> a.map (aa => b.map (bb => aa.overlap (bb))).flatten.flatten
res21: List[Interval] = List(Interval(1,3), Interval(7,8), Interval(9,11))
如果您不习惯选择/可能与一些（T）和无一起使用，那么有助于理解的核心是：
a.map (aa => b.map (bb => aa.overlap (bb)))
res19: List[List[Option[Interval]]] = List(List(Some(Interval(1,3)), None, None), List(None, Some(Interval(7,8)), Some(Interval(9,11))))
第一次展平将两个内部列表合并为一个列表，第二次展平删除了Nones，并给我们留下了间隔，而不是包装Some（Interval）。
也许我可以想出一个迭代的解决方案，它不需要比它匹配的时间间隔多2倍的时间。。。（10分钟后）。。。这是：
def findOverlaps (l1: List[Interval], l2: List[Interval]): List[Option[Interval]] = (l1, l2) match {
case (_, Nil) => Nil
case (Nil, _) => Nil
case (a :: as, b :: bs) => {
if (a.lower > b.upper) findOverlaps (l1, bs)
else if (a.upper < b.lower) findOverlaps (as, l2)
else if (a.upper > b.upper) a.overlap (b) :: findOverlaps (l1, bs)
else a.overlap (b) :: findOverlaps (as, l2)
}
}
前两行内线检查，如果其中一个列表为空，则不会出现更多重叠。
（a：：as，b：：bs）是（l1，l2）的匹配a是l1的头部，as是l1的尾部（可能为零），模拟b是l2的头部，bs是其尾部。
如果a.lower为
否则我们应该有一个重叠，所以我们在任何一种情况下都取a.overlap（b），上界较高的一个列表的整个列表和另一个列表的尾部。
scala> findOverlaps (a, b)
res0: List[Option[Interval]] = List(Some(Interval(1,3)), Some(Interval(7,8)), Some(Interval(9,11)))
你看，没有生成None，对于findOverlaps（b，a），结果是相同的。
所以你有两个带有事件的列表——进入间隔和离开间隔。合并这些列表，保持当前状态为整数0、1、2（活动间隔计数）
Get the next coordinate from both lists
If it is entering event
Increment state
If state becomes 2, start new output interval
If it is closing event
Decrement state
If state becomes 1, close current output interval
处理关系（当值等于[0...1]和[1...2]时）对应于所选规则-如果此类间隔不应该给出交集，则在打开一个之前处理关闭事件
-
问题内容： 我在尝试实现的算法周围束手无策。我有两个列表，希望从两个列表中进行特定组合。 这是一个例子。 在这种情况下，输出为： 我的名字可能比数字多，即。这是一个具有3个名称和2个数字的示例： 输出： 问题答案： 注意 ：此答案是针对上面提出的特定问题的。如果您来自Google，只是想寻找一种使用Python获得笛卡尔积的方法，或者您可能正在寻找简单的列表理解方法- 请参见其他答案。 假设。然后
-
l和r分别是区间的起点和终点。
-
假设我有一个这样的范围列表 现在我想找到一个范围，比如。我的算法应该给我这个范围的所有范围。例如，这个的输出应该是 <代码>输出-[1,3]、[2,5]、[4,6]、[8,10] 我该如何着手解决这个问题？ PS：我知道段树可能会有所帮助。我可以在其中构建树来存储间隔并查询位于间隔内的Point，但如何在给定间隔的情况下获取所有间隔。
-
问题内容： 我在Python中有两个列表，如下所示： 我需要用第一个列表中的项目创建第二个列表，而第二个列表中没有这些项目。从示例中，我必须得到： 有没有循环和检查的快速方法吗？ 问题答案： 当心 你可能期望/希望它等于的位置。如果你想作为答案，则需要使用
-
问题内容： 我在MySQL中有两个表。在每个表中，保存了具有其MAC地址和状态区域信息的设备。 这些状态确实在某些时间戳记（startTime，endTime）及其持续时间（endTime-startTime）处开始和结束，并且是由某些ID引起的。 现在，我想查找某些事件“移动”和“负载”之间的重叠部分，这些重叠部分以天为单位，如下所示： 查询结果应如下所示： 我在这里准备了一个小提琴：http
-
这与寻找重叠的间隔有关。给定一个间隔列表（间隔树），我知道如何做到这一点。我有一个间隔列表。例如， 结果应该是 [2,3], [7,8] 我需要做的是找到所有列表中常见的间隔列表。 我认为这个问题类似于合并列表。问题是我无法应用列表的成对合并。应用此方法可能会导致丢失重叠间隔。因此，我需要将所有列表合并在一起，一次考虑所有列表（而不是成对）。 我可以使用间隔树。将每个列表中的第一个间隔插入间隔树并