Building Outline 131
Question
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.
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] ]
Solution
我的解法:用一个带最大堆的扫描线遍历数组,每出现一个拐点则记录一次区间。新加入一个元素后若堆顶元素和之前不同,则表明出现拐点。
首先处理数组中元素。将每一个点用一个point来保存,保存time(开始写错了,应该是位置,但是要改的太多了),flag(起点为1,终点为0),height。用一个HashMap来记录每一对终点和起点(终点为key,起点为value)。
将所有point保存在一个list中并排序,首先根据时间从小到大排序,若时间相等则根据flag排序(先起点后终点),若flag也相等则根据height排序(若同为起点则从大到小排序,若同为终点则从小到大排序)。这样可以避免重复解。
再构建一个最大堆,用于记录加入的元素的最大值。
开始遍历list中每个point,起点元素加入堆,终点元素删去堆中对应的起点元素。
当遇到一个起点元素时,先记录加入前堆顶元素,然后将该起点元素加入,再看加入后堆顶元素,1)若没有变化,则继续下一个point;2)若有变化,则说明出现拐点,将之前堆顶元素时间作为起点,当前堆顶元素时间作为终点,之前堆顶元素高度作为高度。注意:就算堆顶元素变化,但是如果之前堆顶元素和当前堆顶元素时间相同,说明是在这个时间连续有几个起点被加入,宽度为0,不能算一个区间。
当遇到一个终点元素时,将其对应的起点元素从堆中删除。若此时堆为空,则和5中一样记录一个区间,并继续下一个point。若堆不为空,则需要看此时堆顶元素是否改变。若不变则继续,否则说明出现“拐点”。此处“拐点”要分两种情况讨论: 1)若新的堆顶元素高度和之前堆顶元素高度相同,则说明相同高度的两段区间有重叠,题目要求若发生这种情况要合并这两段区间,所以我们要保留之前的堆顶元素(两段同高度相同重叠区间的最左边),删去新的堆顶元素(即代替原堆顶元素被删除,因为每遇到一个终点必须删去一个起点),具体做法可以是先删去新堆顶元素,再加入原堆顶元素,或者直接将新堆顶元素时间改为原堆顶元素时间。 2)若新堆顶和原堆顶元素高度不同,则像5中那样记录一个区间,但是要将现在的堆顶元素时间改为遇到的终点元素的时间。
遍历完整个list结束
九章解法:用HashMap解,有hashmap模版。
代码如下:
public class Solution {
/**
* @param buildings: A list of lists of integers
* @return: Find the outline of those buildings
*/
class Point{
int time;
//1 -> start, 0 -> end
int flag;
int height;
public Point(int time, int flag, int height){
this.time = time;
this.flag = flag;
this.height = height;
}
}
public ArrayList<ArrayList<Integer>> buildingOutline(int[][] buildings) {
// write your code here
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
if(buildings == null || buildings.length == 0 || buildings[0].length == 0){
return res;
}
HashMap<Point, Point> map = new HashMap<Point, Point>();
ArrayList<Point> list = new ArrayList<Point>();
for(int i = 0; i < buildings.length; i++){
Point start = new Point(buildings[i][0], 1, buildings[i][2]);
Point end = new Point(buildings[i][1], 0, buildings[i][2]);
list.add(start);
list.add(end);
map.put(end, start);
}
Collections.sort(list, new Comparator<Point>(){
public int compare(Point a, Point b){
if(a.time == b.time){
if(a.flag == b.flag){
if(a.flag == 1){
return b.height - a.height;
}else{
return a.height - b.height;
}
}else{
return b.flag - a.flag;
}
}else{
return a.time - b.time;
}
}
});
Queue<Point> queue = new PriorityQueue<Point>(1, new Comparator<Point>(){
public int compare(Point a, Point b){
if(a.height == b.height){
return a.time - b.time;
}else{
return b.height - a.height;
}
}
});
for(int i = 0; i < list.size(); i++){
if(queue.size() == 0){
queue.offer(list.get(i));
continue;
}
ArrayList<Integer> temp = new ArrayList<Integer>();
Point pre = queue.peek();
Point next = list.get(i);
if(next.flag == 1){
queue.offer(next);
Point curt = queue.peek();
if(curt != pre){
if(curt.time == pre.time){
continue;
}
temp.add(pre.time);
temp.add(curt.time);
temp.add(pre.height);
res.add(temp);
}else{
continue;
}
}else{
queue.remove(map.get(next));
if(queue.size() == 0){
temp.add(pre.time);
temp.add(next.time);
temp.add(pre.height);
res.add(temp);
continue;
}
Point curt = queue.peek();
if(curt != pre){
if(curt.height == pre.height){
curt.time = pre.time;
continue;
}
temp.add(pre.time);
temp.add(next.time);
temp.add(pre.height);
res.add(temp);
curt.time = next.time;
}else{
continue;
}
}
}
return res;
}
}
HashMap:
public class Solution {
//HashMap模版
class HashHeap {
ArrayList<Integer> heap;
String mode;
int size_t;
HashMap<Integer, Node> hash;
class Node {
public Integer id;
public Integer num;
Node(Node now) {
id = now.id;
num = now.num;
}
Node(Integer first, Integer second) {
this.id = first;
this.num = second;
}
}
public HashHeap(String mod) {
// TODO Auto-generated constructor stub
heap = new ArrayList<Integer>();
mode = mod;
hash = new HashMap<Integer, Node>();
size_t = 0;
}
public int peek() {
return heap.get(0);
}
public int size() {
return size_t;
}
public Boolean isEmpty() {
return (heap.size() == 0);
}
int parent(int id) {
if (id == 0) {
return -1;
}
return (id - 1) / 2;
}
int lson(int id) {
return id * 2 + 1;
}
int rson(int id) {
return id * 2 + 2;
}
boolean comparesmall(int a, int b) {
if (a <= b) {
if (mode == "min")
return true;
else
return false;
} else {
if (mode == "min")
return false;
else
return true;
}
}
void swap(int idA, int idB) {
int valA = heap.get(idA);
int valB = heap.get(idB);
int numA = hash.get(valA).num;
int numB = hash.get(valB).num;
hash.put(valB, new Node(idA, numB));
hash.put(valA, new Node(idB, numA));
heap.set(idA, valB);
heap.set(idB, valA);
}
public Integer poll() {
size_t--;
Integer now = heap.get(0);
Node hashnow = hash.get(now);
if (hashnow.num == 1) {
swap(0, heap.size() - 1);
hash.remove(now);
heap.remove(heap.size() - 1);
if (heap.size() > 0) {
siftdown(0);
}
} else {
hash.put(now, new Node(0, hashnow.num - 1));
}
return now;
}
public void add(int now) {
size_t++;
if (hash.containsKey(now)) {
Node hashnow = hash.get(now);
hash.put(now, new Node(hashnow.id, hashnow.num + 1));
} else {
heap.add(now);
hash.put(now, new Node(heap.size() - 1, 1));
}
siftup(heap.size() - 1);
}
public void delete(int now) {
size_t--;
Node hashnow = hash.get(now);
int id = hashnow.id;
int num = hashnow.num;
if (hashnow.num == 1) {
swap(id, heap.size() - 1);
hash.remove(now);
heap.remove(heap.size() - 1);
if (heap.size() > id) {
siftup(id);
siftdown(id);
}
} else {
hash.put(now, new Node(id, num - 1));
}
}
void siftup(int id) {
while (parent(id) > -1) {
int parentId = parent(id);
if (comparesmall(heap.get(parentId), heap.get(id)) == true) {
break;
} else {
swap(id, parentId);
}
id = parentId;
}
}
void siftdown(int id) {
while (lson(id) < heap.size()) {
int leftId = lson(id);
int rightId = rson(id);
int son;
if (rightId >= heap.size()
|| (comparesmall(heap.get(leftId), heap.get(rightId)) == true)) {
son = leftId;
} else {
son = rightId;
}
if (comparesmall(heap.get(id), heap.get(son)) == true) {
break;
} else {
swap(id, son);
}
id = son;
}
}
}
class Edge {
int pos;
int height;
boolean isStart;
public Edge(int pos, int height, boolean isStart) {
this.pos = pos;
this.height = height;
this.isStart = isStart;
}
}
class EdgeComparator implements Comparator<Edge> {
@Override
public int compare(Edge arg1, Edge arg2) {
Edge l1 = (Edge) arg1;
Edge l2 = (Edge) arg2;
if (l1.pos != l2.pos)
return compareInteger(l1.pos, l2.pos);
if (l1.isStart && l2.isStart) {
return compareInteger(l2.height, l1.height);
}
if (!l1.isStart && !l2.isStart) {
return compareInteger(l1.height, l2.height);
}
return l1.isStart ? -1 : 1;
}
int compareInteger(int a, int b) {
return a <= b ? -1 : 1;
}
}
ArrayList<ArrayList<Integer>> output(ArrayList<ArrayList<Integer>> res) {
ArrayList<ArrayList<Integer>> ans = new ArrayList<ArrayList<Integer>>();
if (res.size() > 0) {
int pre = res.get(0).get(0);
int height = res.get(0).get(1);
for (int i = 1; i < res.size(); i++) {
ArrayList<Integer> now = new ArrayList<Integer>();
int id = res.get(i).get(0);
if (height > 0) {
now.add(pre);
now.add(id);
now.add(height);
ans.add(now);
}
pre = id;
height = res.get(i).get(1);
}
}
return ans;
}
public ArrayList<ArrayList<Integer>> buildingOutline(int[][] buildings) {
// write your code here
ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
if (buildings == null || buildings.length == 0
|| buildings[0].length == 0) {
return res;
}
ArrayList<Edge> edges = new ArrayList<Edge>();
for (int[] building : buildings) {
Edge startEdge = new Edge(building[0], building[2], true);
edges.add(startEdge);
Edge endEdge = new Edge(building[1], building[2], false);
edges.add(endEdge);
}
Collections.sort(edges, new EdgeComparator());
HashHeap heap = new HashHeap("max");
ArrayList<Integer> now = null;
for (Edge edge : edges) {
if (edge.isStart) {
if (heap.isEmpty() || edge.height > heap.peek()) {
now = new ArrayList<Integer>(Arrays.asList(edge.pos,
edge.height));
res.add(now);
}
heap.add(edge.height);
} else {
heap.delete(edge.height);
if (heap.isEmpty() || edge.height > heap.peek()) {
if (heap.isEmpty()) {
now = new ArrayList<Integer>(Arrays.asList(edge.pos, 0));
} else {
now = new ArrayList<Integer>(Arrays.asList(edge.pos,
heap.peek()));
}
res.add(now);
}
}
}
return output(res);
}
}