3

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

在A中，区间按其起点排序。A没有重叠的区间。

同样，在 中B，区间按其起点排序。B没有重叠的区间。

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

例子：

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

返回：

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

我在一次采访中得到了这个，被难住了。

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

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

4

3 回答 3

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] 时） - 如果此类间隔不应给出交集，则在打开事件之前处理关闭事件

于 2018-03-31T01:50:42.647 回答
1

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

如果一个区间的上限低于另一个区间的下限，则不可能有重叠，因此我们返回 None。

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

数据：

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

第一个 flatten 将两个内部 List 组合成一个 List，第二个 flatten 删除了 None 并给我们留下了 Intervals，而不是包装器 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.上。

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

于 2018-03-31T02:16:41.023 回答
1

这是我用作 apache-spark 程序中复杂化简步骤的组件的算法的实现：链接到另一个相关答案。奇怪的是，它也在 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条件和min- -max函数，要么必须使用 de-Morgan 定律进行预处理/后处理。原理还是一样的，但我绝对不想在交叉路口重复整个练习。不要将其视为缺点，而应将其视为答案的一个特征：没有剧透；）

于 2018-03-31T02:56:25.727 回答