Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 77
Good morning! Here's your coding interview problem for today.

This problem was asked by Snapchat.

Given a list of possibly overlapping intervals, return a new list of intervals where all overlapping intervals have been merged.

The input list is not necessarily ordered in any way.

For example, given `[(1, 3), (5, 8), (4, 10), (20, 25)]`, you should return `[(1, 3), (4, 10), (20, 25)]`.

Pull request:
Day77
Resolves #163.

Patch:
diff --git a/README.md b/README.md
index f422f86..5bec506 100644
--- a/README.md
+++ b/README.md
@@ -86,3 +86,4 @@ problems from
 * [Day 74](https://github.com/vaskoz/dailycodingproblem-go/issues/157)
 * [Day 75](https://github.com/vaskoz/dailycodingproblem-go/issues/159)
 * [Day 76](https://github.com/vaskoz/dailycodingproblem-go/issues/161)
+* [Day 77](https://github.com/vaskoz/dailycodingproblem-go/issues/163)
diff --git a/day77/problem.go b/day77/problem.go
new file mode 100644
index 0000000..017bf75
--- /dev/null
+++ b/day77/problem.go
@@ -0,0 +1,39 @@
+package day77
+
+import "sort"
+
+// Interval represents a linear span between start and end positions.
+type Interval struct {
+	Start, End int
+}
+
+// MergeOverlappingIntervals merges any overlapping intervals.
+// Runs in O(N log N) because of the sorting.
+func MergeOverlappingIntervals(intervals []Interval) []Interval {
+	if len(intervals) == 0 {
+		return nil
+	}
+	sort.Slice(intervals, func(i, j int) bool {
+		if intervals[i].Start < intervals[j].Start {
+			return true
+		} else if intervals[i].Start == intervals[j].Start {
+			return intervals[i].End <= intervals[j].End
+		} else {
+			return false
+		}
+	})
+	merged := make([]Interval, 0, len(intervals))
+	current := intervals[0]
+	for i := 1; i < len(intervals); i++ {
+		if intervals[i].Start < current.End {
+			if intervals[i].End > current.End {
+				current.End = intervals[i].End
+			}
+		} else {
+			merged = append(merged, current)
+			current = intervals[i]
+		}
+	}
+	merged = append(merged, current)
+	return merged
+}


Test patch:
diff --git a/day77/problem_test.go b/day77/problem_test.go
new file mode 100644
index 0000000..f1bbbc4
--- /dev/null
+++ b/day77/problem_test.go
@@ -0,0 +1,38 @@
+package day77
+
+import (
+	"reflect"
+	"testing"
+)
+
+var testcases = []struct {
+	input, expected []Interval
+}{
+	{nil, nil},
+	{[]Interval{}, nil},
+	{[]Interval{
+		{1, 3}, {5, 8}, {4, 10}, {20, 25}},
+		[]Interval{{1, 3}, {4, 10}, {20, 25}},
+	},
+	{[]Interval{
+		{1, 3}, {1, 8}, {4, 10}, {20, 25}},
+		[]Interval{{1, 10}, {20, 25}},
+	},
+}
+
+func TestMergeOverlappingIntervals(t *testing.T) {
+	t.Parallel()
+	for tcid, tc := range testcases {
+		if result := MergeOverlappingIntervals(tc.input); !reflect.DeepEqual(result, tc.expected) {
+			t.Errorf("TC%d Expected %v got %v", tcid, tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkMergeOverlappingIntervals(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MergeOverlappingIntervals(tc.input)
+		}
+	}
+}