Since you're given a sorted list of intervals, you don't actually need to
restart the whole merging process from the start after each merge; you can just
replace the last interval in your output with the new, merged interval and
continue from there. So `reduce' is the perfect tool for the job; my solution
is below.
I used 2-vectors for ranges since they're easier to type and read. Note that
reduce-intervals builds its result in reverse, since seqs like to be
manipulated from the head.
(defn intervals-intersect? [s1 s2]
(not (or
(> (s1 0) (s2 1))
(> (s2 0) (s1 1)))))
(defn join-intervals [s1 s2]
[(min (s1 0) (s2 0)) (max (s1 1) (s2 1))])
(defn reduce-intervals [reduced s]
(let [[s-prev & more] reduced]
(if (and s-prev (intervals-intersect? s-prev s))
(cons (join-intervals s-prev s) more)
(cons s reduced))))
(defn merge-intervals [intervals]
(reverse
(reduce reduce-intervals []
intervals)))
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
