How can I merge multiple overlapping date ranges and create new ones?

Question

I have multiple date ranges each with a start and end date/time, containing a single value from which I want to create new ranges, where the overlapping range values are appended to a slice.

Date/time Ranges are the following:

1. [10:00, 10:15] = 7
2. [10:10, 10:20] = 9
3. [10:05, 10:25] = 2
4. [11:00, now] = 3

To illustrate it better please see the following image (I used only times here, to simplify it):

On the image a date range [10:00, 10:15] contains the value 7, [10:10, 10:20] = 9 and so on.

I would need to generate the following date ranges, where overlapping range values gets merged together:

1. [10:00, 10:05] = 7
2. [10:05, 10:10] = 7,2
3. [10:10, 10:15] = 7,2,9
4. [10:15, 10:20] = 2,9
5. [10:20, 10:25] = 2
6. [10:25, 11:00] = 2 <-- this was a gap, no overlap and not continuous.
7. [11:00, now] = 3

I used a struct to represent a range

type Range struct {
     Start  time.Time
     End    time.Time
     Values []int
}

Is there an easy and efficient way of doing this?

Answer 1

Here's a sketch of an algorithm to do this:

The data struct would be:

type Boundary struct {
   Time time.Time
   AddRemove int
   Value int
}

A Boundary would represent a Value added or removed from the list of values at a given time. For a range:

[from,to]=number

you create two Boundary objects:

b1:=Boundary{Time:from,AddRemove: 1, Value: number}
b2:=Boundary{Time:to,AddRemove:-1,Value:number}

You can then sort all boundary objects by time and AddRemove. If times are equal, you should process adds first, then removes. Once this is done, you can process the boundary objects, and create your ranges:

last:=time.Time{}
values:=map[int]struct{}{}
for _,b:=range boundaries {
   if last.IsZero() {
      last=b.Time
      values[b.Value]=struct{}{}
   } else {
      // Create a new range here with [last,b.Time] with values given in `values`
      if b.AddRemove==1 {
        values[b.Value]=struct{}{}
      } else {
        delete(values,b.Value)
      }
      last=b.Time
   }
}