scala - 在具有开始和结束时间的元组列表中查找空区间的功能方法

Question

假设我有一个包含开始时间和结束时间的元组列表:

List((1,10), (2,11), (3,11), (13,14))

唯一的放松是开始时间正在上升

我期望以下输出:

List((0,1), (11,13))

程序实现相当简单，但是我不知道如何(惯用地)功能性地执行此操作。

scala-for-yield 循环似乎不太合适，因为结果与输入的大小相同。而减少/折叠会限制我只有一个元组作为答案。

Answer 1

考虑以下解决方案:

list
  .foldLeft((List[(Int,Int)](), 0)) {
     case ((res, se), (s, e)) => 
       if(s>se) ((se, s)::res,e) 
       else (res, e)
  }
  ._1
  .reverse

解释。我们累积一对值:空间隔列表(最初为空，List(Int, Int))和最后一个间隔的结束(最初为 0)。在每个步骤中，取当前间隔 (s, e) 并将其与上一个间隔的结束时间进行比较。如果当前间隔的开始大于最后的结束，则存在间隙，我们将其视为结果: (se, s)::res