Average Height of Buildings in Each Segment

Links to Other Solutions

Problem Description

Welcome to the whimsical world of urban planning, where buildings are like children—some are tall, some are short, and they all want to stand out! The problem at hand is to calculate the average height of buildings in each segment of a city. Imagine a city where buildings pop up like mushrooms after rain, and you need to figure out how tall they are on average in different segments.

You are given a list of buildings, each defined by a start point, an end point, and a height. Your task is to find the average height of buildings in each segment where they overlap. So, if you’ve ever wondered how tall your neighbor’s house is compared to yours, this problem is for you!

Code Solution


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, height in sorted(events):
            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 += height
            count += 1 if height > 0 else -1
            prev = curr

        return ans

Approach

The approach taken in this solution is quite elegant. It involves creating a list of events for each building, marking the start and end points along with their heights. By sorting these events, we can traverse through them and maintain a running total of the heights and their counts. Whenever we encounter a new segment (where the current position is greater than the previous), we calculate the average height and store it in our results.

Time and Space Complexity

Time Complexity: O(N log N), where N is the number of buildings. This is due to the sorting of events.

Space Complexity: O(N), as we store the events and the results.

Real-World Example

Imagine you are a city planner trying to figure out how to maximize sunlight in a park surrounded by buildings. By calculating the average height of buildings in each segment, you can determine which areas are overshadowed and need shorter buildings or more trees. This problem is not just about numbers; it’s about creating a livable environment!