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.

Endres

amazon.com/Introduction-Algorithms-Thomas-H-Cormen/dp/… contains a solution with explanation for this (well, it depends on what you are optimizing for, you didn't specify that..). should be very easy to implement in FP – Doan

Any chance you could put me int he right direction as to which algorithm, data structure or approach you are refering to? – Endres

I think it's at the beginning in the greedy algorithms section (though I'm not sure). you have to sort the list first. – Doan

You can see my answer in this link: https://mcmap.net/q/73151/-algorithm-to-detect-overlapping-periods-duplicate – Sikorski

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:

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

Pinko

Works a treat and very simple to implement. Thanks, I don't think I was heading in the right direction! – Endres

This algorithm worked great for a different problem I had of counting resource allotment in a reservation system. The goal was to start with a fixed number of some resource and determine if somebody could check out or reserve a subset of the total given others have previously done the same. – Ozone

Works a treat and very simple to implement. – Tunicle

Answer 2

n.m.'s answer is all you will need but if you want to use the code you've already made then simply sort the ranges by the start time and walk through the list merging overlaps.

Joint