540 ms C# solution using linear array implementation of max priority queue

• public IList<int[]> GetSkyline(int[,] buildings) {
IList<int[]> result = new List<int[]>();
if (buildings == null)
return result;
int n = buildings.GetLength(0);
// n should be different from 0 and Second dimension must be 3 (Li, Ri, Hi)
if (n == 0 || buildings.GetLength(1) != 3)
return result;
result.Add(new int[2] { buildings[0, 0], buildings[0, 2] });
// Create a linear array of visited buildings using the tip that said total
// of input buildings won't exceed 10000
// we will use it as a max priority queue
int[] visited = new int[10000]; // initialized to 0
// initialize current building index to  0
int current = 0;
int next = 1;
visited[current] = 1;
int Li, Ri, Hi;
bool noEndedBuildingExist = true;
while (next < n || noEndedBuildingExist)
{
Li = buildings[current, 0];
Ri = buildings[current, 1];
Hi = buildings[current, 2];
if (next < n && Ri >= buildings[next, 0])
{
// compare tops
if (Hi < buildings[next, 2])
{
// we find a new key
if (Li == buildings[next, 0])
result[result.Count-1][1] = buildings[next, 2];
else
result.Add(new int[2] { buildings[next, 0], buildings[next, 2] });
current = next;
}
// Add the new building to the visited ones
visited[next] = 1;
next++;
}
else
{
// Extract the max height from the visited and clean in the same time
// the ones that end to the left of the current building
visited[current] = -1;
int topmostid = -1;
int topmost = -1;
noEndedBuildingExist = false;
int i = 0;
while (i < next)
{
if (visited[i] != -1)
{
if (buildings[i, 1] <= Ri)
{
//ended
visited[i] = -1;
}
else
{
noEndedBuildingExist = true;
if (buildings[i, 2] > topmost)
{
topmost = buildings[i, 2];
topmostid = i;
}
}
}
i++;
}

if (topmostid != -1)
{
if (topmost != Hi)
{
// We find a new key
result.Add(new int[2] { Ri, topmost });
}

current = topmostid;
}
else if(next < n)
{
result.Add(new int[2] { Ri, 0 });
result.Add(new int[2] { buildings[next, 0], buildings[next, 2] });
current = next;
next++;
}
}
}