给定两个排序的区间列表，return 两个列表之间的重叠区间

Question

给你两个间隔列表，A 和 B。

在A中，间隔按起点排序。 None 个间隔 A 重叠。

同样，在 B 中，间隔按其起点排序。 B 内的 None 个间隔重叠。

Return 两个列表之间重叠的间隔。

示例：

A: {[0,4], [7,12]}
B: {[1,3], [5,8], [9,11]}

Return:

{[1,3], [7,8], [9,11]}

我在面试中得到了这个并且被难住了。

我想到了比较两个列表之间的间隔。如果两者之间存在重叠，则将重叠添加到结果列表中。然后我以较小的起始间隔推进列表的指针，但在采访结束时无法找到可行的解决方案。

解决这个问题的最佳方法是什么？

Answer 1

因此您有两个包含事件的列表 - 进入间隔和离开间隔。合并这些列表，将当前状态保持为整数 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] 时）- 如果此类间隔不应给出交集，则在打开事件之前处理关闭事件

Answer 2

下面是一个实现，遵循罗马原则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 是一个 class，第一行可以理解为构造函数。 lower 和 upper 应该是自我解释的（Int 类型）。 class 有一个方法重叠，它采用 class （其他）和 return 的第二个实例，结果是重叠的新间隔。但是包装成一个Option，意思是：如果没有发现重叠，我们returnNone。如果我们找到一个，那就是 Some (Interval)。您可以帮助自己将此构造理解为一个列表，它要么是空的，要么只包含一个元素。这是一种避免 NullpointerException 的技术，通过发出可能没有结果的信号，使用 Type。

如果一个区间的上限低于另一个区间的下限，则不能重叠，所以我们returnNone。

对于重叠，我们取两个下限中的最大值作为下限，取两个上限中的最小值作为新的上限。

数据：

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

核心，如果你不习惯Option/Maybe与Some(T)和None，可能有助于理解，是：

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 的头部，作为 l1 的尾部（可能是 Nil），模拟 b 是 l2 的头部, bs 它的尾巴。

如果 a.lower > b.upper，我们取 b 列表的尾部并递归地重复整个 l1-list 和类似的，整个 l2-List 但只有尾部l1 列表，如果 b.lower > a.upper.

否则我们应该有一个重叠，所以我们在任何一种情况下都采用 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)也是一样的结果。

Answer 3

这是我在 apache-spark 程序中用作复杂 reduce-step 组件的算法的实现：link to another related answer。奇怪的是，它也在 Scala 中。

这里是孤立的算法：

  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
}

它的工作原理与合并排序的 merge 步骤非常相似，但您必须查看整个间隔，而不是查看单个数字。原理还是一样，只是case-distinctions变得很讨厌。

编辑：不完全是这样。你想要交集，这里的算法产生并集。您要么必须翻转很多 if-else-条件和 min-max-函数，要么您必须使用 de-Morgan 法律。原理仍然相同，但我绝对不想在十字路口重复整个练习。不要将其视为缺点，而是将其视为答案的特点：请勿剧透;)

给定两个排序的区间列表，return 两个列表之间的重叠区间

Given two sorted lists of intervals, return the overlapping intervals between the two lists

algorithm

interval-tree

overlap

intervals