haskell - 从时间跨度列表中确定时间间隔(列表中的跨度未涵盖)

Question

我有一个时间跨度列表(以整数元组形式给出)，例如:

timespans = [ (1200, 1210)
        , (1202, 1209)
        , (1505, 1900)
        , (1300, 1500)
        , (1400, 1430)
        ]   

我想找到一个优雅的 Haskell 解决方案来确定列表中的时间跨度未涵盖的时间间隔。

Answer 1

首先，我会按开始时间对跨度进行排序。然后你可以很容易地合并重叠的跨度。一旦你有了它，你就可以通过成对迭代合并的跨度(通过用尾部压缩它)来找到间隙。间隔将是从对中第一个项目的结束时间到第二个项目的开始时间的跨度。

在代码中，这看起来像这样:

mergeSortedSpans [] = []
mergeSortedSpans ((from1, to1):(from2, to2):spans) | to1 >= from2 =
   mergeSortedSpans $ (from1, max to1 to2):spans
mergeSortedSpans (span:spans) = span : mergeSortedSpans spans

inPairs _ [] = []
inPairs f (x:xs) = zipWith f (x:xs) xs

gap (_, to1) (from2, _) = (to1, from2)

gaps = inPairs gap . mergeSortedSpans . sort

用法:

gaps timespans
-- [(100,500),(1210,1300),(1500,1505)]