Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 286
Good morning! Here's your coding interview problem for today.

This problem was asked by VMware.

The skyline of a city is composed of several buildings of various widths and heights, possibly overlapping one another when viewed from a distance. We can represent the buildings using an array of (left, right, height) tuples, which tell us where on an imaginary x-axis a building begins and ends, and how tall it is. The skyline itself can be described by a list of (x, height) tuples, giving the locations at which the height visible to a distant observer changes, and each new height.

Given an array of buildings as described above, create a function that returns the skyline.

For example, suppose the input consists of the buildings `[(0, 15, 3), (4, 11, 5), (19, 23, 4)]`. In aggregate, these buildings would create a skyline that looks like the one below.
```
     ______  
    |      |        ___
 ___|      |___    |   | 
|   |   B  |   |   | C |
| A |      | A |   |   |
|   |      |   |   |   |
```
------------------------
As a result, your function should return `[(0, 3), (4, 5), (11, 3), (15, 0), (19, 4), (23, 0)]`.

Pull request:
Day286
Resolves #585.

Patch:
diff --git a/README.md b/README.md
index e9c79db..96b06b4 100644
--- a/README.md
+++ b/README.md
@@ -294,3 +294,4 @@ problems from
 * [Day 283](https://github.com/vaskoz/dailycodingproblem-go/issues/577)
 * [Day 284](https://github.com/vaskoz/dailycodingproblem-go/issues/578)
 * [Day 285](https://github.com/vaskoz/dailycodingproblem-go/issues/583)
+* [Day 286](https://github.com/vaskoz/dailycodingproblem-go/issues/585)
diff --git a/day286/problem.go b/day286/problem.go
new file mode 100644
index 0000000..adb0c4a
--- /dev/null
+++ b/day286/problem.go
@@ -0,0 +1,67 @@
+package day286
+
+// Building represents a 2D building.
+type Building struct {
+	Left, Right, Height int
+}
+
+// Skyline represents vertical edges of the skyline.
+type Skyline struct {
+	X, Height int
+}
+
+// CreateSkyline returns the skyline.
+// Runs in O(N log N).
+func CreateSkyline(buildings []Building) []Skyline {
+	return createSkyline(buildings, 0, len(buildings)-1)
+}
+
+func createSkyline(buildings []Building, l, r int) []Skyline {
+	if l == r {
+		result := make([]Skyline, 2)
+		result[0] = Skyline{buildings[l].Left, buildings[l].Height}
+		result[1] = Skyline{buildings[l].Right, 0}
+		return result
+	}
+	mid := (l + r) / 2
+	sl := createSkyline(buildings, l, mid)
+	sr := createSkyline(buildings, mid+1, r)
+	return merge(sl, sr)
+}
+
+func max(a, b int) int {
+	if a > b {
+		return a
+	}
+	return b
+}
+
+func merge(sky1, sky2 []Skyline) []Skyline {
+	result := make([]Skyline, 0, len(sky1)+len(sky2))
+	var h1, h2, i, j int
+
+	for i < len(sky1) && j < len(sky2) {
+		if sky1[i].X < sky2[j].X {
+			x1 := sky1[i].X
+			h1 = sky1[i].Height
+			maxh := max(h1, h2)
+			result = append(result, Skyline{x1, maxh})
+			i++
+		} else {
+			x2 := sky2[j].X
+			h2 = sky2[j].Height
+			maxh := max(h1, h2)
+			result = append(result, Skyline{x2, maxh})
+			j++
+		}
+	}
+	for i < len(sky1) {
+		result = append(result, sky1[i])
+		i++
+	}
+	for j < len(sky2) {
+		result = append(result, sky2[j])
+		j++
+	}
+	return result
+}


Test patch:
diff --git a/day286/problem_test.go b/day286/problem_test.go
new file mode 100644
index 0000000..9489519
--- /dev/null
+++ b/day286/problem_test.go
@@ -0,0 +1,38 @@
+package day286
+
+import (
+	"reflect"
+	"testing"
+)
+
+// nolint
+var testcases = []struct {
+	buildings []Building
+	skyline   []Skyline
+}{
+	{
+		[]Building{{0, 15, 3}, {4, 11, 5}, {19, 23, 4}},
+		[]Skyline{{0, 3}, {4, 5}, {11, 3}, {15, 0}, {19, 4}, {23, 0}},
+	},
+	{
+		[]Building{{5, 7, 10}, {8, 20, 5}, {9, 12, 7}, {10, 15, 12}, {18, 25, 6}},
+		[]Skyline{{5, 10}, {7, 0}, {8, 5}, {9, 7}, {10, 12}, {12, 12}, {15, 5}, {18, 6}, {20, 6}, {25, 0}},
+	},
+}
+
+func TestCreateSkyline(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if skyline := CreateSkyline(tc.buildings); !reflect.DeepEqual(skyline, tc.skyline) {
+			t.Errorf("Expected %v, got %v", tc.skyline, skyline)
+		}
+	}
+}
+
+func BenchmarkCreateSkyline(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			CreateSkyline(tc.buildings)
+		}
+	}
+}