合并两个排序的间隔列表

Question

给定A和B，这是两个区间列表。 A 在 A 内没有重叠，B 在 B 内没有重叠。在 A 中，间隔按其起点排序。在 B 中，区间按起点排序。如何合并两个区间列表并输出不重叠的结果？

一种方法是连接两个列表，按起点排序，并应用 https://www.geeksforgeeks.org/merging-intervals/ 中讨论的合并间隔。有没有更有效的方法？

这是一个例子：

A: [1,5], [10,14], [16,18]
B: [2,6], [8,10], [11,20]

输出：

[1,6], [8, 20]

Answer 1

因此您有两个包含事件的排序列表 - 进入间隔和离开间隔。

合并这些列表，将当前状态保持为整数 0、1、2（活动间隔计数）

Get the next coordinate from both lists 
If it is entering event
   Increment state
   If state becomes 1, start new output interval 
If it is closing event
   Decrement state
   If state becomes 0, close current output interval

请注意，此算法类似于求交集

Answer 2

一个简单的解决方案可能是，压缩所有元素，将它们放入一个集合中，对其进行排序，然后迭代以将形容词元素转换为区间。

可以为您的其他问题选择类似的方法，只需消除所有不同的值以获得重叠。

但是 - 这种方法存在问题。

让我们定义一个 class 区间：

case class Interval (lower: Int, upper: Int) {    
    def deflate () : List [Int] = {(lower to upper).toList}
}

并使用它：

val e = List (Interval (0, 4), Interval (7, 12))
val f = List (Interval (1, 3), Interval (6, 8), Interval (9, 11))

放气：

e.map (_.deflate)
// res26: List[List[Int]] = List(List(0, 1, 2, 3, 4), List(7, 8, 9, 10, 11, 12))    
f.map (_.deflate)
// res27: List[List[Int]] = List(List(1, 2, 3), List(6, 7, 8), List(9, 10, 11))

::: 组合了两个列表，这里是两个列表的列表，这就是为什么我们必须将结果展平，以形成一个大列表：

(res26 ::: res27).flatten
// res28: List[Int] = List(0, 1, 2, 3, 4, 7, 8, 9, 10, 11, 12, 1, 2, 3, 6, 7, 8, 9, 10, 11)

对于不同的，我们删除重复项：

(res26 ::: res27).flatten.distinct
// res29: List[Int] = List(0, 1, 2, 3, 4, 7, 8, 9, 10, 11, 12, 6)

然后我们对其进行排序：

(res26 ::: res27).flatten.distinct.sorted
// res30: List[Int] = List(0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12)

一站式命令链：

val united = ((e.map (_.deflate) ::: f.map (_.deflate)).flatten.distinct).sorted
// united: List[Int] = List(0, 1, 2, 3, 4, 6, 7, 8, 9, 10, 11, 12)
//                                        ^ (Gap)

现在我们必须找到 4 和 6 以及 return 两个不同列表之间的差距。我们递归地遍历输入列表 l，如果元素来自 sofar 收集的元素比最后一个大 1，我们将该元素收集到这个 sofar-list 中。否则，我们 return 将 sofar 收集的列表作为部分结果，然后将其余部分拆分为仅包含当前元素的列表作为新的 sofar-collection。一开始，sofar 是空的，所以我们可以从将第一个元素添加到该列表并用它拆分尾部开始。

def split (l: List [Int], sofar: List[Int]): List[List[Int]] = l match {
  case Nil    => List (sofar)
  case h :: t => if (sofar.isEmpty) split (t, List (h)) else 
    if (h == sofar.head + 1) split (t, h :: sofar) 
    else sofar :: split (t, List (h))
}

// Nil is the empty list, we hand in for initialization
split (united, Nil) 
// List(List(4, 3, 2, 1, 0), List(12, 11, 10, 9, 8, 7, 6))

将列表转换为间隔将是一项微不足道的任务 - 获取第一个和最后一个元素，瞧！

但这种方法存在问题。也许您意识到，我重新定义了您的 A: 和 B:（来自前一个问题）。在 B 中，我将第二个元素从 5-8 重新定义为 6-8。因为否则，它会与 A 中的 0-4 合并，因为 4 和 5 是直接邻居，那么为什么不将它们合并为一个大区间呢？

但也许它应该以这种方式工作？对于以上数据：

split (united, Nil) 
// List(List(6, 5, 4, 3, 2, 1), List(20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8))

Answer 3

这是一种不同的方法，本着对重叠问题的回答的精神。

<!--code lang=scala--> 
def findUnite (l1: List[Interval], l2: List[Interval]): List[Interval] = (l1, l2) match {
    case (Nil, Nil) => Nil
    case (as, Nil)  => as
    case (Nil, bs)  => bs
    case (a :: as, b :: bs) => {
             if (a.lower > b.upper) b :: findUnite (l1, bs)
        else if (a.upper < b.lower) a :: findUnite (as, l2)
        else if (a.upper > b.upper) findUnite (a.union (b).get :: as, bs)
        else                        findUnite (as, a.union (b).get :: bs)
    }
}

如果两个列表都是空的 - return 空列表。如果只有一个为空，return 另一个。如果一个列表的上限低于另一个列表的下限，则不可能统一，因此 return 另一个并继续其余的。如果它们重叠，则不要return，而是递归地调用该方法，统一在更远距离的一侧，而不消耗更远的距离。

并集方法看起来与重叠的方法相似：

<!--code scala--> 
case class Interval (lower: Int, upper: Int) {
    // from former question, to compare
    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)))
    }

    def union (other: Interval) : Option [Interval] = {
        if (lower > other.upper || upper < other.lower) None else
        Some (Interval (Math.min (lower, other.lower), Math.max (upper, other.upper)))
    }    
}

不重叠的测试是一样的。但是 min 和 max 换了地方。

所以对于 (2, 4) (3, 5) 重叠是 (3, 4), 联合是 (2, 5).

lower   upper
_____________
    2    4 
    3    5 
_____________
min 2    4 
max 3    5

Table min/max lower/upper。

<!--code lang='scala'--> 
val e = List (Interval (0, 4), Interval (7, 12))
val f = List (Interval (1, 3), Interval (6, 8), Interval (9, 11))
findUnite (e, f)
// res3: List[Interval] = List(Interval(0,4), Interval(6,12))

现在对于上面的棘手或不清楚的案例：

val e = List (Interval (0, 4), Interval (7, 12))
val f = List (Interval (1, 3), Interval (5, 8), Interval (9, 11))
findUnite (e, f)
// res6: List[Interval] = List(Interval(0,4), Interval(5,12))

0-4 和 5-8 不重叠，因此它们形成两个不同的结果，不会合并。

合并两个排序的间隔列表

Merge two sorted lists of intervals

algorithm

intervals

overlap

interval-tree