在已排序的不连续区间列表中插入一个区间

Question

我有一个排序的不连续区间列表和一个区间，例如， [（1,5），（10,15），（20,25）]和​​（12,27）。所以，（12,27）是间隔 我想将它们合并为一个排序的不连续区间列表：[（1,5），（10,27）]。

Answer 1

伪：

list = ... 
u = (12,27) 
i = 0 
newlist = [] 

while (max(list[i]) < min(u)) //add all intervals before intersection 
    newlist.add(list[i++]) 
mini = i 

while (min(list[i]) < max(u)) // skip all intersecting intervals 
    i++ 
maxi = i 

newlist.add((min(list[mini],u),max(list[maxi],u)) // add the new interval 

while (i < list.length) // add remaining intervals 
    newlist.add(list[i++]) 

return newlist 

Answer 2

您可以用图形您的问题模式，其实你的间隔为节点，它们相互连接，如果他们有共同部分（例如，（12,27）连接到（现在首先应该找到连接的组件，然后在每个连接组件中找到最小值开始（例如10）和最大值结束（例如25）。很高兴看到Interval Graphs。

Answer 3

这是我的非惯用斯卡拉解决方案充满变数。该解决方案看起来比它应该是更长的时间，因为我有穷人的实施append和插入列表只支持prepend操作。

的ALGO如下：

1. 扫描到间隔列表分为两个列表那些不使用新的时间间隔和那些做重叠。非重叠间隔是在新间隔之后或完全在新间隔之前开始的间隔。另外，如果我们要插入一个新的时间间隔，它会在最低的时间间隔之后。在这个阶段，我们有一个重叠间隔列表和一个非重叠列表。
2. 如果没有重叠，则新的间隔要么早于所有给定的间隔，要么在所有的间隔之后，或者在两个间隔之间（仍然没有重叠）。
3. 如果存在重叠，则将重叠区间与新区间合并。重叠区间的开始是min（新区间的开始，最小重叠区间的开始）。我们可以类似地计算结束。现在将重叠间隔插入之前计算的位置。

下面是代码：

object trial { 
    val intervals1 = List((1, 2), (4, 6), (7, 8), (16, 17))) 
    val intervals2 = List((1, 5), (10, 15), (20, 25) 

    val newInterval1 = (11, 12) 
    val newInterval2 = (12, 27) 

    // Interval algo test. 
    val result1 = Merge(intervals1, newInterval1) // result1 : List((1,2), (4,6), (7,8), (11,12), (16,17)) 
    val result2 = Merge(intervals2, newInterval2) // result2 : List[(Int, Int)] = List((1,5), (10,27)) 
    } 

object Merge{ 
    def append[T](list: List[T], el: T): List[T] = { 
    (el :: list.reverse).reverse 
    } 
    def insert[T](list: List[T], pos: Int, elem: T): List[T] = { 
    var newList = List.empty[T] 
    val reversePos = list.length - pos 
    list.reverse.zipWithIndex foreach { 
     case(el, i) if i == reversePos => { 
     newList = elem :: newList 
     newList = el :: newList 
     } 
     case (el, i) => newList = el :: newList 
    } 
    newList 
    } 

    def apply(list: List[(Int, Int)], interval: (Int, Int)): List[(Int, Int)] = { 
    val (min, max) = interval 
    var newList = List.empty[(Int, Int)] 
    // Store potentially overlapping stuff. 
    var overlap = List.empty[(Int, Int)] 
    // Maintain the position to begin merge. 
    var posInsert = 0 
    list.zipWithIndex foreach { case(intervalz, i) => 
     if (intervalz._2 < min) { 
     // Does not overlap but an insert will be after the highest of these. 
     posInsert = i 
     newList = append(newList, intervalz) 
     } else if (intervalz._1 > max) { 
     // Does not overlap. 
     newList = append(newList, intervalz) 
     } else overlap = append(overlap, intervalz) 
    } 
    if (overlap isEmpty) { 
     if (posInsert == 0) newList = interval :: newList 
     else newList = insert(newList, posInsert + 1, interval) 
    } else { 
     // Start of new interval is the lower of the first overlap's start or the interval's start. 
     val startOfInterval = Math.min(overlap.head._1, min) 
     // Enf of interval is higher of last overlap's end or interval's end. 
     val endOfInterval = Math.max(overlap.head._2, max) 
     // Insert the merged interval after the highest interval smaller than the start of the new internval. 
     if (posInsert == 0) newList = (startOfInterval, endOfInterval) :: newList 
     else newList = insert(newList, posInsert + 1, (startOfInterval, endOfInterval)) 
    } 
    newList 
    } 
} 

它通过这里提到的测试和为O（N）。

编辑。它的算法版本：

intervals = [....] 
newInterval = (12, 27) 
newList = [] 
overlappingList = [] 
posInsert = 0 
i = 0 

while (i < intervals.size) 
    if (intervals[i].max < newInterval.min) 
    posInsert = i 
    append(newList, intervals[i]) 
    else if (intervals[i].min > newInterval.max) 
    append(newList, intervals[i]) 
    else 
    append(overlappingList, intervals[i]) 
    i++ 

if (overlap isEmpty) 
    if (posInsert == 0) prepend(newList, newInterval) 
    else insert(newList, posInsert + 1, newInterval) 
else 
    start = Min(overlappingList[i].min, newInterval.min) 
    end = Max(overlappingList[i].max, newInterval.max) 
    if (posInsert == 0) prepend(newList, newInterval) 
    else insert(newList, posInsert + 1, new Interval(start, end)) 
return newList