Skip to content

Instantly share code, notes, and snippets.

@samidarko
Created March 13, 2018 08:48
Show Gist options
  • Save samidarko/ce0eef431b39e7790cd8af3f9372ebc1 to your computer and use it in GitHub Desktop.
Save samidarko/ce0eef431b39e7790cd8af3f9372ebc1 to your computer and use it in GitHub Desktop.
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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment