如何在功能上合并列表中的重叠数字范围

Question

我有许多范围对象需要合并,以便所有重叠范围消失:

case class Range(from:Int, to:Int)

val rangelist = List(Range(3, 40), Range(1, 45), Range(2, 50), etc)

这是范围:

  3  40  
  1  45  
  2  50  
 70  75  
 75  90  
 80  85  
100 200

完成后我们会得到:

  1  50  
 70  90  
100 200  

命令式算法:

1. Pop()第一个范围-obj并遍历列表的其余部分,将其与每个其他范围进行比较.
2. 如果存在重叠项,则将它们合并在一起(这会生成一个新的Range实例)并从源列表中删除2个合并候选项.
3. 在列表的末尾,将Range对象(可能已经通过合并多次更改)添加到final-result-list.
4. 使用下一个剩余项目重复此操作.
5. 一旦源列表为空,我们就完成了.

要做到这一点必须要创建大量的临时变量,索引循环等.

所以我想知道是否有更实用的方法？

乍一看,源集合必须能够像Stack一样提供pop()PLUS,能够在迭代时通过索引删除项目,但之后就不再那么具有功能了.

Answer 1

我喜欢这些谜题:

case class Range(from:Int, to:Int) {
  assert(from <= to)

  /** Returns true if given Range is completely contained in this range */
  def contains(rhs: Range) = from <= rhs.from && rhs.to <= to

  /** Returns true if given value is contained in this range */
  def contains(v: Int) = from <= v && v <= to
}

def collapse(rangelist: List[Range]) = 
  // sorting the list puts overlapping ranges adjacent to one another in the list
  // foldLeft runs a function on successive elements. it's a great way to process
  // a list when the results are not a 1:1 mapping.
  rangelist.sortBy(_.from).foldLeft(List.empty[Range]) { (acc, r) =>
    acc match {
      case head :: tail if head.contains(r) =>
        // r completely contained; drop it
        head :: tail
      case head :: tail if head.contains(r.from) =>
        // partial overlap; expand head to include both head and r
        Range(head.from, r.to) :: tail
      case _ =>
        // no overlap; prepend r to list
        r :: acc
    }
  }

Answer 2

尝试尾递归.(只有在没有发生尾递归优化的情况下才需要注释;如果可以注释,编译器将执行此操作.)

import annotation.{tailrec => tco}
@tco final def collapse(rs: List[Range], sep: List[Range] = Nil): List[Range] = rs match {
  case x :: y :: rest =>
    if (y.from > x.to) collapse(y :: rest, x :: sep)
    else collapse( Range(x.from, x.to max y.to) :: rest, sep)
  case _ =>
    (rs ::: sep).reverse
}
def merge(rs: List[Range]): List[Range] = collapse(rs.sortBy(_.from))