Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 119
Good morning! Here's your coding interview problem for today.

This problem was asked by Google.

Given a set of closed intervals, find the smallest set of numbers that covers all the intervals. If there are multiple smallest sets, return any of them.

For example, given the intervals `[0, 3], [2, 6], [3, 4], [6, 9]`, one set of numbers that covers all these intervals is `{3, 6}`.

Pull request:
Day119
Resolves #247.

Patch:
diff --git a/README.md b/README.md
index d64045c..44e6503 100644
--- a/README.md
+++ b/README.md
@@ -128,6 +128,7 @@ problems from
 * [Day 116](https://github.com/vaskoz/dailycodingproblem-go/issues/242)
 * [Day 117](https://github.com/vaskoz/dailycodingproblem-go/issues/245)
 * [Day 118](https://github.com/vaskoz/dailycodingproblem-go/issues/246)
+* [Day 119](https://github.com/vaskoz/dailycodingproblem-go/issues/247)
 * [Day 120](https://github.com/vaskoz/dailycodingproblem-go/issues/248)
 * [Day 122](https://github.com/vaskoz/dailycodingproblem-go/issues/252)
 * [Day 123](https://github.com/vaskoz/dailycodingproblem-go/issues/253)
diff --git a/day119/problem.go b/day119/problem.go
new file mode 100644
index 0000000..d6d2180
--- /dev/null
+++ b/day119/problem.go
@@ -0,0 +1,62 @@
+package day119
+
+import "sort"
+
+// Interval has a start and an end.
+type Interval struct {
+	Start, End int
+}
+
+// SmallestSetCoverage returns the smallest intervals that cover
+// the given intervals.
+func SmallestSetCoverage(intervals []Interval) []Interval {
+	if len(intervals) == 0 {
+		return nil
+	}
+	sort.Slice(intervals, func(i, j int) bool {
+		return intervals[i].Start < intervals[j].Start ||
+			(intervals[i].Start == intervals[j].Start &&
+				intervals[i].End < intervals[j].End)
+	})
+	var results []Interval
+	highMin := 0
+	lowMax := intervals[0].End
+	highest := lowMax
+	count := 1
+	n := len(intervals)
+	for i := 1; i <= n; i++ {
+		if i < n && intervals[i].Start <= highest {
+			highest = max(intervals[i].End, highest)
+			highMin = max(intervals[i].Start, highMin)
+			lowMax = min(lowMax, intervals[i].End)
+			highMin = max(highMin, lowMax)
+			count++
+		} else {
+			if count == 1 {
+				one := intervals[i-1].Start
+				lowMax = one
+				highMin = one
+			}
+			results = append(results, Interval{lowMax, highMin})
+			if i < n {
+				lowMax = intervals[i].End
+				highest = intervals[i].End
+				count = 1
+			}
+		}
+	}
+	return results
+}
+
+func max(a, b int) int {
+	if a > b {
+		return a
+	}
+	return b
+}
+func min(a, b int) int {
+	if a < b {
+		return a
+	}
+	return b
+}


Test patch:
diff --git a/day119/problem_test.go b/day119/problem_test.go
new file mode 100644
index 0000000..5f2a006
--- /dev/null
+++ b/day119/problem_test.go
@@ -0,0 +1,34 @@
+package day119
+
+import (
+	"reflect"
+	"testing"
+)
+
+var testcases = []struct {
+	intervals, expected []Interval
+}{
+	{nil, nil},
+	{[]Interval{{5, 10}}, []Interval{{5, 5}}},
+	{[]Interval{{0, 3}, {2, 6}, {3, 4}, {6, 9}}, []Interval{{3, 6}}},
+	{[]Interval{{0, 1}, {2, 4}, {3, 4}, {6, 9}}, []Interval{{0, 0}, {4, 4}, {6, 6}}},
+	{[]Interval{{10, 20}, {2, 4}, {3, 4}, {6, 9}}, []Interval{{4, 4}, {6, 6}, {10, 10}}},
+	{[]Interval{{10, 20}, {1, 10}, {3, 4}, {20, 30}}, []Interval{{4, 20}}},
+}
+
+func TestSmallestSetCoverage(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := SmallestSetCoverage(tc.intervals); !reflect.DeepEqual(result, tc.expected) {
+			t.Errorf("Expected %v got %v", tc.expected, result)
+		}
+	}
+}
+
+func BenchmarkSmallestSetCoverage(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			SmallestSetCoverage(tc.intervals)
+		}
+	}
+}