Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 200
Good morning! Here's your coding interview problem for today.

This problem was asked by Microsoft.

Let `X` be a set of `n` intervals on the real line. We say that a set of points `P` "stabs" `X` if every interval in `X` contains at least one point in `P`. Compute the smallest set of points that stabs `X`.

For example, given the intervals `[(1, 4), (4, 5), (7, 9), (9, 12)]`, you should return `[4, 9]`.

Pull request description:
Day200
Resolves #411.

Patch:
diff --git a/README.md b/README.md
index ff4f882..d334027 100644
--- a/README.md
+++ b/README.md
@@ -208,3 +208,4 @@ problems from
 * [Day 196](https://github.com/vaskoz/dailycodingproblem-go/issues/404)
 * [Day 197](https://github.com/vaskoz/dailycodingproblem-go/issues/405)
 * [Day 199](https://github.com/vaskoz/dailycodingproblem-go/issues/409)
+* [Day 200](https://github.com/vaskoz/dailycodingproblem-go/issues/411)
diff --git a/day200/problem.go b/day200/problem.go
new file mode 100644
index 0000000..8176b20
--- /dev/null
+++ b/day200/problem.go
@@ -0,0 +1,36 @@
+package day200
+
+import "sort"
+
+// Point is an integer representing a point on a line.
+type Point int
+
+// Interval on a line from start to end inclusive at both ends.
+type Interval struct {
+	Start, End Point
+}
+
+// StabIntervalPoints computes the smallest set of points that stabs X.
+// Runs in O(N log N), but modifies the input slice by sorting.
+func StabIntervalPoints(X []Interval) []Point {
+	if len(X) == 0 {
+		return nil
+	}
+	sort.Slice(X, func(i, j int) bool {
+		if X[i].End < X[j].End {
+			return true
+		} else if X[i].End == X[j].End {
+			return X[i].Start < X[j].Start
+		}
+		return false
+	})
+	P := []Point{X[0].End}
+	last := P[0]
+	for _, interval := range X {
+		if interval.Start > last {
+			last = interval.End
+			P = append(P, last)
+		}
+	}
+	return P
+}


Test patch:
diff --git a/day200/problem_test.go b/day200/problem_test.go
new file mode 100644
index 0000000..ae3dcd6
--- /dev/null
+++ b/day200/problem_test.go
@@ -0,0 +1,36 @@
+package day200
+
+import (
+	"reflect"
+	"testing"
+)
+
+var testcases = []struct {
+	X []Interval
+	P []Point
+}{
+	{[]Interval{{1, 4}, {4, 5}, {7, 9}, {9, 12}}, []Point{4, 9}},
+	{[]Interval{}, nil},
+	{nil, nil},
+	{[]Interval{{9, 12}, {7, 9}, {4, 5}, {1, 4}}, []Point{4, 9}},
+	{[]Interval{{9, 12}, {7, 9}, {4, 5}, {1, 4}, {3, 5}}, []Point{4, 9}},
+}
+
+func TestStabIntervalPoints(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		input := append([]Interval{}, tc.X...)
+		if result := StabIntervalPoints(input); !reflect.DeepEqual(result, tc.P) {
+			t.Errorf("Expected %v, got %v", tc.P, result)
+		}
+	}
+}
+
+func BenchmarkStabIntervalPoints(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			input := append([]Interval{}, tc.X...)
+			StabIntervalPoints(input)
+		}
+	}
+}