Define time intervals from the list of time intervals (not covered by the spans in the list)

Question

I have a list of time slots (defined as Integer-Tuples), for example:

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

I want to find an elegant Haskell solution for defining time gaps that are not covered by timelines in the list.

Answer 1

First, I sorted the gaps by the time they started. Then you can easily merge overlapping gaps. Once you have this, you can find the gaps just by going over the combined spaces in pairs (by fastening it with the tail). The gap will be the interval from the end time of the first element of the pair to the start time of the second element.

In the code, it will 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 

Using:

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

Answer 2

My solution works with divide-and-conquer to melt all overlapping time slots to get a sorted list of non-overlapping time slots:

 module Test where type Time = Int type Start = Time type Stop = Time type Span = (Start, Stop) timespans :: [Span] timespans = [ (1200, 1210) , (1202, 1209) , (1505, 1900) , (1300, 1500) , (1400, 1430) , (500,1200) , (20,100) ] flattentime :: [Span] -> [Span] flattentime [] = [] flattentime [x] = [x] flattentime (s:ss) = combine (flattentime [ times | times <- ss, (fst times) < (fst s) ]) s (flattentime [ times | times <- ss, (fst times) >= (fst s) ]) combine [] s [] = [s] combine [] s ss2 = melt s (head ss2) ++ tail ss2 combine ss1 s [] = firsts ss1 ++ melt (last ss1) s combine ss1 s ss2 = (firsts ss1) ++ melt3 (last ss1) s (head ss2) ++ (tail ss2) melt (x1,x2) (x3,x4) | x2 < x3 = [(x1,x2), (x3,x4)] | x4 < x2 = [(x1,x2)] | otherwise = [(x1,x4)] melt3 (x1,x2) (x3,x4) (x5,x6) = if (length ss >1) then (head ss):(melt y (x5,x6)) else melt y (x5,x6) where ss = melt (x1,x2) (x3,x4) y = last ss firsts [x] = [] firsts [] = [] firsts (x:xs) = x:(firsts xs) 

Not so clean and elegant I would like it to be ... who has a shorter solution?

Answer 3

Elegant - do you mean something like?

 import Data.List timespans = [ (1200, 1210) , (1202, 1209) , (1505, 1900) , (1300, 1500) , (1400, 1430) ] gaps xs0 = filter g $ zipWith f xs (tail xs) where xs = merge $ sort xs0 f (_, t0) (t1, _) = (t0, t1) g (t0, t1) = t0 < t1 merge [] = [] merge ((t0, t1):(t2, t3):ys) | t2 < t1 = merge ((t0, max t1 t3) : ys) merge (y:ys) = y : merge ys main = print (gaps timespans) 

Answer 4

Thanks sepp2k - your right; it is much easier than you suggest! In the Haskell working code:

 flattentime :: [(Integer,Integer)] -> [(Integer,Integer)] flattentime [] = [] flattentime [x] = [x] flattentime ((x1,x2):(y1,y2):ts) | y2<x2 = (x1,x2):(flattentime ts) | y1<x2 = (x1,y2):(flattentime ts) | otherwise = (x1,x2) : (flattentime ((y1,y2):ts)) 

Then I need to call simply:

 > (flattentime.sort) timespans