Maybe a good solution for this is just to merge everything in the Xaxis, and then everything on the Yaxis
Both test cases are identical.
The merge technique works. However, I used a slightly differently approach, with no recursion, and using priority queues and TreeMap. Here is the step by step approach.
Complexity  O(nlogn), works upto input size 10^4

Divide the input into two separate priority queues, start and end boundaries
 For start boundary, order by x in ascending order. If x values are equal, order by y in descending order
 For end boundary, order by x in ascending order. If x values are equal, order by y in ascending order
 Reason: for start, you want to process taller buildings first, for end, process shorter buildings first

Declare a TreeMap (similar to hashmap, but sorted by keys, addition and deletion are O(logn))
 the map will store the heights of previously processed boundaries and their counts.
 initialize the map with an entry (0,1).
 also declare a variable for tracking the currentMaxHeight, set to 0.

Process the start and end boundaries together one by one, like in a merge sort
 Peek the boundaries from both queues, and compare. The one with lower x value will be considered, if x are same, the start boundary will be considered.
 For start boundaries, increment the count of height by 1 in the map. If none present, add one.
 For end boundaries, decrement the count of height by 1 in the map. If it becomes 0, remove it.
 With every increment and decrement operations, check if there is new max value in the treemap.
 If yes, update currentMaxHeight to that new value, add the pair of the x value and new max to the result array
 If not, do nothing

Process the remaining entries int the end boundaries queue in similar way.
Hey this is a great explanation, but can you create some type of visualization like the count of smaller numbers problem?
c++ implementation
using namespace std;
struct Point{
int x;
int y;
bool start;
Point(int x, int y, bool start){
this>x = x;
this>y = y;
this>start = start;
}
};
struct Compare {
bool operator() (Point & p1, Point & p2){
if(p1.x == p2.x){
if(p1.start && p2.start) return p1.y > p2.y;
if(!p1.start && !p2.start) return p1.y < p2.y;
if(p1.start) return true;
}
return p1.x < p2.x;
}
} comparePoints;
std::vector<std::vector<int>> get_skyline(std::vector<std::vector<int>> buildings) {
// WRITE YOUR BRILLIANT CODE HERE
vector<Point> points;
multiset<int,greater<int>> s;
for(auto num: buildings) {
points.push_back(Point(num[0], num[2], true));
points.push_back(Point(num[1], num[2], false));
}
sort(points.begin(), points.end(), comparePoints);
vector<vector<int>> res;
int maxHeight = 0;
s.insert(maxHeight);
for(int i = 0; i < points.size(); i++) {
//cout << points[i].start << " " << points[i].x << ","<< points[i].y << endl;
if(!points[i].start) {
s.erase(points[i].y);
}else{
s.insert(points[i].y);
}
int currHeight = *s.begin();
//cout << currHeight << " " << maxHeight << endl;
if(maxHeight != currHeight) {
res.push_back({points[i].x, currHeight});
maxHeight = currHeight;
}
}
return res;
}
updated:
using namespace std;
struct Point{
int x;
int y;
bool start;
Point(int x, int y, bool start){
this>x = x;
this>y = y;
this>start = start;
}
};
struct Compare {
bool operator() (Point & p1, Point & p2){
if(p1.x == p2.x){
if(p1.start && p2.start) return p1.y > p2.y;
if(!p1.start && !p2.start) return p1.y < p2.y;
return p1.start ? true : false;
}
return p1.x < p2.x;
}
} comparePoints;
std::vector<std::vector<int>> get_skyline(std::vector<std::vector<int>> buildings) {
// WRITE YOUR BRILLIANT CODE HERE
vector<Point> points;
multiset<int,greater<int>> s;
for(auto num: buildings) {
points.push_back(Point(num[0], num[2], true));
points.push_back(Point(num[1], num[2], false));
}
sort(points.begin(), points.end(), comparePoints);
vector<vector<int>> res;
int maxHeight = 0;
s.insert(maxHeight);
for(int i = 0; i < points.size(); i++) {
//cout << points[i].start << " " << points[i].x << ","<< points[i].y << endl;
if(!points[i].start) {
auto it=s.find(points[i].y);
s.erase(it); // to delete one occurence
}else{
s.insert(points[i].y);
}
int currHeight = *s.begin();
//cout << currHeight << " " << maxHeight << endl;
if(maxHeight != currHeight) {
res.push_back({points[i].x, currHeight});
maxHeight = currHeight;
}
}
return res;
}
easy to understand divide & conquer approach
https://leetcode.com/problems/theskylineproblem/discuss/398002/Divideandconquer(C%2B%2B)
Sweepline algo + heap:
def getSkyline(self, buildings: List[List[int]]) > List[List[int]]:
# we need all building [start, height], [end, height] positions + building's [end, 0] markers.
# r,r,0 is the building end marker  we need to get [position,0] locations
# so we use 1size building markers with height 0 to add such information to the buildings array
buildings = [i for l,r,h in buildings for i in [[l,r,h],[r,r,0]]]
# sort by position and if there are building with the same [left,right], sort by tallerst first
# e.g. [1,5,2],[1,5,5],[1,5,10] > [1,5,10],[1,5,5],[1,5,2] so that the tallest is the first one
buildings.sort(key=lambda x: (x[0], x[2]))
# max_heap with a dummy value #1 to avoid checking if heap is empty or not
heap = [(0, float(inf))]
# res with a dummy value #2 to avoid checking if res is empty or not
res = [[0,0]]
# p is the sweepline position (aka all buildings start,end positions on the Xline)
for p,r,h in buildings:
# push in max_heap height and building right pos
# during "sweeplining" we need to know until when the current height is valid
# this is achived by pushing to the heap height + building's right side
heappush(heap, (h, r))
# remove all building's heights from the heap which have right side <= sweepline
# why <= and not < ??? The end of buildings is exclusive, so we need to track [start, end)
# but we remove the end of a building from the heap!!!
# the trick is due to "marker buldings" with [r,r] and height=0 we have the following sequence:
# [1,2,5]... [2,2,0], so technically we remove the building right side by the sweepline,
# but at the same time we still have the next point [2,2,0] which is
# not removed by the current sweepline [1,2,5] yet and is used to form the output array
while heap and heap[0][1] <= p:
heappop(heap)
# if max height in the heap is not the same as the last one stored in the output
# we know that we have a height change, which we need to save. [sweepline_pos, height]
# could be from a building e.g. [10,5] or it could be from the marker with 0height [10,0]
# e.g. end of overlapping buildings or just last building
if res[1][1] != heap[0][0]:
res.append([p, heap[0][0]])
# generator to drop the helperdummy 1st [0,0] value
return (res[i] for i in range(1, len(res)))