## Approach 1: Merge Sort

• Time:O(n\log n)
• Space:O(n)

## C++

``````class Solution {
public:
vector<vector<int>> getSkyline(const vector<vector<int>>& buildings) {
const int n = buildings.size();
if (n == 0)
return {};
if (n == 1) {
const int left = buildings[0][0];
const int right = buildings[0][1];
const int height = buildings[0][2];
return {{left, height}, {right, 0}};
}

const auto left = getSkyline({begin(buildings), begin(buildings) + n / 2});
const auto right = getSkyline({begin(buildings) + n / 2, end(buildings)});
return merge(left, right);
}

private:
vector<vector<int>> merge(const vector<vector<int>>& left,
const vector<vector<int>>& right) {
vector<vector<int>> ans;
int i = 0;  // left's index
int j = 0;  // right's index
int leftY = 0;
int rightY = 0;

while (i < left.size() && j < right.size())
// choose the point with smaller x
if (left[i][0] < right[j][0]) {
leftY = left[i][1];  // update the ongoing leftY
} else {
rightY = right[j][1];  // update the ongoing rightY
}

while (i < left.size())

while (j < right.size())

return ans;
}

void addPoint(vector<vector<int>>& ans, int x, int y) {
if (!ans.empty() && ans.back()[0] == x) {
ans.back()[1] = y;
return;
}
if (!ans.empty() && ans.back()[1] == y)
return;
ans.push_back({x, y});
}
};
``````

## JAVA

``````class Solution {
public List<List<Integer>> getSkyline(int[][] buildings) {
final int n = buildings.length;
if (n == 0)
return new ArrayList<>();
if (n == 1) {
final int left = buildings[0][0];
final int right = buildings[0][1];
final int height = buildings[0][2];
List<List<Integer>> ans = new ArrayList<>();
return ans;
}

var leftSkyline = getSkyline(Arrays.copyOfRange(buildings, 0, n / 2));
var rightSkyline = getSkyline(Arrays.copyOfRange(buildings, n / 2, n));
return merge(leftSkyline, rightSkyline);
}

private List<List<Integer>> merge(List<List<Integer>> left, List<List<Integer>> right) {
List<List<Integer>> ans = new ArrayList<>();
int i = 0; // left's index
int j = 0; // right's index
int leftY = 0;
int rightY = 0;

while (i < left.size() && j < right.size())
// choose the point with smaller x
if (left.get(i).get(0) < right.get(j).get(0)) {
leftY = left.get(i).get(1); // update the ongoing leftY
} else {
rightY = right.get(j).get(1); // update the ongoing rightY
}

while (i < left.size())

while (j < right.size())

return ans;
}

private void addPoint(List<List<Integer>> ans, int x, int y) {
if (!ans.isEmpty() && ans.get(ans.size() - 1).get(0) == x) {
ans.get(ans.size() - 1).set(1, y);
return;
}
if (!ans.isEmpty() && ans.get(ans.size() - 1).get(1) == y)
return;
}
}
``````

## Python

``````class Solution:
def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
n = len(buildings)
if n == 0:
return []
if n == 1:
left, right, height = buildings[0]
return [[left, height], [right, 0]]

left = self.getSkyline(buildings[:n // 2])
right = self.getSkyline(buildings[n // 2:])
return self._merge(left, right)

def _merge(self, left: List[List[int]], right: List[List[int]]) -> List[List[int]]:
ans = []
i = 0  # left's index
j = 0  # right's index
leftY = 0
rightY = 0

while i < len(left) and j < len(right):
# choose the powith smaller x
if left[i][0] < right[j][0]:
leftY = left[i][1]  # update the ongoing leftY
i += 1
else:
rightY = right[j][1]  # update the ongoing rightY
j += 1

while i < len(left):
i += 1

while j < len(right):
j += 1

return ans

def _addPoint(self, ans: List[List[int]], x: int, y: int) -> None:
if ans and ans[-1][0] == x:
ans[-1][1] = y
return
if ans and ans[-1][1] == y:
return
ans.append([x, y])
``````

## Approach 2: C++ `std::multiset`

• Time:O(n\log n)
• Space:O(n)

## C++

``````class Solution {
public:
vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
vector<vector<int>> ans;
vector<vector<int>> events;  // {{Li, Hi} | {Ri, -Hi}}

for (const auto& b : buildings) {
events.push_back({b[0], b[2]});
events.push_back({b[1], -b[2]});  // minus to indicate leaving
}

sort(begin(events), end(events), [](const auto& a, const auto& b) {
// same entering, sort from higher to lower
// same leaving, sort from lower to higher
return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
});

for (const auto& event : events) {
const int x = event[0];
const int h = abs(event[1]);
const int isEntering = event[1] > 0;
if (isEntering) {
if (h > maxHeight())
ans.push_back({x, h});
set.insert(h);
} else {
set.erase(set.equal_range(h).first);
if (h > maxHeight())
ans.push_back({x, maxHeight()});
}
}

return ans;
}

private:
multiset<int> set;
int maxHeight() const {
return set.empty() ? 0 : *rbegin(set);
}
};
``````