-
Notifications
You must be signed in to change notification settings - Fork 0
/
merge.go
105 lines (97 loc) · 3.57 KB
/
merge.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
package merge
import (
"errors"
"intervals/merge/interval"
"sort"
)
// Takes a list of intervals and returns a list of
// merged intervals, i.e. a list of intervals where all overlapping
// intervals are merged together. In case of an error,
// the returned error object reflects the error and is not nil.
func Merge(intervals []interval.Interval) ([]interval.Interval, error) {
if len(intervals) == 0 {
return intervals, nil
}
/**
* Intervals are sorted ascendingly by their Start element.
* We do so to make the next step of merging work: we only
* have to iterate once over all intervals and no longer
* have to compare each interval with each other interval.
* This sorting step thus avoids quadratic runtime.
* This step introduces **invariant A**: no remaining intervals
* after the current interval can be merged with the last interval.
*
* Notes for discussion: sort.Slice is mentioned to be not stable.
* Do we need stable sorting here? No, we dont, because the
* order of the second element does not matter for merging.
*/
sort.Slice(intervals, func(a, b int) bool {
return intervals[a].Start < intervals[b].Start
})
/**
* We keep list of all merged intervals. This adds to the
* memory footprint of the algorithm: in the worst case for
* an input if size n we need twice the memory. We could
* improve here by merging in place or dropping the merged
* intervals from the list of intervals. For now, I keep
* it simple.
*/
merged := []interval.Interval{intervals[0]}
for _, currentInterval := range intervals[1:] {
last := merged[len(merged)-1]
/**
* If the current interval overlaps with the last,
* we can safely merge them and update the last interval
* to the merged one. This step is crucial to avoid quadratic
* runtime: in the next iteration of the for loop, we compare
* with the now updated, merged interval.
*/
if last.Overlaps(currentInterval) {
mergedInverval, err := MergeInterval(last, currentInterval)
if err != nil {
return nil, err
}
merged[len(merged)-1] = *mergedInverval
} else {
/**
* If the current interval does not overlap with the last one,
* we can move on to comparing the current interval to the remaining
* ones. We do so by updating the merged intervals list, appending
* the current interval. In the next iteration, we pick this very
* element as the one for comparison to the remaing intervals.
* We can safely do so due to invariant A: no remaining intervals
* after the current interval can be merged with the last interval.
* Their Start elements are bigger than the End element of the current
* interval. If not, the current interval would have been merged with
* with the last one.
*/
merged = append(merged, currentInterval)
}
}
return merged, nil
}
// Takes two intervals and returns a merged interval.
// In case of an error, the returned
// error object reflects the error and is not nil.
func MergeInterval(a, b interval.Interval) (*interval.Interval, error) {
return interval.New(
min(a.Start, b.Start),
max(a.End, b.End),
)
}
// Takes two intervals and returns a merged interval
// if the two intervals overlap.
//
// In case of an error, the returned
// error object reflects the error and is not nil.
//
// If the intervals do not overlap, the returned
// error object reflects the error and is not nil.
// The returned interval is empty.
func MergeIntervalsIfOverlap(a, b interval.Interval) (interval.Interval, error) {
if a.Overlaps(b) {
merged, err := MergeInterval(a, b)
return *merged, err
}
return interval.Interval{}, errors.New("Intervals do not overlap")
}