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

我的解法：用一个带最大堆的扫描线遍历数组，每出现一个拐点则记录一次区间。新加入一个元素后若堆顶元素和之前不同，则表明出现拐点。

1. 首先处理数组中元素。将每一个点用一个point来保存，保存time（开始写错了，应该是位置，但是要改的太多了），flag（起点为1，终点为0），height。用一个HashMap来记录每一对终点和起点（终点为key，起点为value）。

2. 将所有point保存在一个list中并排序，首先根据时间从小到大排序，若时间相等则根据flag排序（先起点后终点），若flag也相等则根据height排序（若同为起点则从大到小排序，若同为终点则从小到大排序）。这样可以避免重复解。

3. 再构建一个最大堆，用于记录加入的元素的最大值。

4. 开始遍历list中每个point，起点元素加入堆，终点元素删去堆中对应的起点元素。

5. 当遇到一个起点元素时，先记录加入前堆顶元素，然后将该起点元素加入，再看加入后堆顶元素，1）若没有变化，则继续下一个point；2）若有变化，则说明出现拐点，将之前堆顶元素时间作为起点，当前堆顶元素时间作为终点，之前堆顶元素高度作为高度。注意：就算堆顶元素变化，但是如果之前堆顶元素和当前堆顶元素时间相同，说明是在这个时间连续有几个起点被加入，宽度为0，不能算一个区间。

6. 当遇到一个终点元素时，将其对应的起点元素从堆中删除。若此时堆为空，则和5中一样记录一个区间，并继续下一个point。若堆不为空，则需要看此时堆顶元素是否改变。若不变则继续，否则说明出现“拐点”。此处“拐点”要分两种情况讨论： 1）若新的堆顶元素高度和之前堆顶元素高度相同，则说明相同高度的两段区间有重叠，题目要求若发生这种情况要合并这两段区间，所以我们要保留之前的堆顶元素（两段同高度相同重叠区间的最左边），删去新的堆顶元素（即代替原堆顶元素被删除，因为每遇到一个终点必须删去一个起点），具体做法可以是先删去新堆顶元素，再加入原堆顶元素，或者直接将新堆顶元素时间改为原堆顶元素时间。 2）若新堆顶和原堆顶元素高度不同，则像5中那样记录一个区间，但是要将现在的堆顶元素时间改为遇到的终点元素的时间。

7. 遍历完整个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);
  }

}