2015. Average Height of Buildings in Each Segment

Problem Description

In this problem, we are given an array of buildings, where each building is defined by a starting position (start_i), an ending position (end_i), and its height (height_i). The goal is to describe the street by providing a summary of building heights in the form of segments with average heights. Each segment covers a half-closed interval [left, right) and specifies the average height of all buildings within that interval. The array representing the street should be filled with the fewest possible segments while still accurately portraying the buildings' average heights.

Notice that the average height for a segment is calculated by (integer) dividing the total height of the buildings in the segment by the number of buildings in that segment.

This problem is essentially about merging intervals and calculating the weighted average of heights where buildings overlap.

Intuition

To solve this problem, we can:

1. Utilize a line sweep technique which involves breaking down the buildings' information at certain key points (i.e., the start and end of buildings).
2. Keep a running tally of the height and count of buildings as we "sweep" the street from left to right. This lets us keep track of changes in the average height as we encounter the beginnings and ends of buildings.
3. As we move along the street, we build segments based on the changes in the count and height of buildings. When a new building starts or an existing one ends, it's an opportunity to potentially start a new segment or modify the current one.

Here's more detail on the approach taken in the provided solution:

• The cnt dictionary keeps track of how many buildings are present at each point on the number line.
• The height dictionary keeps track of the cumulative height of the buildings at each point on the number line.
• By iterating over the sorted keys of cnt, we are effectively scanning the number line from left to right.
• Based on the height and count at each position, we calculate the average height for that position and use the information to create or extend the segments in the ans list.
• If a new segment continues directly from the previous one and has the same average height, they are merged; otherwise, a new segment is added to ans.

The crucial insight is that the segments of the street should only change at the points where buildings start or end, resulting in a change of height or count. This approach ensures that we can capture all changes in heights across the street with minimal segments, as required.

Learn more about Greedy, Sorting and Heap (Priority Queue) patterns.

Solution Approach

The solution approach is implemented in Python using the following elements:

• Dictionaries: Two defaultdict(int) instances are created, cnt for maintaining the count of how many buildings overlap at any given point and height for the cumulative height at every point.
• Line Sweep Algorithm: This technique involves iterating over key points along the number line (in this case, the starts and ends of buildings) and updating cnt and height dictionaries.

The algorithm proceeds with these steps:

1. Initialization: For each building, update the cnt and height dictionaries at the start and end points of the building.

   1for s, e, h in buildings:
   2    cnt[s] += 1
   3    cnt[e] -= 1
   4    height[s] += h
   5    height[e] -= h

