2015. Average Height of Buildings in Each Segment
Description
A perfectly straight street is represented by a number line. The street has building(s) on it and is represented by a 2D integer array buildings
, where buildings[i] = [start_{i}, end_{i}, height_{i}]
. This means that there is a building with height_{i}
in the halfclosed segment [start_{i}, end_{i})
.
You want to describe the heights of the buildings on the street with the minimum number of nonoverlapping segments. The street can be represented by the 2D integer array street
where street[j] = [left_{j}, right_{j}, average_{j}]
describes a halfclosed segment [left_{j}, right_{j})
of the road where the average heights of the buildings in the segment is average_{j}
.
 For example, if
buildings = [[1,5,2],[3,10,4]],
the street could be represented bystreet = [[1,3,2],[3,5,3],[5,10,4]]
because:<ul> <li>From 1 to 3, there is only the first building with an average height of <code>2 / 1 = 2</code>.</li> <li>From 3 to 5, both the first and the second building are there with an average height of <code>(2+4) / 2 = 3</code>.</li> <li>From 5 to 10, there is only the second building with an average height of <code>4 / 1 = 4</code>.</li> </ul> </li>
Given buildings
, return the 2D integer array street
as described above (excluding any areas of the street where there are no buldings). You may return the array in any order.
The average of n
elements is the sum of the n
elements divided (integer division) by n
.
A halfclosed segment [a, b)
is the section of the number line between points a
and b
including point a
and not including point b
.
Example 1:
Input: buildings = [[1,4,2],[3,9,4]] Output: [[1,3,2],[3,4,3],[4,9,4]] Explanation: From 1 to 3, there is only the first building with an average height of 2 / 1 = 2. From 3 to 4, both the first and the second building are there with an average height of (2+4) / 2 = 3. From 4 to 9, there is only the second building with an average height of 4 / 1 = 4.
Example 2:
Input: buildings = [[1,3,2],[2,5,3],[2,8,3]] Output: [[1,3,2],[3,8,3]] Explanation: From 1 to 2, there is only the first building with an average height of 2 / 1 = 2. From 2 to 3, all three buildings are there with an average height of (2+3+3) / 3 = 2. From 3 to 5, both the second and the third building are there with an average height of (3+3) / 2 = 3. From 5 to 8, there is only the last building with an average height of 3 / 1 = 3. The average height from 1 to 3 is the same so we can group them into one segment. The average height from 3 to 8 is the same so we can group them into one segment.
Example 3:
Input: buildings = [[1,2,1],[5,6,1]] Output: [[1,2,1],[5,6,1]] Explanation: From 1 to 2, there is only the first building with an average height of 1 / 1 = 1. From 2 to 5, there are no buildings, so it is not included in the output. From 5 to 6, there is only the second building with an average height of 1 / 1 = 1. We cannot group the segments together because an empty space with no buildings seperates the segments.
Constraints:
1 <= buildings.length <= 10^{5}
buildings[i].length == 3
0 <= start_{i} < end_{i} <= 10^{8}
1 <= height_{i} <= 10^{5}
Solutions
Solution 1: Differential Ordered Hash Table
We use the differential idea and an ordered hash table height
to record the height change at each position, and cnt
to record the change in the number of buildings. By calculating the prefix sum of the ordered hash table, we can get the height and the number of buildings at each position.
Finally, we traverse the ordered hash table. For each position, if both the height and the number of buildings are not zero, it means that there is a building at this position. We then check whether the average height of the building at this time is the same as that of the previous building. If it is the same, we merge them; otherwise, we add it to the result set.
The time complexity is $O(n \times \log n)$, and the space complexity is $O(n)$. Here, $n$ is the number of buildings.







