aboutsummaryrefslogtreecommitdiff
path: root/skyline_problem.cpp
blob: 1828978829500d977fc296b9d362a48bafca706a (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include "leetcode.h"

class Solution {
public:
  vvd(int) getSkyline(vvd(int) & buildings) {
    vvd(int) ans;
    map<int, vector<pair<int, int>>> mvp;
    for (auto &b : buildings) {
      mvp[b[0]].push_back({b[2], 0});
      mvp[b[1]].push_back({b[2], 1});
    }
    multiset<int> m;
    for (auto &[pos, heights] : mvp) {
      for (auto &[height, type] : heights) {
        if (type == 0)
          m.insert(height);
        else
          m.erase(m.find(height));
      }
      int newHeight = m.empty() ? 0 : *m.begin();
      if (!ans.empty() && ans.back()[1] == newHeight)
        continue;
      else
        ans.push_back(vector<int>({pos, newHeight}));
    }
    return ans;
  }
};