# The Skyline Problem

The only question that really stumped me during my Google interviews was The Skyline Problem. I remember only being able to write some up a solution in pseudocode after being given many hints before my time was up.

It's been banned for some time now, so I thought I'd dump the solution here. Maybe, I will elaborate and clean up the code some other time. It's one of the cleverest uses of an ordered map (usually implemented as a tree map) that I've seen.

``````#include <algorithm>
#include <iostream>
#include <map>
#include <sstream>
#include <utility>
#include <vector>

using namespace std;

namespace {
struct Wall {
enum Type : int {
LEFT = 1,
RIGHT = 0
};

int position;
int height;
Type type;

Wall(int position, int height, Wall::Type type) :
position(position), height(height), type(type) {}

bool operator<(const Wall &other) {
return position < other.position;
}
};

ostream& operator<<(ostream& stream, const Wall &w) {
return stream << "Position: " << to_string(w.position) << ';'
<< " Height: " << to_string(w.height) << ';'
<< " Type: " << (w.type == Wall::Type::LEFT ? "Left" : "Right");
}
}  // namespace

class Solution {
public:
vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
vector<Wall> walls;
for (const vector<int>& building : buildings) {
walls.emplace_back(building[0], building[2], Wall::Type::LEFT);
walls.emplace_back(building[1], building[2], Wall::Type::RIGHT);
}
sort(walls.begin(), walls.end());
vector<vector<int>> skyline;
map<int, int> heightCount;
for (vector<Wall>::const_iterator wallPtr = walls.cbegin(); wallPtr != walls.cend();) {
int currentPosition = wallPtr -> position;
do {
if (wallPtr -> type == Wall::Type::LEFT) {
++heightCount[wallPtr -> height];
} else if (wallPtr -> type == Wall::Type::RIGHT) {
if (--heightCount[wallPtr -> height] == 0) {
heightCount.erase(wallPtr -> height);
}
}
++wallPtr;
} while (wallPtr != walls.cend() && wallPtr -> position == currentPosition);
if (skyline.empty() || heightCount.empty() ||
heightCount.crbegin() -> first != skyline.back()[1]) {
skyline.emplace_back(vector<int>{
currentPosition, heightCount.empty() ? 0 : heightCount.crbegin() -> first});
}
}
return skyline;
}
};
``````