2. Processing the Sweeping Line: Before we begin processing, we initialize ans (answer list), i (current position), h (current total height), and n (current number of buildings).

   1ans = []
   2i = h = n = 0

   We sort the keys of the cnt dictionary to get the points in increasing order and then iterate through these points. j represents the current key during the iteration. For each such key:

   a. If there's at least one building overlapping (n > 0), we calculate the average height (h // n) and initialize a segment [i, j, avg height].

   b. We check whether we can extend the previous segment in the ans list by comparing the current segment's start point and average height with the previous segment's end point and height. If they match, we extend the end point (ans[-1][1]), otherwise, we append the new segment to ans.

   c. Finally, we update i, h, and n with the current point's details.

   1for j in sorted(cnt.keys()):
   2    if n:  # There's at least one building spanning the current segment.
   3        t = [i, j, h // n]
   4        if ans and ans[-1][1] == i and ans[-1][2] == t[-1]:
   5            ans[-1][1] = j  # Extend the last segment.
   6        else:
   7            ans.append(t)  # Start a new segment.
   8    i = j
   9    h += height[j]
   10    n += cnt[j]

3. Returning the Result: Finally, the ans list containing the minimum number of non-overlapping segments describing the buildings on the street is returned.

The correctness of this approach hinges on the efficiency of the line sweep algorithm, which elegantly handles the merging of intervals and calculation of average heights. The defaultdict(int) data structure is instrumental in maintaining the running count and cumulative height without the need for complex checks or initializations.

Example Walkthrough

Let's go through the solution approach with a small example to illustrate how it works.

Suppose we have the following array of buildings: [(1, 5, 4), (2, 6, 6), (4, 7, 5)]. Each tuple represents a building with a start position, end position, and height. Using the solution approach, we want to create segments that describe the street with the minimum number of segments while accurately portraying the average building heights.

Initialization

First, we initialize our cnt and height dictionaries using the given buildings' details.

1buildings = [(1, 5, 4), (2, 6, 6), (4, 7, 5)]
2cnt = defaultdict(int)
3height = defaultdict(int)
4
5for s, e, h in buildings:
6    cnt[s] += 1
7    cnt[e] -= 1
8    height[s] += h
9    height[e] -= h

After this step, we have:

• cnt: {1: 1, 5: -1, 2: 1, 6: -1, 4: 1, 7: -1}
• height: {1: 4, 5: -4, 2: 6, 6: -6, 4: 5, 7: -5}

These dictionaries indicate how the count and height are changing at each key point.

Processing

We now initialize our variables for processing the sweeping line:

1ans = []
2i = h = n = 0

Next, we sort the keys (points of interest where buildings start and end) of the cnt dictionary and iterate through them, updating i, h, and n and creating segments:

1for j in sorted(cnt.keys()):
2    if n > 0:  # There's at least one building in the current segment
3        avg_height = h // n
4        segment = [i, j, avg_height]
5        if ans and ans[-1][1] == i and ans[-1][2] == avg_height:
6            ans[-1][1] = j  # Extend the last segment
7        else:
8            ans.append(segment)  # Start a new segment
9    i = j
10    h += height[j]
11    n += cnt[j]

Walking through the sorted keys:

1. At point 1, i becomes 1, h becomes 4, and n becomes 1. We don't create a segment since we've just started.
2. At point 2, h becomes 10 (4+6), and n becomes 2 (1+1). The average height is 10//2 = 5. We create a segment [1,2,5].
3. At point 4, h becomes 15 (10+5), and n remains 2. The average height is 15//2 = 7. We create a segment [2,4,7].
4. At point 5, h becomes 11 (15-4), and n decreases to 1 (2-1). The average height is 11. We create a segment [4,5,11].
5. At point 6, h becomes 5 (11-6), and n becomes 0 (1-1). As n is 0, no buildings are spanning this segment, so no need to create a new segment.
6. At point 7, h remains 5 (5-0), and n remains 0 (0+0). Again, as n is 0, no buildings are spanning this segment, so we're done.

Finally, we have our ans: [[1, 2, 5], [2, 4, 7], [4, 5, 11]].

This represents the minimum number of segments that accurately describe the street profile in terms of average building heights.

The above walkthrough demonstrates how the line sweep algorithm effectively processes the building information to create segments. The running tally of height and count is kept, and wall segments are built based on changes in count and height. The key insight is that new segments are only created when needed, which ensures minimal segments are used while still accurately representing the street profile.

Solution Implementation

Time and Space Complexity

Time Complexity

The time complexity of the algorithm is determined by several factors:

1. The loop where each building's start and end points with the corresponding height changes are recorded. This loop runs once for every building, hence it has a time complexity of O(N), where N is the number of buildings.

2. The sorting of the keys of the cnt dictionary. This is the most expensive operation in the algorithm with a time complexity of O(M * log(M)), where M is the number of unique points (start or end of buildings).

3. The second loop, where the average height is computed between points. This loop iterates over every key in the sorted list of keys, which is O(M) operations. Inside this loop, calculations are done in constant time, O(1).

Combining these, the overall time complexity is driven by the sorting step and is O(M * log(M)) where M is the number of unique start or endpoints.

Space Complexity

The space complexity is determined by the auxiliary data structures used:

1. The height and cnt defaultdicts, which will hold as many entries as there are unique start and end points (at most 2N, because there could be a start and end for each building). This gives O(M) space complexity, where M is the number of unique points.

2. The ans list, which in the worst case, if every building has a unique start and end that doesn't overlap with any other, would also be O(M).

Therefore, the overall space complexity is also O(M).

Learn more about how to find time and space complexity quickly using problem constraints.