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

Question

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

Date/time 范围如下：

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

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

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

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

algorithm

datetime

date-range

go

dateinterval