[Программирование, Алгоритмы, Go] Algorithms in Go: Merge Intervals

Ответить на тему

Автор

Сообщение

news_bot ^®

Стаж: 6 лет 9 месяцев
Сообщений: 27286

news_bot ^® написал(а)
25-Янв-2021 13:30

Цитировать

This is the third part of a series covering the implementation of algorithms in Go. In this article, we discuss the Merge Intervals algorithm. Usually, when you start learning algorithms you have to deal with some problems like finding the least common denominator or finding the next Fibonacci number. While these are indeed important problems, it is not something that we solve every day. Actually, in the vast majority of cases, we only solve such kinds of algorithms when we learn how to solve the algorithms. What I like about the Merge Interval algorithm is that we apply it in our everyday life, usually without even noticing that we are solving an algorithmic problem. Let's say that we need to organize a meeting for our team. We have three colleagues Jay, May, and Ray and their time schedule look as follows (a colored line represents an occupied timeslot):

Which timeslot should we pick up for a new meeting? One could look at the picture, find a gap in Ray's schedule, and check whether the others a gap there as well.

How can we implement this logic? Most straightforwardly, we can iterate through every minute of the day and check whether someone is having a meeting during that time. If none of the colleagues are occupied at that time, we find an available minute. How can we simplify this approach? Instead of checking all employees for every minute, we can merge their schedules and find the available slots in the resulting schedule.

After the merge, we can iterate through the array of the merged meetings and find the gaps. How can we implement the algorithm above? Let's create type Slot that represents a time slot in the schedule; for simplicity, we use integers to denote the start and the end of the time slot instead of time.Time type.

type Slot struct {
start int
end int
}

For each of the employees will have a sorted array of Slots (staring from the earliest time slot) that represent occupied time slots in their schedule. Our function will take an array of Slot arrays that represents the schedule for the whole team as an input parameter.

[][]Slot{
{{9, 10}}, // occupied time slots for John
{{1, 3}, {5, 6}}, // occupied time slots for James
{{2, 3}, {6, 8}}, // ...
{{4, 6}
}

Our function will return an array of Slots that represent the commonly available slots for each member of the team. We merge the schedules of two employees by merging their arrays of Slots. How do we do the merge of two arrays? We need to iterate through both arrays and see whether we have overlapping time slots. How can we know that the slots are overlapping? In general, we have two options for overlapping intervals A and B:

If neither of the two above conditions is satisfied, then the intervals do not overlap. We can iterate through both of the arrays and see whether we have an overlap. Let's arr1 and arr2 represent the occupied time slots for two employees. We start with i1 and i2 equal to zero and continue the iteration till we exhaust either of the arrays. At each step, we check whether the current intervals from each of the arrays overlap.

// Merge two array of slots.
func Merge(arr1, arr2 []Slot) []Slot {
out := make([]Slot, 0)
i1, i2 := 0, 0
for i1 < len(arr1) && i2 < len(arr2) {
v1, v2 := arr1[i1], arr2[i2]

If the intervals overlap then we merge them. Let's say interval v1 from arr1 ends earlier than v2 from arr2 In this case, the next interval from arr1 can have an overlap with the merged interval of v1 and v2. Therefore, we merge v1 into v2, i.e. v2.Start = min(v2.Start, v1.Start) and v2.Stop = max(v2.Stop, v1.Stop) and increase i1. i2 stays the same, therefore at the next iteration, we will check whether the next interval from arr1 overlaps with the merged interval.

overlap12 := (v2.Start >= v1.Start) && (v2.Start <= v1.Stop)
overlap21 := (v1.Start >= v2.Start) && (v1.Start <= v2.Stop)
if overlap12 || overlap21 {
merged := Slot{
Start: min(v1.Start, v2.Start),
Stop: max(v1.Stop, v2.Stop),
}
if v1.Stop < v2.Stop {
arr2[i2] = merged
i1++
} else {
arr1[i1] = merged
i2++
}
continue
}

If there is no overlap, we save the interval with the earliest stop (let's say an interval v2 from arr2) to the output array and increase index i2 for arr2. The other interval v1 from arr1 can still have an overlap with the next interval from arr2 so we don't increase i1.

if v1.Stop < v2.Stop {
out = append(out, v1)
i1++
} else {
out = append(out, v2)
i2++
}

When i1 or i2 becomes equal to the length of the corresponding array we stop the iteration. As no more overlaps are possible, we simply add the remaining intervals to the output array. The full listing for the function:

// Merge two arrays of meetings.
func Merge(arr1, arr2 []Slot) []Slot {
out := make([]Slot, 0)
i1, i2 := 0, 0
for i1 < len(arr1) && i2 < len(arr2) {
v1, v2 := arr1[i1], arr2[i2]
overlap12 := (v2.Start >= v1.Start) && (v2.Start <= v1.Stop)
overlap21 := (v1.Start >= v2.Start) && (v1.Start <= v2.Stop)
if overlap12 || overlap21 {
merged := Slot{
Start: min(v1.Start, v2.Start),
Stop: max(v1.Stop, v2.Stop),
}
if v1.Stop < v2.Stop {
arr2[i2] = merged
i1++
} else {
arr1[i1] = merged
i2++
}
continue
}
// no overlap; save the earliest of the intervals
if v1.Stop < v2.Stop {
out = append(out, v1)
i1++
} else {
out = append(out, v2)
i2++
}
}
out = append(out, arr1[i1:]...)
out = append(out, arr2[i2:]...)
return out
}

We merged the schedules of two colleagues. We need to merge all the schedules and then find the gaps within the merged schedule. How do find the gaps? We need to invert a Slot array considering the start and the end of the working day.

// Given an array of occupied time slots,
// returns available time slots in range from 1 to 12.
// We consider that working day starts at 1 and ends at 12.
func inverseSchedule(schedule []Slot) []Slot {
start := 1
var out []Slot
for ind, appointment := range schedule {
if ind == 0 && appointment.Start == 1 {
start = appointment.Stop
continue
}
out = append(out, Slot{Start: start, Stop: appointment.Start})
start = appointment.Stop
}
if start < 12 {
out = append(out, Slot{Start: start, Stop: 12})
}
return out
}

The resulting function looks as follows:

// AvailableSlots for all employees.
// Working hours starts at 1 ends at 12.
func AvailableSlots(schedule [][]Slot) []Slot {
if len(schedule) == 0 {
return []Slot{{1, 12}}
}
if len(schedule) == 1 {
return inverseSchedule(schedule[0])
}
merged := Merge(schedule[0], schedule[1])
for _, s := range schedule[2:] {
merged = Merge(merged, s)
}
return inverseSchedule(merged)
}

Here you can find thesource code and the tests for the solution.In the next article, we consider other solutions for the problem and compare their algorithmic complexity.
===========
Источник:
habr.com
===========
Похожие новости:

Теги для поиска: #_programmirovanie (Программирование), #_algoritmy (Алгоритмы), #_go, #_go, #_programming, #_algorithms, #_interval, #_intervals, #_merge, #_programmirovanie (
Программирование
), #_algoritmy (
Алгоритмы
), #_go

Профиль ЛС

Ответить на тему

Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы

Текущее время: 22-Ноя 20:40
Часовой пояс: UTC + 5