Determine time gaps from list of time-spans (not covered by the spans in the list)

Question

I have a list of time-spans (given as Integer-Tuples), e.g.:

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

I want to find an elegant Haskell solution to determine time gaps which are not covered by the timespans in the list.

Answer 1

First I would sort the spans by their starting time. Then you can merge overlapping spans pretty easily. Once you have that you can find the gaps by just iterating over the merged spans in pairs (by zipping it with its tail). The gap will be the span from the end time of the first item of the pair to the starting time of the second item.

In code this would look like this:

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

Usage:

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