-
Notifications
You must be signed in to change notification settings - Fork 0
/
mergingIntervals.go
61 lines (50 loc) · 2.66 KB
/
mergingIntervals.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
package mergingIntervals
import "sort"
const (
// FirstIntervalElement is used to index the first interval in the slice of intervals.
FirstIntervalElement = 0
// StartOfInterval is used to index the startpoint of an interval.
StartOfInterval = 0
// EndOfInterval is used to index the endpoint of an interval.
EndOfInterval = 1
// IntervalLengthCheck is used to check the length of an interval-slice.
IntervalLengthCheck = 2
)
// Interval provides functions to merge and sort a slice of intervals.
type Interval struct{}
// Merge invokes helper-functions in order to sort and return a slice of merged intervals.
func (i Interval) Merge(intervalSlice [][]int) [][]int {
// If there are less than two Intervals in the slice of Intervals we can return the slice of intervals without doing anything.
if len(intervalSlice) < IntervalLengthCheck {
return intervalSlice
}
i.sortIntervalsByStart(intervalSlice)
return i.mergeIntervals(intervalSlice)
}
// mergeIntervals returns a slice of merged intervals.
func (i Interval) mergeIntervals(intervalSlice [][]int) [][]int {
returnedIntervals := [][]int{}
// the start and endpoint of the first interval in the slice is used as a comparison for the following intervals.
tmpIntervalStart := intervalSlice[FirstIntervalElement][StartOfInterval]
tmpIntervalEnd := intervalSlice[FirstIntervalElement][EndOfInterval]
for _, intervalElement := range intervalSlice {
// if: If the current interval can be merged with the previous interval, the endpoint of the previous interval is updated with the endpoint of the current interval.
if tmpIntervalEnd >= intervalElement[StartOfInterval] && tmpIntervalEnd < intervalElement[EndOfInterval] {
tmpIntervalEnd = intervalElement[EndOfInterval]
// elseif: If the current interval is unmergeable with the previous interval, append it to the returnedIntervals slice.
// Next, the start and endpoint of the current interval is used for comparison as tmpIntervalStart and tmpIntervalEnd.
} else if tmpIntervalEnd < intervalElement[StartOfInterval] {
returnedIntervals = append(returnedIntervals, []int{tmpIntervalStart, tmpIntervalEnd})
tmpIntervalStart = intervalElement[StartOfInterval]
tmpIntervalEnd = intervalElement[EndOfInterval]
}
}
returnedIntervals = append(returnedIntervals, []int{tmpIntervalStart, tmpIntervalEnd})
return returnedIntervals
}
// sortIntervalsByStart sorts the slice of intervals by its startpoints.
func (i Interval) sortIntervalsByStart(intervalSlice [][]int) {
sort.Slice(intervalSlice, func(firstIntervalIndex, secondIntervalIndex int) bool {
return intervalSlice[firstIntervalIndex][StartOfInterval] < intervalSlice[secondIntervalIndex][StartOfInterval]
})
}