Leetcode: The Skyline Problem
This question is asked in many, many, companies. But before this, let's know the difference between a dot (.) and an arrow (->).
foo->bar() is the same as (*foo).bar().
The parenthesizes above are necessary because of the binding strength of the * and . operators.
Given the location and heights of the buildings, I want to make the skyline.
The geometric information is given in buildings with left right, and height. [left, right, height]. The left is the left edge x coordinate, the right is the right edge x coordinate, height is the height of the building. The skyline is key of points represented in coordinate in the form [x1, y1] [x2, y2], etc. No consecutive horizontal lines of equal height!
We can try a naiive solution for each rectangle for each cell starting at r.left and r.right c in the cell gets the maximum or r.height and the previous value of c. So go over each rectangle and then cell and then that's how we attempt the solution. This is close now, but there is still a small amount of error. This means the running the time of the algorithm depends of the resolution of the output image.
If we're dealing with so many points, the solution is to reduce the number of points in play.We can look into each critical point and print the areas in each critical point.
for each rectangle r:
for each critical point c:
if c.x >= r.left && c.x < r.right;
c.y gets the max of r.height and previous value of c.y
As a result, we need to find all of the critical points on the left and right side of the given rectangle.
They are marked in black dots here:
So they are either edges if no intersections or intersections between rectangles.
We remove from priority queue when we encounter the end of a building. We get a part of final result when it is part of the priority queue.
We add the y to the priority queue. So, I couple the X value with the maximum value of the priority queue. We remove the original height and now return the new "maximum height".
Let's solve this problem in a nutshell again.
We got each of the rectangles. For each of the rectangles, label a start and end point. Order each point by the start point.
We also initialize the priority Queue. For the start, place the height inside of the priority queue. Add the start point of the rectangle to the final result. If we reach the end point of a rectangle, we subsequently remove this point from the priority queue and update the max_val. If there is no value in the priority queue with the updated maximum value, then we're done. Let's first do the Java Implementation, then try to convert it to C++. In Java, I'll have "true" represent the beginning of each point and the keyword "false" represent the end.
class Solution {
//return the skyline as denoted inside of the question.
public List<List<Integer>> getSkyline(int[][] buildings) {
//result
List<List<Integer>> res = new new ArrayList;
//Priority queue of points
TreeSet<Integer> pq = new TreeSet<>(Collections.reverseOrder());
//frequency
Map<Integer, Integer> freq = new HashMap<>();
//Point list
List<Point> points = getPoints(buildings);
pq.add(0);
//start with the original, put this inside of the frequency
freq.put(0, 1);
//traverse through all of the points.
for(Point p: points) {
int before = pq.first();
//add to priority queue if start
if(p.isStart) {
pq.add(p.y);
freq.put(p.y, freq.getOrDefault(p.y, 0) + 1) ;
} else {
//remove from priority queue if end and none in frequency array
freq.put(p.y, freq.getOrDefault(p.y, 0) + 1) ;
if(freq.get(p.y) == 0) {
pq.remove(p.y);
}
}
//remove first from priority queue
int after = pq.first();
if(after != before) {
//if we get different x values, add this to the final result.
res.add(new ArrayList<>(Arrays.asList(p.x, after)));
}
}
}
public List<Point> getPoints(int[][] buildings) {
//add the lists of all the points inside of the buildings with height and stuff and the end point.
//Sort the points to make a "priority queue"
//return the points XD
List<Point> points = new ArrayList<>();
for(int[] p: buildings) {
points.add(new Point(p[0], p[2], true));
points.add(new Point(p[1], p[2], false));
}
Collections.sort(points);
return points;
}
class Point implements Comparable<Point> {
int x;
int y;
boolean isStart;
Point(int x, int y, boolean isStart) {
this.x = x;
this.y = y;
this.isStart = isStart;
}
public int compareTo(Point o) {
//this is how we will sort the priority queue, by x first. If x is the same, then we will sort the priority queue by y value. Remember, ending has more precedence than the starting if we are doing this and starting has more precedence if we are trying to reference the object. So, we sort by first order of x, then by order of earliest ending to object starting.
//for both start points, enqueue the taller and for both end points, dequeue the shorter.
//else do enqueue first.
if(this.x != o.x) {
return this.x - o.x;
} else {
if(this.isStart && o.isStart) {
return -this.y + o.y;
} else if (this.isStart && !o.isStart) {
return -this.y - o.y;
} else if (!this.isStart && o.isStart) {
return this.y + o.y;
} else {
return this.y - o.y;
}
}
}
}
}
Now, let's attempt to work on the C++ implementation.
I assume double arraylist is simply denoted as a vector in C++.
push_back wants to add to the vector in C++, which can also be indicated as the ArrayList.
class Solution {
public:
vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
map<int, <vector<vector<int>>> points;
for(vector<int>& building : buildings) {
points[building[0]].push_back(building);
points[building[1]].push_back(building);
}
auto comp = [](const vector<int>& b1, const vector<int>& b2) {
return b1[2] < b2[2];
};
//priority queue with the comparator comp.
priority_queue<vector<int>, vector<vector<int>>, decltype(comp)> pq(comp);
vector<vector<int>> ans;
//go through all of the points.
for(auto it = points.begin(); it != points.end; ++it) {
int x = it->first;
vector<vector<int>> bs = it -> second;
//update the heap.
for(vector<int>&b : bs) {
if (x == b[0]) {
pq.push(b);
}
}
//pop the priority queue when you hit the right edge of the building you pop nodes off until the top node is a building whose right edge is still ahead.
while(!pq.empty() && pq.top()[1] <= x) {
pq.pop();
}
if(pq.empty()) {
ans.push_back({x, 0});
} else {
int h = pq.top()[2];
if(ans.empty() || h != ans.back()[1]) {
ans.push_back({x, h});
}
}
}
return ans;
}
};
Comments
Post a Comment