# 3ms fastest java solution beat 99.95%

• Each node represents a "key point",use node to devide the scope,
When add a new node, devide a scope into two small scopes.
So every triple can be represented as two nodes.
Then set every influenced scopes to higher height, finally merge the same height scopes;

If you want time in 3ms, you can use new int[2] to replace node.l,and node.h; To let code concise, I use later (4ms).

``````import java.util.*;
//use two-way linked list with first and last node
class Node{
int l, h;                          //int[] a = new int[2]
Node pri, next;

Node (int x, int y)    {    l = x;    h = y;   }

n.next = this;
n.pri = pri;
pri.next = n;
pri = n;
}

public static void del (Node n)    {  //delete Node n
n.pri.next = n.next;
n.next.pri = n.pri;
}
}

public class Solution    {
public List<int[]> getSkyline (int[][] b)    {
List<int[]> list = new ArrayList<int[]> ();
int n = b.length;
if (n == 0)
return list;
Node first = new Node (0, 0);
Node last = new Node (0, 0);
first.next = last;
last.pri = first;

Node p = first.next;

for (int i = 1; i < n; i++)   {
int l = b[i][0];
int r = b[i][1];
int h = b[i][2];

if (h <= p.h && r <= p.next.l)  //no need change
continue;

Node start = p;

int lastH = p.h;
Node nextStart = p;
if (l == p.l)  //no need add new Node
p.h = Math.max (h, p.h);
else    {  //insert the start node
while (p != last && p.l < l)
p = p.next;

lastH = p.pri.h;
nextStart = p.pri;
p.add (new Node (l, Math.max (h, lastH)));
}

while (p != last && p.l < r)     {   //set height of node between l and r
lastH = p.h;
p.h = Math.max (h, p.h);
p = p.next;
}

if (p.l != r)   //insert end node, the height of end node is lastH

Node end = p;

p = start;
while (p.next != end)    {   //merge Nodes of equal height
if (p.h == p.next.h)
Node.del (p.next);
else
p = p.next;
}

p = nextStart;
}

p = first.next;
while (p != last)    {