Given_N_buildings in a x-axis，each building is a rectangle and can be represented by a triple (start, end, height)，where start is the start position on x-axis, end is the end position on x-axis and height is the height of the building. Buildings may overlap if you see them from far away，find the outline of them。
An outline can be represented by a triple, (start, end, height), where start is the start position on x-axis of the outline, end is the end position on x-axis and height is the height of the outline.
Notice
Please merge the adjacent outlines if they have the same height and make sure different outlines cant overlap on x-axis.
Have you met this question in a real interview?
Yes
Example
Given 3 buildings：
[
[1, 3, 3],
[2, 4, 4],
[5, 6, 1]
]
The outlines are：
[
[1, 2, 3],
[2, 4, 4],
[5, 6, 1]
]
//hash map with dup values
class HashHeap {
class Node {
int id, num;
public Node(int id, int num) {
this.id = id;
this.num = num;
}
public Node(Node node) {
this.id = node.id;
this.num = node.num;
}
}
List<Integer> heap = null;
HashMap<Integer, Node> hash = null;
int size;
String mod;
public HashHeap(String mod) {
this.heap = new ArrayList<Integer>();
this.size = 0;
this.mod = mod;
this.hash = new HashMap<Integer, Node>();
}
public int getParent(int index) {
if (index == 0) {
return -1;
}
return (index - 1) / 2;
}
public int getLeft(int index) {
return 2 * index + 1;
}
public int getRight(int index) {
return 2 * index + 2;
}
public void swap(int indexA, int indexB) {
int valA = heap.get(indexA);
int valB = heap.get(indexB);
int numA = hash.get(valA).num;
int numB = hash.get(valB).num;
hash.put(valB, new Node(indexA, numB));
hash.put(valA, new Node(indexB, numA));
heap.set(indexB, valA);
heap.set(indexA, valB);
}
public boolean compare(int a, int b) {
//which one should be closer to the top
if (a > b) {
if (mod == "min") {
return false;
} else {
return true;
}
} else {
if (mod == "min") {
return true;
} else {
return false;
}
}
}
public void siftUp(int id) {
while (getParent(id) > -1) {
int parentId = getParent(id);
if (compare(heap.get(parentId), heap.get(id)) == true) {
break;
} else {
swap(id, parentId);
}
id = parentId;
}
}
public void siftDown(int index) {
while (getLeft(index) < heap.size()) {
int left = getLeft(index);
int right = getRight(index);
int son = 0;
if (right >= heap.size() || compare(heap.get(left), heap.get(right))) {
son = left;
} else { // right < heap.size() && !compare(heap.get(left), heap.get(right))
son = right;
}
if (compare(heap.get(index), heap.get(son))) {
break;
} else {
swap(index, son);
}
index = son;
}
}
public int poll() {
int val = heap.get(0);
this.size--;
Node cur = hash.get(val);
int num = cur.num;
int id = cur.id;
if (hash.get(val).num > 1) {
hash.put(val, new Node(id, num));
return val;
}
swap(0, heap.size() - 1);
heap.remove(heap.size() - 1);
hash.remove(val);
siftDown(0);
return val;
}
public void add(int val) {
this.size++;
if (hash.containsKey(val)) {
Node cur = hash.get(val);
hash.put(val, new Node(cur.id, cur.num + 1));
return;
}
heap.add(val);
hash.put(val, new Node(heap.size() - 1, 1));
siftUp(heap.size() - 1);
}
public void remove(int val) {
this.size--;
Node cur = hash.get(val);
int num = cur.num;
int index = cur.id;
if (num > 1) {
hash.put(val, new Node(index, num - 1));
} else {
swap(index, heap.size() - 1);
hash.remove(val);
heap.remove(heap.size() - 1);
if (index < heap.size()) {
siftUp(index);
siftDown(index);
}
}
}
public int peek() {
return heap.get(0);
}
public boolean isEmpty() {
return this.size == 0;
}
}
class Edge {
int pos,height;
boolean isStart;
public Edge(int pos, int height, boolean isStart) {
this.isStart = isStart;
this.pos = pos;
this.height = height;
}
}
public class Solution {
/*
* @param buildings: A list of lists of integers
* @return: Find the outline of those buildings
*/
public List<List<Integer>> buildingOutline(int[][] buildings) {
// write your code here
List<List<Integer>> ans = new ArrayList<>();
if (buildings == null || buildings.length == 0 || buildings[0] == null || buildings[0].length == 0) {
return ans;
}
List<Edge> edges = new ArrayList<>();
for (int[] building : buildings) {
Edge start = new Edge(building[0], building[2], true);
edges.add(start);
Edge end = new Edge(building[1], building[2], false);
edges.add(end);
}
//hash heap
// PriorityQueue<Integer> hashHeap = new PriorityQueue<Integer>(new Comparator<Integer>(){
// public int compare(Integer a, Integer b) {
// return b - a;
// }
// });
HashHeap hashHeap = new HashHeap("max");
Collections.sort(edges, new Comparator<Edge>(){
public int compare(Edge a, Edge b) {
if (a.pos != b.pos) {
return a.pos - b.pos;
}
if (a.isStart && b.isStart) {
return b.height - a.height;
}
if (!a.isStart && !b.isStart) {
return a.height - b.height;
}
return a.isStart ? -1 : 1;
}
});
for (Edge edge : edges) {
//if the edge is a starting edge
if (edge.isStart) {
//hashheap being empty: no points or start fresh, height change point, need to enter an entry
//the newly entered edge has a lower height: ignore
//the newly entered edge has a higher height: height change point, so enter a entry into the result set
if (hashHeap.isEmpty() || edge.height > hashHeap.peek()) {
List<Integer> current = new ArrayList<>();
current.add(edge.pos);
current.add(edge.height);
ans.add(current);
}
hashHeap.add(edge.height);
} else {
hashHeap.remove(edge.height);
if (hashHeap.isEmpty() || edge.height > hashHeap.peek()) {
List<Integer> current = new ArrayList<>();
if (hashHeap.isEmpty()) {
current.add(edge.pos);
current.add(0);
} else {
current.add(edge.pos);
current.add(hashHeap.peek());
}
ans.add(current);
}
}
}
// for (List<Integer> list : ans) {
// for (Integer item : list) {
// System.out.print(item + ",");
// }
// System.out.println("");
// }
return output(ans);
}
public List<List<Integer>> output(List<List<Integer>> ans) {
List<List<Integer>> res = new ArrayList<>();
if (ans == null || ans.size() == 0) {
return res;
}
int pre = ans.get(0).get(0);
int height = ans.get(0).get(1);
for (int i = 1; i < ans.size(); i++) {
int post = ans.get(i).get(0);
if (height > 0) {
List<Integer> cur = new ArrayList<>();
cur.add(pre);
cur.add(post);
cur.add(height);
res.add(cur);
}
pre = post;
height = ans.get(i).get(1);
}
return res;
}
}