给定两个排序的间隔列表，返回两个列表之间的重叠间隔。

Question

您将得到两个间隔列表，A和B。

在A中，间隔按其起点进行排序。A中的任何间隔都不重叠。

同样，在B中，间隔按其起点进行排序。B中的任何间隔都不重叠。

返回两个列表之间重叠的间隔。

示例：

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

返回：

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

我在一次面试中得到了这个，结果被难住了。

我想比较一下这两个列表之间的间隔。如果两者之间存在重叠，则将重叠添加到结果列表中。然后，我以较小的开始间隔提前了列表的指针，但在面试结束时无法找到有效的解决方案。

解决这个问题的最好办法是什么？

Answer 1

下面是一个实现，遵循罗马原则divide不分皂白：

首先，查找一个方法，该方法在给定的一对间隔内找到重叠(如果有的话)。

/* 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)。类有一个方法重叠，它接受类的第二个实例(其他)，并返回一个新的重叠间隔。但是包装成一个选项，这意味着:如果没有找到重叠，我们就不返回。如果我们找到一个，它是一个(间隔)。您可以帮助自己将这个构造理解为一个列表，它要么是空的，要么就是包含一个元素。这是一种通过发送信号来避免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的匹配物，a是l1的头，l1的尾(可能是Nil)，模拟b是l2的头，b是它的尾。

如果a.lower是> b.upper，则取b列表的尾，递归地重复整个l1 -列表和类似的，对整个L2-列表，但只重复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)))

您看，没有生成任何一个，对于findOverlaps (b，a)，结果是相同的。

Answer 2

因此，您有两个事件列表-输入间隔和离开间隔。合并这些列表，将当前状态保持为整数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 3

下面是一个算法的实现，我用它作为apache火花程序中一个复杂的缩减步骤的组件：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步骤，但是您必须查看整个间隔，而不是查看单个数字。原则保持不变，只有案件-区别变得相当恶劣。

编辑：不是那么回事。你想要交集，这里的算法就会产生联合。您要么需要翻转相当多的if-else-conditions和min-max-functions，要么必须使用de定律进行预处理/后处理。原则仍然是一样的，但我绝对不想重复这整个练习的交叉口。不要把它看作是一个缺点，而是把它当作答案的一个特征:没有破坏者;)