Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 397
Good morning! Here's your coding interview problem for today.

This problem was asked by Microsoft.

You are given a list of jobs to be done, where each job is represented by a start time and end time. Two jobs are compatible if they don't overlap. Find the largest subset of compatible jobs.

For example, given the following jobs (there is no guarantee that jobs will be sorted):
```
[(0, 6),
(1, 4),
(3, 5),
(3, 8),
(4, 7),
(5, 9),
(6, 10),
(8, 11)]
```
Return:
```
[(1, 4),
(4, 7),
(8, 11)]
```

Pull request description:
Day397
Resolves #797.

Patch:
diff --git a/README.md b/README.md
index 3fe325e..64392a6 100644
--- a/README.md
+++ b/README.md
@@ -389,4 +389,5 @@ problems from
 * [Day 394](https://github.com/vaskoz/dailycodingproblem-go/issues/791)
 * [Day 395](https://github.com/vaskoz/dailycodingproblem-go/issues/793)
 * [Day 396](https://github.com/vaskoz/dailycodingproblem-go/issues/795)
+* [Day 397](https://github.com/vaskoz/dailycodingproblem-go/issues/797)
 
diff --git a/day397/problem.go b/day397/problem.go
new file mode 100644
index 0000000..82e0078
--- /dev/null
+++ b/day397/problem.go
@@ -0,0 +1,54 @@
+package day397
+
+import "sort"
+
+// Job has a start and end time.
+type Job struct {
+	Start, End int
+}
+
+// LargestSubsetCompatibleJobs returns the largest
+// subset of compatible jobs. Compatible jobs are non-overlapping.
+func LargestSubsetCompatibleJobs(jobs []Job) []Job {
+	copied := append([]Job{}, jobs...)
+	sort.Slice(copied, func(i, j int) bool {
+		if copied[i].End < copied[j].End {
+			return true
+		} else if copied[i].End == copied[j].End {
+			return copied[i].Start < copied[j].Start
+		}
+
+		return false
+	})
+
+	possible := make([][]Job, 0)
+
+	for _, job := range copied {
+		added := false
+
+		for i, p := range possible {
+			left := p[len(p)-1]
+
+			if job.Start >= left.End {
+				possible[i] = append(p, job)
+			}
+		}
+
+		if !added {
+			possible = append(possible, []Job{job})
+		}
+	}
+
+	largestSize := 0
+
+	var largest []Job
+
+	for _, p := range possible {
+		if len(p) > largestSize {
+			largestSize = len(p)
+			largest = p
+		}
+	}
+
+	return largest
+}


Test patch:
diff --git a/day397/problem_test.go b/day397/problem_test.go
new file mode 100644
index 0000000..8a2ad88
--- /dev/null
+++ b/day397/problem_test.go
@@ -0,0 +1,65 @@
+package day397
+
+import (
+	"reflect"
+	"testing"
+)
+
+// nolint
+var testcases = []struct {
+	jobs, expected []Job
+}{
+	{
+		[]Job{
+			{0, 6},
+			{1, 4},
+			{3, 5},
+			{3, 8},
+			{4, 7},
+			{5, 9},
+			{6, 10},
+			{8, 11},
+		},
+		[]Job{
+			{1, 4},
+			{4, 7},
+			{8, 11},
+		},
+	},
+	{
+		[]Job{
+			{0, 100},
+			{1, 3},
+			{3, 5},
+			{0, 10},
+			{6, 8},
+			{9, 10},
+			{6, 10},
+			{8, 11},
+		},
+		[]Job{
+			{1, 3},
+			{3, 5},
+			{6, 8},
+			{9, 10},
+		},
+	},
+}
+
+func TestLargestSubsetCompatibleJobs(t *testing.T) {
+	t.Parallel()
+
+	for _, tc := range testcases {
+		if res := LargestSubsetCompatibleJobs(tc.jobs); !reflect.DeepEqual(res, tc.expected) {
+			t.Errorf("Expected %v, got %v", tc.expected, res)
+		}
+	}
+}
+
+func BenchmarkLargestSubsetCompatibleJobs(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			LargestSubsetCompatibleJobs(tc.jobs)
+		}
+	}
+}