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<>();
ans.add(new ArrayList<>(Arrays.asList(left, height)));
ans.add(new ArrayList<>(Arrays.asList(right, 0)));
return ans;
}
List<List<Integer>> leftSkyline = getSkyline(Arrays.copyOfRange(buildings, 0, n / 2));
List<List<Integer>> 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
addPoint(ans, left.get(i).get(0), Math.max(left.get(i++).get(1), rightY));
} else {
rightY = right.get(j).get(1); // update the ongoing rightY
addPoint(ans, right.get(j).get(0), Math.max(right.get(j++).get(1), leftY));
}
while (i < left.size())
addPoint(ans, left.get(i).get(0), left.get(i++).get(1));
while (j < right.size())
addPoint(ans, right.get(j).get(0), right.get(j++).get(1));
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;
ans.add(new ArrayList<>(Arrays.asList(x, y)));
}
}
leetcode
challenge
Here is the link for the problem:
https://leetcode.com/problems/the-skyline-problem/
Top comments (8)
good
Thank you😊
Good implementation, but lacks proper explanation and documentation
Thank you, I want to do that...but I don't to how can I create it with explanation.....
I don't know to create a blog.
I understand that it can be intimidating at first, everyone here had, has or will have that feeling at some point.
But if you face that challenge, one step at a time, everything will be fine 🙂🙂🙂.
Some advices to get started:
Use JavaDoc in your code
Documentation might seem irrelevant, useless, or hard to write right now but trust me, it will help.
First of all you will start a habit of documenting your code, a habit that will help you down the line in your career. And you will get better over time, avoiding the mistakes we all make when documenting something.
For example, you have a function called
addPoint
. Someone reading the code will need to search for that function in your solution and perform some mental gymnastics to figure out what it does. It also has some scary parameters likeList<List<Integer>>
. You should write down what this thing does. I assure you that in a month, if you read your solution, you won't have a clue.Documenting your code will also do half of the work of explanation for you. When I write something here, I create the code and then use the documentation to create the post. You just need to elaborate on the comments you've written.
Explain your thinking process
Why do you need the
merge
function? How do you calculate the points?Split your solution in logical parts and try to explain what you did and what problem it solves, why you chose this approach and how you did it. It doesn't have to be long, a paragraph or two will suffice.
After all, you will get a lot more feedback and interaction with other people of various levels of experience, if you try to have some explanation.
And don't worry that you will make mistakes. Everybody does all the time. This is a really friendly community and I promise you that you will get a lot more out of it if you try to get out of your comfort zone. 🙂🙂🙂
Hello sir, Thank you me for understanding me......but I honestly tell you, it will take time to make Blogs for leetcode solution
So it's quantity over quality
yeah