We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Average Height of Buildings in Each Segment

Number: 2142

Difficulty: Medium

Paid? Yes

Companies: Microsoft

Problem Description

Given a list of buildings represented as [start, end, height] describing a half-closed interval [start, end) and a constant height for that building, partition the street (i.e., the number line) into the minimum number of non-overlapping segments such that in each segment the average height of all active buildings (using integer division) is constant. Segments where there are no buildings are omitted, and contiguous segments with the same average height must be merged.

Key Insights

  • Use a sweep line algorithm to handle events (building starts and ends) along the number line.
  • Treat each building’s start as an addition event and its end as a removal event.
  • For events at the same coordinate, process removal events before addition events to correctly implement the half-open interval [start, end).
  • Maintain variables to track the current sum of heights and the count of active buildings.
  • Compute the average using integer division (sum // count) whenever there is a change in the set of active buildings.
  • Merge contiguous segments if they have the same computed average height.

Space and Time Complexity

Time Complexity: O(n log n) due to sorting the events, where n is the number of buildings.
Space Complexity: O(n) for storing the events.

Solution

We use a sweep line algorithm for this problem. First, we convert each building into two events: one for the start (addition) event and one for the end (removal) event. We then sort these events by coordinate, ensuring that removals come before additions when they share the same coordinate. As we sweep through the events along the number line, we update the active set of buildings by maintaining the total height and the count of buildings. On any change of coordinate, if there is at least one active building, we compute the current average using integer division and record the segment. Finally, we merge adjacent segments with the same average value to achieve the minimum segmentation required.

Code Solutions

# Python solution

def averageHeightSegments(buildings):
    events = []
    # Create events: (coordinate, type, height)
    # type: -1 for removal, +1 for addition to ensure removals processed first at the same coordinate
    for start, end, height in buildings:
        events.append((start, +1, height))
        events.append((end, -1, height))
    
    # Sort events by coordinate and then by type (removal before addition)
    events.sort(key=lambda x: (x[0], x[1]))
    
    result = []
    current_sum = 0
    current_count = 0
    prev_coordinate = None

    # Process each event
    i = 0
    while i < len(events):
        coordinate = events[i][0]
        # If we have moved to a new coordinate and there are active buildings, record a segment
        if prev_coordinate is not None and coordinate != prev_coordinate and current_count > 0:
            avg = current_sum // current_count
            # Merge the last segment if its average is same as current
            if result and result[-1][2] == avg and result[-1][1] == prev_coordinate:
                result[-1][1] = coordinate
            else:
                result.append([prev_coordinate, coordinate, avg])
        # Process all events at this coordinate
        while i < len(events) and events[i][0] == coordinate:
            _, event_type, height = events[i]
            # Process removal event: subtract from current_sum and decrement count
            if event_type == -1:
                current_sum -= height
                current_count -= 1
            else:
                # Process addition event: add to current_sum and increment count
                current_sum += height
                current_count += 1
            i += 1
        # Update the previous coordinate pointer
        prev_coordinate = coordinate
    return result

# Example usage:
buildings = [[1,4,2],[3,9,4]]
print(averageHeightSegments(buildings))  # Expected: [[1,3,2],[3,4,3],[4,9,4]]
← Back to All Questions