泛函的方式找到空的間隔在開始和結束時間的元組的列表

說我有一個開始和結束時間的元組的列表：泛函的方式找到空的間隔在開始和結束時間的元組的列表

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

泛函的方式找到空的間隔在開始和結束時間的元組的列表

回答

相關問題