每段建筑物的平均高度

The solution uses a line sweep algorithm combined with differential counting. For each building, start and end positions are marked in a 'diff' dictionary where heights are added at the start and subtracted at the end. Another 'cnts' dictionary tracks how many buildings start or end at each point. By iterating over the sorted keys of these dictionaries, we compute the current total height and count of buildings at each position. This allows us to determine the average height for any segment where it remains constant. The result is appended to the list if the average height changes from the previous segment or a new segment starts.

时间复杂度: O(k log k)

空间复杂度: O(k)

class Solution:
    def averageHeightOfBuildings(self, buildings: List[List[int]]) -> List[List[int]]:
        diff = defaultdict(int)  # Differential map to track height changes at each point
        cnts = defaultdict(int)  # Count map to track number of buildings starting or ending
        for a, b, h in buildings:
            diff[a] += h  # Add height at the start of a building
            diff[b] -= h  # Subtract height at the end of a building
            cnts[a] += 1  # Increment building count at start
            cnts[b] -= 1  # Decrement building count at end
        cur, cnt, last, last_p, ans = 0, 0, None, None, []
        for k in sorted(diff.keys()):
            cur += diff[k]  # Update current total height
            if last:
                if ans and ans[-1][1] == last_p and ans[-1][2] == last // cnt:
                    ans[-1][1] = k  # Extend the last segment if average height is the same
                else:
                    ans.append([last_p, k, last // cnt])  # Start a new segment
            cnt += cnts[k]  # Update the count of overlapping buildings
            last, last_p = cur, k  # Store the current height and position for next iteration
        return ans