3

给定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]
4

3 回答 3

2

所以你有两个带有事件的排序列表 - 进入间隔和离开间隔。

合并这些列表，将当前状态保持为整数 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

请注意，此算法类似于在那里找到交叉点

于 2018-03-31T03:12:16.380 回答
1

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

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

如果两个列表都是空的 - 返回空列表。如果只有一个为空，则返回另一个。如果一个列表的上限低于另一个列表的下限，则无法统一，因此返回另一个并继续其余的。如果它们重叠，则不返回，而是递归调用该方法，统一在更远的间隔一侧，而没有消耗的不太远的间隔。

union 方法看起来类似于进行重叠的方法：

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

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

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

于 2018-03-31T05:26:34.497 回答
1

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

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

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

让我们定义一个类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，如果元素来自 sofar 收集的元素，比上一个大 1，我们将该元素收集到这个 sofar 列表中。否则，我们将 sofar 收集的列表作为部分结果返回，然后将其余部分与仅包含当前元素的 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))
于 2018-03-31T03:50:10.580 回答