How to calculate "Outersections" from Sets of date range

Question

Consider a list of sets of date ranges:

A: [{2017/01/01, 2017/01/30},{2017/02/15, 2017/03/05},{2017/03/25, 2017/04/30}]

B: [{2017/01/01, 2017/01/30}]

C: [{2017/01/01, 2017/01/20},{2017/02/19, 2017/03/15}]

Is there a efficient way to calculate the "Outersection" intervals (Hatched area, with no intersections between the A,B,C date ranges)?

EDIT: @kaidul-islam, thanks for your answer! I simplified the logic into one for and one if:

...
for (i; i < n - 1; i++) {
    var current := ranges[i];
    var next := ranges[i + 1];

    if (next.left > current.right) {
        gap := next.left - right
        if(gap > 0){
            result.add(gap)
        }
    }
}

i missed something?

PS: ranges is sorted by left and right date.

Answer 1

Sort all the set of ranges (A, B and C together) according to ascending order of left date (range with smaller date at left position will come first).

And then follow this pseudo-code:

result = []
left := range[0].left
right := range[0].right
i := 0
while(i < n):

   while(i + 1 < n && ranges[i + 1].left <= right):
       right := max(ranges[i + 1].right, right)
       i := i + 1
   end

   if(i + 1 < n):
       gap := ranges[i + 1].left - right
       if(gap > 0):
           result.add(gap)
       endif
   endif

end

return result

Time complexity is O(nlogn) for sorting and O(n) for left to right scan where n is the total number of ranges summing up all sets.

Let me know if you need any help.