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

Question

我有多个日期范围，每个日期范围都有一个开始和结束日期/时间，包含一个我想从中创建新范围的值，其中重叠的范围值被附加到一个切片中。日期/时间范围如下：[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

}

ABoundary将表示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

   }

}