Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 191
Good morning! Here's your coding interview problem for today.

This problem was asked by Stripe.

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Intervals can "touch", such as `[0, 1]` and `[1, 2]`, but they won't be considered overlapping.

For example, given the intervals `(7, 9), (2, 4), (5, 8)`, return `1` as the last interval can be removed and the first two won't overlap.

The intervals are not necessarily sorted in any order.

Pull request description:
Day191
Resolves #395.

Patch:
diff --git a/README.md b/README.md
index 6ce3b31..c3633e6 100644
--- a/README.md
+++ b/README.md
@@ -201,3 +201,4 @@ problems from
 * [Day 188](https://github.com/vaskoz/dailycodingproblem-go/issues/388)
 * [Day 189](https://github.com/vaskoz/dailycodingproblem-go/issues/391)
 * [Day 190](https://github.com/vaskoz/dailycodingproblem-go/issues/393)
+* [Day 191](https://github.com/vaskoz/dailycodingproblem-go/issues/395)
diff --git a/day191/problem.go b/day191/problem.go
new file mode 100644
index 0000000..2c86b08
--- /dev/null
+++ b/day191/problem.go
@@ -0,0 +1,26 @@
+package day191
+
+import "sort"
+
+// Interval has a start and end.
+type Interval struct {
+	Start, End int
+}
+
+// MinRemoveNoOverlap returns the minimum number of intervals
+// to remove to remove all overlaps.
+// Runs in O(N log N) time.
+func MinRemoveNoOverlap(intervals []Interval) int {
+	sort.Slice(intervals, func(i, j int) bool {
+		return intervals[i].End < intervals[j].End
+	})
+	count := 0
+	current := -int(^uint(0)>>1) - 1
+	for _, interval := range intervals {
+		if interval.Start >= current {
+			count++
+			current = interval.End
+		}
+	}
+	return len(intervals) - count
+}


Test patch:
diff --git a/day191/problem_test.go b/day191/problem_test.go
new file mode 100644
index 0000000..cd0f77a
--- /dev/null
+++ b/day191/problem_test.go
@@ -0,0 +1,27 @@
+package day191
+
+import "testing"
+
+var testcases = []struct {
+	intervals []Interval
+	removes   int
+}{
+	{[]Interval{{7, 9}, {2, 4}, {5, 8}}, 1},
+}
+
+func TestMinRemoveNoOverlap(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := MinRemoveNoOverlap(tc.intervals); result != tc.removes {
+			t.Errorf("Expected %v, got %v", tc.removes, result)
+		}
+	}
+}
+
+func BenchmarkMinRemoveNoOverlap(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			MinRemoveNoOverlap(tc.intervals)
+		}
+	}
+}