Как я могу объединить несколько перекрывающихся диапазонов дат и создавать новые?

Question

У меня есть несколько диапазонов дат, каждый с начальной и конечной датой / временем, содержащим одно значение, из которого я хочу создать новые диапазоны, где перекрывающиеся значения диапазонов добавляются к срезу.

Дата / Диапазоны времени следующие:

1. [10:00, 10:15] = 7
2. [10:10, 10:20] = 9
3. [ 10:05, 10:25] = 2
4. [11:00, сейчас] = 3

Чтобы проиллюстрировать это лучше, пожалуйста, смотрите следующее изображение (я использовал здесь только раз, для упрощения):

На изображении диапазон дат [10:00, 10:15] содержит значение 7, [10:10 , 10:20] = 9 и т. Д.

Мне нужно сгенерировать следующие диапазоны дат, где перекрывающиеся значения диапазонов объединяются вместе:

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 <- - это был зазор, не перекрывающийся и не непрерывный. </li>
7. [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
   }
}

Answer 2

Создание структуры для общего TimeEvent (Start / End)

type TimeEvent struct {
     EventTime time.Time
     IsStart bool // check start event or end
     Value int // set for both event.

}

Создание фрагмента TimeEvent, используя все время начала и окончания и значение

Затем сортируйте их по EventTime и IsStart и итерация TimeEvent

1. Если Start, добавьте в список

2. Если End, затем удалите из списка и сохраните список