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

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  

命令式算法:

Pop() 第一个 range-obj 并遍历列表的其余部分，将其与其他每个范围进行比较。

如果有重叠的项目，
将它们合并在一起(这会产生一个新的 Range 实例)并从源列表中删除 2 个合并候选者。

在列表的末尾，将 Range 对象(通过合并可能已更改多次)添加到最终结果列表。

对剩余的下一个项目重复此操作。

一旦源列表为空，我们就完成了。

要强制执行此操作，必须创建大量临时变量、索引循环等。

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

乍一看，源集合必须能够像堆栈一样提供 pop() PLUS
提供在迭代时按索引删除项目的能力，但那样就不再那么实用了。

Answer 1

尝试尾递归。 (如果尾递归优化没有发生，则只需要注释来警告您；无论您是否注释，编译器都会这样做。)

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