Maybe a good solution for this is just to merge everything in the X-axis, and then everything on the Y-axis
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?
1 Like
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/the-skyline-problem/discuss/398002/Divide-and-conquer-(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 1-size 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 X-line)
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 0-height [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 helper-dummy 1st [0,0] value
return (res[i] for i in range(1, len(res)))