合并两个已排序的区间列表

Question

给定两个区间列表A和B，其中A中没有重叠的部分，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]

- user9577088

---

这不清楚。 - touch my body

我在你的另一个话题中给了你最有效的线性算法来处理交集。并集可以类比处理。 - MBo

@user unknown 我着急了。不是十分相似 - 这里他想要的是联合，那里 - 交集，但是方法是相同的。 - MBo

你自己做了什么来解决这个问题？ - user unknown

@userunknown 我在第二段解释了我自己尝试解决问题的方法。像[25,26]这样的元素被保留下来。 - user9577088

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 

请注意，这个算法类似于交集查找这里的算法。

- MBo

Answer 2

一个简单的解决方案是，将所有元素压缩，放入一个集合中，进行排序，然后迭代以将相邻元素转换为间隔。

对于您的另一个问题，可以选择类似的方法，只需消除所有不同的值即可获得重叠部分。

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

让我们定义一个Interval类：

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)

使用distinct，我们可以去除重复项：

(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之间的空隙，并返回两个不同的列表。我们通过递归遍历输入列表l，如果元素比上一个大1，那么我们将该元素收集到这个sofar-list中。否则，我们将已收集的list作为部分结果返回，然后用只包含当前元素的List来拆分其余部分作为新的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))

- user unknown

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

如果两个列表都为空，则返回空列表。 如果其中一个为空，则返回另一个。 如果一个列表的上限低于另一个列表的下限，则无法进行合并，因此返回另一个并继续处理其余部分。 如果它们重叠，则不要返回，而是在更远达间隔一侧调用该方法进行递归，并且不包括已使用的较短距离间隔。

联合方法与执行重叠的方法类似：

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

非重叠测试相同，但最小值和最大值交换了位置。

因此对于(2,4)(3,5)，重叠部分为(3,4)，并集为(2,5)。

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

表格最小/最大下限/上限。

<!--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不重叠，因此它们形成两个不会合并的不同结果。

- user unknown