218. The Skyline Problem

Approach 1: Merge Sort

• Time: $O(n\log n)$
• Space: $O(n)$

C++JavaPython

class Solution {
 public:
  vector<vector<int>> getSkyline(const vector<vector<int>>& buildings) {
    const int n = buildings.size();
    if (n == 0)
      return {};
    if (n == 1) {
      const int left = buildings[0][0];
      const int right = buildings[0][1];
      const int height = buildings[0][2];
      return {{left, height}, {right, 0}};
    }

    const vector<vector<int>> left =
        getSkyline({buildings.begin(), buildings.begin() + n / 2});
    const vector<vector<int>> right =
        getSkyline({buildings.begin() + n / 2, buildings.end()});
    return merge(left, right);
  }

 private:
  vector<vector<int>> merge(const vector<vector<int>>& left,
                            const vector<vector<int>>& right) {
    vector<vector<int>> ans;
    int i = 0;  // left's index
    int j = 0;  // right's index
    int leftY = 0;
    int rightY = 0;

    while (i < left.size() && j < right.size())
      // Choose the point with the smaller x.
      if (left[i][0] < right[j][0]) {
        leftY = left[i][1];  // Update the ongoing `leftY`.
        addPoint(ans, left[i][0], max(left[i++][1], rightY));
      } else {
        rightY = right[j][1];  // Update the ongoing `rightY`.
        addPoint(ans, right[j][0], max(right[j++][1], leftY));
      }

    while (i < left.size())
      addPoint(ans, left[i][0], left[i++][1]);

    while (j < right.size())
      addPoint(ans, right[j][0], right[j++][1]);

    return ans;
  }

  void addPoint(vector<vector<int>>& ans, int x, int y) {
    if (!ans.empty() && ans.back()[0] == x) {
      ans.back()[1] = y;
      return;
    }
    if (!ans.empty() && ans.back()[1] == y)
      return;
    ans.push_back({x, y});
  }
};

class Solution {
  public List<List<Integer>> getSkyline(int[][] buildings) {
    final int n = buildings.length;
    if (n == 0)
      return new ArrayList<>();
    if (n == 1) {
      final int left = buildings[0][0];
      final int right = buildings[0][1];
      final int height = buildings[0][2];
      List<List<Integer>> ans = new ArrayList<>();
      ans.add(new ArrayList<>(Arrays.asList(left, height)));
      ans.add(new ArrayList<>(Arrays.asList(right, 0)));
      return ans;
    }

    List<List<Integer>> leftSkyline = getSkyline(Arrays.copyOfRange(buildings, 0, n / 2));
    List<List<Integer>> rightSkyline = getSkyline(Arrays.copyOfRange(buildings, n / 2, n));
    return merge(leftSkyline, rightSkyline);
  }

  private List<List<Integer>> merge(List<List<Integer>> left, List<List<Integer>> right) {
    List<List<Integer>> ans = new ArrayList<>();
    int i = 0; // left's index
    int j = 0; // right's index
    int leftY = 0;
    int rightY = 0;

    while (i < left.size() && j < right.size())
      // Choose the point with the smaller x.
      if (left.get(i).get(0) < right.get(j).get(0)) {
        leftY = left.get(i).get(1); // Update the ongoing `leftY`.
        addPoint(ans, left.get(i).get(0), Math.max(left.get(i++).get(1), rightY));
      } else {
        rightY = right.get(j).get(1); // Update the ongoing `rightY`.
        addPoint(ans, right.get(j).get(0), Math.max(right.get(j++).get(1), leftY));
      }

    while (i < left.size())
      addPoint(ans, left.get(i).get(0), left.get(i++).get(1));

    while (j < right.size())
      addPoint(ans, right.get(j).get(0), right.get(j++).get(1));

    return ans;
  }

  private void addPoint(List<List<Integer>> ans, int x, int y) {
    if (!ans.isEmpty() && ans.get(ans.size() - 1).get(0) == x) {
      ans.get(ans.size() - 1).set(1, y);
      return;
    }
    if (!ans.isEmpty() && ans.get(ans.size() - 1).get(1) == y)
      return;
    ans.add(new ArrayList<>(Arrays.asList(x, y)));
  }
}

class Solution:
  def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]:
    n = len(buildings)
    if n == 0:
      return []
    if n == 1:
      left, right, height = buildings[0]
      return [[left, height], [right, 0]]

    left = self.getSkyline(buildings[:n // 2])
    right = self.getSkyline(buildings[n // 2:])
    return self._merge(left, right)

  def _merge(self, left: List[List[int]], right: List[List[int]]) -> List[List[int]]:
    ans = []
    i = 0  # left's index
    j = 0  # right's index
    leftY = 0
    rightY = 0

    while i < len(left) and j < len(right):
      # Choose the powith smaller x
      if left[i][0] < right[j][0]:
        leftY = left[i][1]  # Update the ongoing `leftY`.
        self._addPoint(ans, left[i][0], max(left[i][1], rightY))
        i += 1
      else:
        rightY = right[j][1]  # Update the ongoing `rightY`.
        self._addPoint(ans, right[j][0], max(right[j][1], leftY))
        j += 1

    while i < len(left):
      self._addPoint(ans, left[i][0], left[i][1])
      i += 1

    while j < len(right):
      self._addPoint(ans, right[j][0], right[j][1])
      j += 1

    return ans

  def _addPoint(self, ans: List[List[int]], x: int, y: int) -> None:
    if ans and ans[-1][0] == x:
      ans[-1][1] = y
      return
    if ans and ans[-1][1] == y:
      return
    ans.append([x, y])

Approach 2: C++ std::multiset

• Time: $O(n\log n)$
• Space: $O(n)$

C++

class Solution {
 public:
  vector<vector<int>> getSkyline(vector<vector<int>>& buildings) {
    vector<vector<int>> ans;
    vector<vector<int>> events;  // [(Li, Hi) | (Ri, -Hi)]

    for (const vector<int>& b : buildings) {
      events.push_back({b[0], b[2]});
      events.push_back({b[1], -b[2]});  // Minus means leaving.
    }

    ranges::sort(events, [](const vector<int>& a, const vector<int>& b) {
      return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
    });

    for (const vector<int>& event : events) {
      const int x = event[0];
      const int h = abs(event[1]);
      const int isEntering = event[1] > 0;
      if (isEntering) {
        if (h > maxHeight())
          ans.push_back({x, h});
        set.insert(h);
      } else {
        set.erase(set.equal_range(h).first);
        if (h > maxHeight())
          ans.push_back({x, maxHeight()});
      }
    }

    return ans;
  }

 private:
  multiset<int> set;

  int maxHeight() const {
    return set.empty() ? 0 : *set.rbegin();
  }
};