algorithm - Problem calculating overlapping date ranges

Question

I have a problem trying to work out the correct algorithm to calculate a set of date ranges.

Basically I have a list of unordered date ranges (List containing arrays of start and end times) and I want to consolidate this list so it does not contains overlapping times.

Basically to consolidate two date ranges:

if start1 <= end2 and start2 <= end1 //Indicates overlap
   if start2 < start1 //put the smallest time in start1
      start1 = start2
   endif
   if end2 > end1 //put the highest time in end1
      end1 = end2
   endif
endif

This joins the two date times.

I hit a stumbling block when it comes to iterating through all the values so the end list only contains values which are not overlapping.

My functional and recursive programming is a bit rusty and any help would be welcome.

Answer 1

Do not look at the intervals, look only at their ends.

You have a bunch of starting moments and a bunch of ending moments. Imagine that starting moments are red and ending moments are blue. Or imagine that starting moments are opening braces and ending moments are closing braces.

Put them all together in a list. Sort the list from earliest to latest, ignoring the colour.

Now take a counter set to zero with you, and walk down the list. When you see a red moment, increment the counter. When you see a blue moment, decrement the counter. When the counter value goes from 0 to 1, output "start" and the current time. When the counter value goes from 1 to 0, output "end" and the current time. If the counter value drops below 0, output "Houston, we have a problem". You should end with your counter at 0 and a bunch of nice non-overlapping intervals.

This is the good old brace counting algorithm.

Illustration.

 A bunch of overlapping intervals:

 (-------------------) 
                       (----------------------)           
                                                          (---)
       (---------------------)                       
                                                     (-----------------)

 A bunch of interval ends:

 (-----(-------------)-(-----)----------------)      (----(---)--------)