// Time: O(nlogn) // Space: O(n) // BST solution. class Solution { public: enum {start, end, height}; struct Endpoint { int height; bool isStart; }; /** * @param buildings: A list of lists of integers * @return: Find the outline of those buildings */ vector> buildingOutline(vector> &buildings) { map> point_to_height; // Ordered, no duplicates. for (const auto& building : buildings) { point_to_height[building[start]].push_back({building[height], true}); point_to_height[building[end]].push_back({building[height], false}); } vector> res; map height_to_count; // BST. int curr_start = -1; int curr_max = 0; // Enumerate each point in increasing order. for (const auto& kvp : point_to_height) { const auto& point = kvp.first; const auto& heights = kvp.second; for (const auto& h : heights) { if (h.isStart) { ++height_to_count[h.height]; } else { --height_to_count[h.height]; if (height_to_count[h.height] == 0) { height_to_count.erase(h.height); } } } if (height_to_count.empty() || curr_max != height_to_count.crbegin()->first) { if (curr_max > 0) { res.push_back({curr_start, point, curr_max}); } curr_start = point; curr_max = height_to_count.empty() ? 0 : height_to_count.crbegin()->first; } } return res; } }; // Time: O(nlogn) // Space: O(n) // Divide and conquer solution. class Solution2 { public: enum {start, end, height}; /** * @param buildings: A list of lists of integers * @return: Find the outline of those buildings */ vector> buildingOutline(vector> &buildings) { return ComputeSkylineInInterval(buildings, 0, buildings.size()); } // Divide and Conquer. vector> ComputeSkylineInInterval(const vector>& buildings, int left_endpoint, int right_endpoint) { if (right_endpoint - left_endpoint <= 1) { // 0 or 1 skyline, just copy it. return {buildings.cbegin() + left_endpoint, buildings.cbegin() + right_endpoint}; } int mid = left_endpoint + ((right_endpoint - left_endpoint) / 2); auto left_skyline = ComputeSkylineInInterval(buildings, left_endpoint, mid); auto right_skyline = ComputeSkylineInInterval(buildings, mid, right_endpoint); return MergeSkylines(&left_skyline, &right_skyline); } // Merge Sort vector> MergeSkylines(vector> *left_skyline, vector> *right_skyline) { int i = 0, j = 0; vector> merged; while (i < left_skyline->size() && j < right_skyline->size()) { if ((*left_skyline)[i][end] < (*right_skyline)[j][start]) { merged.emplace_back(move((*left_skyline)[i++])); } else if ((*right_skyline)[j][end] < (*left_skyline)[i][start]) { merged.emplace_back(move((*right_skyline)[j++])); } else if ((*left_skyline)[i][start] <= (*right_skyline)[j][start]) { MergeIntersectSkylines(&merged, &(*left_skyline)[i], &i, &(*right_skyline)[j], &j); } else { // (*left_skyline)[i][start] > (*right_skyline)[j][start]. MergeIntersectSkylines(&merged, &(*right_skyline)[j], &j, &(*left_skyline)[i], &i); } } // Insert the remaining skylines. merged.insert(merged.end(), left_skyline->begin() + i, left_skyline->end()); merged.insert(merged.end(), right_skyline->begin() + j, right_skyline->end()); return merged; } // (*a)[start] <= (*b)[start] void MergeIntersectSkylines(vector> *merged, vector *a, int *a_idx, vector *b, int *b_idx) { if ((*a)[end] <= (*b)[end]) { if ((*a)[height] > (*b)[height]) { // |aaa| if ((*b)[end] != (*a)[end]) { // |abb|b (*b)[start] = (*a)[end]; merged->emplace_back(move(*a)), ++(*a_idx); } else { // aaa ++(*b_idx); // abb } } else if ((*a)[height] == (*b)[height]) { // abb (*b)[start] = (*a)[start], ++(*a_idx); // abb } else { // (*a)[height] < (*b)[height]. if ((*a)[start] != (*b)[start]) { // bb merged->push_back({(*a)[start], (*b)[start], (*a)[height]}); // |a|bb } ++(*a_idx); } } else { // (*a)[end] > (*b)[end]. if ((*a)[height] >= (*b)[height]) { // aaaa ++(*b_idx); // abba } else { // |bb| // |a||bb|a if ((*a)[start] != (*b)[start]) { merged->push_back({(*a)[start], (*b)[start], (*a)[height]}); } (*a)[start] = (*b)[end]; merged->emplace_back(move(*b)), ++(*b_idx); } } } };

Problem