一条完全笔直的街道由一条数字线表示。街道上有建筑物，由二维整数阵列 buildings 表示，其中 buildings[i] = [starti, endi, heighti]。这意味着在 半封闭的位置[starti，endi] 有一座高度为 heighti 的建筑。
你想用 最少 数量的非重叠 部分 来 描述 街道上建筑物的高度。街道可以用2D整数数组 street 来表示，其中 street[j] = [leftj, rightj, averagej] 描述了道路的 半封闭区域 [leftj, rightj) ，该段中建筑物的 平均 高度为 averagej 。
- 例如，如果
buildings = [[1,5,2],[3,10,4]]，street = [[1,3,2],[3,5,3],[5,10,4]]可以表示街道，因为：<ul> <li>从 1 到 3 ，只有第一栋建筑的平均高度为 <code>2 / 1 = 2</code> 。</li> <li>从 3 到 5 ，第一和第二栋建筑的平均高度均为 <code>（2+4） / 2 = 3 </code>。</li> <li>从 5 到 10 ，只有第二栋建筑的平均高度为 <code>4 / 1 = 4</code> 。</li> </ul> </li>
给定 buildings ，返回如上所述的二维整数矩阵 street （ 不包括 街道上没有建筑物的任何区域）。您可以按 任何顺序 返回数组。
n 个元素的 平均值 是 n 个元素除以 n 的 总和 （整数除法）。
半闭合段 [a, b) 是点 a 和 b 之间的数字线的截面，包括 点 a ，不包括 点 b 。
示例1：
输入: buildings = [[1,4,2],[3,9,4]] 输出: [[1,3,2],[3,4,3],[4,9,4]] 解释: 从 1 到 3 ，只有第一栋建筑的平均高度为 2 / 1 = 2。 从 3 到 4 ，第一和第二栋建筑的平均高度均为（2+4）/ 2 = 3。 从 4 到 9 ，只有第二栋建筑的平均高度为 4 / 1 = 4。
示例 2:
输入: buildings = [[1,3,2],[2,5,3],[2,8,3]] 输出: [[1,3,2],[3,8,3]] 解释: 从 1 到 2 ，只有第一栋建筑的平均高度为 2 / 1 = 2。 从 2 到 3 ，这三座建筑的平均高度均为 （2+3+3） / 3 = 2。 从 3 到 5 ，第二和第三栋楼都在那里，平均高度为 （3+3） / 2 = 3。 从 5 到 8 ，只有最后一栋建筑的平均高度为 3 / 1 = 3。 从 1 到 3 的平均高度是相同的，所以我们可以把它们分成一个部分。 从 3 到 8 的平均高度是相同的，所以我们可以把它们分成一个部分。
示例 3:
输入: buildings = [[1,2,1],[5,6,1]] 输出: [[1,2,1],[5,6,1]] 解释: 从 1 到 2 ，只有第一栋建筑的平均高度为 1 / 1 = 1。 从 2 到 5 ，没有建筑物，因此不包括在输出中。 从 5 到 6 ，只有第二栋建筑的平均高度为 1 / 1 = 1。 我们无法将这些部分组合在一起，因为没有建筑的空白空间将这些部分隔开。
提示:
1 <= buildings.length <= 105buildings[i].length == 30 <= starti < endi <= 1081 <= heighti <= 105
方法一：差分有序哈希表
我们利用差分思想，使用有序哈希表 height 记录每个位置的高度变化，cnt 记录建筑物的数量变化。对有序哈希表求前缀和，即可得到每个位置的高度和建筑物数量。
最后遍历有序哈希表，对于每个位置，如果高度和建筑物数量都不为 0，则说明该位置有建筑物，判断此时的建筑物是否与上个建筑物的平均高度相同，如果相同，则合并，否则加入结果集。
时间复杂度为
class Solution:
def averageHeightOfBuildings(self, buildings: List[List[int]]) -> List[List[int]]:
height = defaultdict(int)
cnt = defaultdict(int)
for s, e, h in buildings:
cnt[s] += 1
cnt[e] -= 1
height[s] += h
height[e] -= h
ans = []
i = h = n = 0
for j in sorted(cnt.keys()):
if n:
t = [i, j, h // n]
if ans and ans[-1][1] == i and ans[-1][2] == t[-1]:
ans[-1][1] = j
else:
ans.append(t)
i = j
h += height[j]
n += cnt[j]
return ansclass Solution {
public int[][] averageHeightOfBuildings(int[][] buildings) {
TreeMap<Integer, Integer> height = new TreeMap<>();
TreeMap<Integer, Integer> cnt = new TreeMap<>();
for (var v : buildings) {
int s = v[0], e = v[1], h = v[2];
cnt.put(s, cnt.getOrDefault(s, 0) + 1);
cnt.put(e, cnt.getOrDefault(e, 0) - 1);
height.put(s, height.getOrDefault(s, 0) + h);
height.put(e, height.getOrDefault(e, 0) - h);
}
int i = 0, h = 0, n = 0;
List<int[]> res = new ArrayList<>();
for (int j : cnt.keySet()) {
if (n > 0) {
int[] t = new int[] {i, j, h / n};
int k = res.size() - 1;
if (k >= 0 && res.get(k)[1] == i && res.get(k)[2] == t[2]) {
res.get(k)[1] = j;
} else {
res.add(t);
}
}
h += height.get(j);
n += cnt.get(j);
i = j;
}
int[][] ans = new int[res.size()][3];
for (i = 0; i < ans.length; ++i) {
ans[i] = res.get(i);
}
return ans;
}
}class Solution {
public:
vector<vector<int>> averageHeightOfBuildings(vector<vector<int>>& buildings) {
map<int, int> height, cnt;
for (auto& v : buildings) {
int s = v[0], e = v[1], h = v[2];
cnt[s]++, cnt[e]--;
height[s] += h, height[e] -= h;
}
vector<vector<int>> ans;
int i = 0, h = 0, n = 0;
for (auto& [j, _] : cnt) {
if (n) {
vector<int> t = {i, j, h / n};
if (ans.size() && ans.back()[1] == i && ans.back()[2] == t[2]) {
ans.back()[1] = j;
} else {
ans.push_back(t);
}
}
i = j;
h += height[j];
n += cnt[j];
}
return ans;
}
};func averageHeightOfBuildings(buildings [][]int) [][]int {
height := make(map[int]int)
cnt := make(map[int]int)
for _, v := range buildings {
s, e, h := v[0], v[1], v[2]
cnt[s]++
cnt[e]--
height[s] += h
height[e] -= h
}
keys := make([]int, len(cnt))
for k := range cnt {
keys = append(keys, k)
}
sort.Ints(keys)
i, h, n := 0, 0, 0
ans := [][]int{}
for _, j := range keys {
if n > 0 {
t := []int{i, j, h / n}
if len(ans) > 0 && ans[len(ans)-1][1] == i && ans[len(ans)-1][2] == t[2] {
ans[len(ans)-1][1] = j
} else {
ans = append(ans, t)
}
}
i = j
h += height[j]
n += cnt[j]
}
return ans
}