algorithm - 如何合并多个重叠的日期范围并创建新的日期范围？

Question

我有多个日期范围，每个日期范围都有一个开始日期和结束日期/时间，其中包含一个我想从中创建新范围的值，重叠的范围值会附加到 slice 中。

日期/时间范围如下:

[10:00，10:15] = 7

[10:10，10:20] = 9

[10:05，10:25] = 2

[现在11:00] = 3

为了更好地说明它，请参见下图(为简化起见，我在这里仅使用了几次):



在图像上，日期范围[10:00，10:15]包含值7，[10:10，10:20] = 9，依此类推。

我将需要生成以下日期范围，其中重叠的范围值将合并到一起:

[10:00，10:05] = 7

[10:05，10:10] = 7.2

[10:10，10:15] = 7,2,9

[10:15，10:20] = 2,9

[10:20，10:25] = 2

[10:25，11:00] = 2 <-这是一个缺口，没有重叠且不连续。

[现在11:00] = 3

我用一个结构来代表一个范围

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

有一种简单有效的方法吗？

Answer 1

这是执行此操作的算法示意图:

数据结构为:

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

Boundary表示在给定时间从值列表中添加或删除的Value。对于范围:

[from,to]=number

您创建两个Boundary对象:

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

然后，您可以按时间和AddRemove对所有边界对象进行排序。如果时间相等，则应先处理添加，然后删除。完成此操作后，您可以处理边界对象并创建范围:

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
   }
}