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


  • 1
    O
    public IList<int[]> GetSkyline(int[,] buildings) {
          IList<int[]> result = new List<int[]>();
          // check bad inputs
          if (buildings == null)
            return result;
          // Read number of buildings
          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;
          // Add left endpoint
          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)
              {
                // Add ground key
                result.Add(new int[2] { Ri, 0 });
                // Add the next key
                result.Add(new int[2] { buildings[next, 0], buildings[next, 2] });
                current = next;
                next++;
              }
            }
          }
    
          // Add right most key
          result.Add(new int[2] { buildings[current, 1], 0 });
          return result;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.