Пример кода (с тестами)это здесь
нужно
В сценарии с диаграммой Ганта мы часто сталкиваемся с такой ситуацией, пять сотрудников A, B, C, D, E, возможно, их работа параллельна, нам нужно рассчитать Общее количество часов, отработанных за определенный период времени.
Мы не можем просто сложить рабочие часы всех пяти человек, потому что будет некоторое совпадение. Итак, на данный момент нам нужен инструмент для вычисления пересечения и объединения времени.
идеи
Отсортируйте набор дискретных периодов времени по времени начала, от меньшего к большему. так
[{2 7} {4 11} {10 19} {10 30} {16 18} {19 29} {23 35} {24 42} {25 30} {27 49}]
Я заменю время очень маленькими секундами, чтобы облегчить понимание.
Зациклить отсортированный массив, если время начала следующего периода времени находится между временем начала и временем окончания предыдущего периода времени, затем продолжите合并, иначе分离.
Вы можете видеть, что у нас есть два ключевых действия здесь,合并,分离, и это основной код, который мы хотим реализовать.
выполнить
Непрерывное рабочее время будет иметь две точки,开始时间а также结束时间.
Таким образом, мы можем спроектировать эту временную структуру как:
type T struct {
Start int64
End int64
}
А рабочее время человека состоит из нескольких T, поэтому мы определяем тип среза
type TSlice []T
Чтобы объединить времена последовательно, нам нужно объединитьTSliceприводить в порядок.
Мы знаем, что в Go есть пакет сортировки, и нам нужно только реализовать интерфейс типа сортировки для реализации сортировки TSlice.
Мы реализуем следующее:
func (t TSlice) Len() int { return len(t) }
func (t TSlice) Swap(i, j int) { t[i], t[j] = t[j], t[i] }
func (t TSlice) Less(i, j int) bool { return t[i].Start < t[j].Start }
Три метода: длина, обменная позиция и отношение.
Таким образом, мы можем напрямую использоватьsort.Stable()Стабильная сортировка, отсортированные срезы нашего периода времени.
Ну а далее реализуем метод union, назовем егоUnion:
func (t TSlice) Union() TSlice {
// 新建一个空的时间切片
var s TSlice
// 如果有至少两个是时间段，我们才排序，否则直接返回
if len(t) > 1 {
// @todo 合并逻辑
}
return s
}
Метод Union вернет идентичныйTSliceНарезка времени, которая не что иное, как союз.
Как только количество периодов времени в t больше 1, нам нужно выполнить логику обработки:
if len(t) > 1 {
sort.Stable(t)
s = append(s, t[0])
// @todo 循环比较合并
}
Сначала мы сортируем временные срезы, затем помещаем первый временной период в качестве первого элемента в наш результат TSlice, чтобы мы могли начать циклическое сравнение.
if len(t) > 1 {
sort.Stable(t)
s = append(s, t[0])
for k, v := range t {
// 如果开始时间大于结束时间，那其实是错误数据，但是我们这里正常返回
// 你可以根据自己的需要定制错误处理逻辑
if v.Start > v.End {
return s
}
// 第一组元素我们不做任何操作
if k == 0 {
continue
}
// 当开始时间介于上一个时间段的开始时间和结束时间之间
if v.Start >= s[len(s)-1].Start && v.Start <= s[len(s)-1].End {
// 合并
if v.End > s[len(s)-1].End {
s[len(s)-1].End = v.End
}
// 如果大于上一个时间段的结束时间
} else if v.Start > s[len(s)-1].End {
// 分离
inner := T{Start: v.Start, End: v.End}
s = append(s, inner)
}
}
}
На самом деле картина ясна:
Вы можете видеть, что конечный результат такжеTSliceТипы.
Вышеупомянутое объединение, процесс объединения, а что насчет пересечения?
На самом деле пересечение тоже очень простое.Если пересекаются два периода времени, нам нужно только судить: время начала является наибольшим, а время окончания - наименьшим из двух периодов времени.
func (t TSlice) Intersect() TSlice {
var s TSlice
if len(t) > 1 {
sort.Stable(t)
s = append(s, t[0])
for k, v := range t {
if v.Start > v.End {
return s
}
if k == 0 {
continue
}
// 两个时间段相交
if v.Start >= s[0].Start && v.Start <= s[0].End {
// 开始时间取最大的那个
s[0].Start = v.Start
// 结束时间取最小的那个
if v.End <= s[0].End {
s[0].End = v.End
}
} else {
return s[:0]
}
}
}
return s
}
То же самое, сфотографируем:
Следует отметить, что результатом этого пересечения является полное пересечение - результат будет только тогда, когда все периоды времени будут иметь общее время. Разве такого рода требования не слишком часто используются в реальном процессе? ? Так что думаю можно добиться: одно пересечение, два пересечения... Условная фильтрация.
увидеть эффект
Мы случайным образом сгенерировали набор временных отрезков
func makeTimes(t int) TSlice {
var set TSlice
rand.Seed(time.Now().Unix())
for i := 0; i < t; i++ {
randStart := rand.Int63n(50)
randEnd := randStart + rand.Int63n(25) + 1
set = append(set, T{Start: randStart, End: randEnd})
}
return set
}
testSet := makeTimes(10) // 生成10个时间段的时间切片
res := testSet.Union() // 直接调用 Union() 或者 Intersect()
Входные данные:
[{10 21} {34 52} {49 54} {18 31} {26 44} {24 27} {43 51} {41 53} {20 41} {48 67}]
Выходной результат:
[{10 67}]
Результат в порядке~
дополнительный
Я обнаружил, что в процессе набора объединения потребуется окончательная сумма времени, поэтому мы добавляем метод Sum() в TSlice, Это простое суммирование цикла:
func (t TSlice) Sum() (sum int64) {
for i := 0; i < len(t); i++ {
sum += t[i].End - t[i].Start
}
return sum
}
Метод вызова: TSlice.Union().Sum()