## Average Height of Buildings in Each Segment

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

## C++

``````class Solution {
public:
vector<vector<int>> averageHeightOfBuildings(vector<vector<int>>& buildings) {
vector<vector<int>> ans;
vector<pair<int, int>> events;

for (const auto& b : buildings) {
const int start = b[0];
const int end = b[1];
const int height = b[2];
events.emplace_back(start, height);
events.emplace_back(end, -height);
}

sort(begin(events), end(events));

int prev = 0;
int count = 0;
int sumHeight = 0;

for (const auto& [curr, h] : events) {
const int height = abs(h);
if (sumHeight > 0 && curr > prev) {
const int avgHeight = sumHeight / count;
if (!ans.empty() && ans.back()[1] == prev && avgHeight == ans.back()[2])
ans.back()[1] = curr;
else
ans.push_back({prev, curr, avgHeight});
}
sumHeight += h;
count += h > 0 ? 1 : -1;
prev = curr;
}

return ans;
}
};
``````

## JAVA

``````class Solution {
public int[][] averageHeightOfBuildings(int[][] buildings) {
List<int[]> ans = new ArrayList<>();
List<Pair<Integer, Integer>> events = new ArrayList<>();

for (int[] b : buildings) {
final int start = b[0];
final int end = b[1];
final int height = b[2];
}

Collections.sort(events, Comparator.comparing(Pair::getKey));

int prev = 0;
int count = 0;
int sumHeight = 0;

for (var event : events) {
final int curr = event.getKey();
final int h = event.getValue();
final int height = Math.abs(h);
if (sumHeight > 0 && curr > prev) {
final int avgHeight = sumHeight / count;
if (!ans.isEmpty() && ans.get(ans.size() - 1)[1] == prev &&
avgHeight == ans.get(ans.size() - 1)[2])
ans.get(ans.size() - 1)[1] = curr;
else
}
sumHeight += h;
count += h > 0 ? 1 : -1;
prev = curr;
}

return ans.toArray(new int[ans.size()][]);
}
}
``````

## Python

``````class Solution:
def averageHeightOfBuildings(self, buildings: List[List[int]]) -> List[List[int]]:
ans = []
events = []

for start, end, height in buildings:
events.append((start, height))
events.append((end, -height))

prev = 0
count = 0
sumHeight = 0

for curr, h in sorted(events):
height = abs(h)
if sumHeight > 0 and curr > prev:
avgHeight = sumHeight // count
if ans and ans[-1][1] == prev and avgHeight == ans[-1][2]:
ans[-1][1] = curr
else:
ans.append([prev, curr, avgHeight])
sumHeight += h
count += 1 if h > 0 else -1
prev = curr

return ans
``````