泛函的方式找到空的间隔在开始和结束时间的元组的列表

说我有一个开始和结束时间的元组的列表：泛函的方式找到空的间隔在开始和结束时间的元组的列表

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

唯一的放松是启动时间提升

我期待以下的输出：

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

的程序执行是相当简单的，但我不会有一个线索，要做到这一点（惯用）功能。

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

来源

2016-05-31 hbogert

你只使用整数？或者至少有一组离散的值？ – meucaa

在实际的问题是，他们是unix时间戳。 – hbogert

你正在寻找一个库或算法的描述？这可能是相关的：https：//github.com/rklaehn/intervalset –

考虑以下解决方案：

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

来源

2016-05-31 15:33:11 Nyavro

我低估了折叠的可能性。这很漂亮，虽然类似于我的程序解决方案，所以也许我并没有离开太远。 – hbogert

可以使用scanLeft的组合过滤器和地图

list.scanLeft((0,0,0))((l,r) => 
    if(r._1 > l._3) {(l._2, r._1, r._2)} 
    else {(l._1,r._2, r._2)}) 
filter(x => x._2 != x._3) 
map(x => (x._1, x._2))

在扫描过程中，我们查看扫描对的右侧元素（即作业），以查看它是否大于目前的结束时间（由（0,0,0）三元组开始）。如果是这样，我们输出包含三重，从而，

的差距
的差距
截至差距作业的停止时间结束时开始。

如果右手的即作业的开始时间不大于左手的结束时间，那么就没有空白的差距，我们创建一个三元组来扩大当前的工作条件（缺少一个更好的词），由

副本任务连胜的开始时间
复制最后一个任务的结束时间
一样2.

我们现在可以识别通过查看三元组的第二和第三元素不同（验证这是一个iff关系）。我们现在过滤这个事实。最后我们映射，所以我们得到适当的输出形式。

来源

2016-06-04 13:35:31 hbogert

泛函的方式找到空的间隔在开始和结束时间的元组的列表

回答

相关问题