merge_intervals.hs

import qualified Data.List as L

l1 = [(1, 3), (2, 4), (5, 7), (6, 8), (10, 15)]
l2 = [(6, 8), (1, 9), (2, 4), (4, 7)]

sort' :: Ord b => [(b, b1)] -> [(b, b1)]
sort' = L.sortOn fst

mergeIntervals [] = []
mergeIntervals ((s, e):xs) = fn ((s,e):[]) $ xs
    where
        fn stack [] = stack
        fn stack@((ss,se):st) ((ns,ne):ys) = if (ns > se)
                                                  then fn ((ns, ne):stack) ys
                                                  else fn ((ss, max se ne):st) ys

main :: IO ()
main = do
    putStrLn ("mergeIntervals " ++ show l1 ++ " = " ++ show (mergeIntervals $ sort' l1))
    putStrLn ("mergeIntervals " ++ show l2 ++ " = " ++ show (mergeIntervals $ sort' l2))