Problem Description
This is a problem to find the appropriate order to reconstruct buildings given the heights of buildings on a long street. Each building is represented by an array of heights, and based on that array, we need to determine the order in which those buildings were erected.
For example, if the heights of the buildings are [3, 1, 4, 1, 5], the order in which they should be built, starting from the tallest building, is as follows.
- Building 1: Height 5
- Building 2: Height 4
- Building 3: Height 3
- Building 4: Height 1
- Building 5: Height 1
Input
An integer array heights will be given. Each element represents the height of a building.
Output
You must output the order in which the buildings should be erected in the form of a list of indices.
Example
Input: heights = [3, 1, 4, 1, 5] Output: [4, 3, 0, 1, 2]
Solution Process
To solve this problem, we need to sort the building indices based on their height information. Below are the steps of the solution process.
Step 1: Input
First, we need to take the heights of the given buildings as input. We can declare a heights array or receive input through a function.
Step 2: Create Height-Index Pairs
Create a list of pairs containing each building’s height and index. In Python, we can easily create a list that includes indices using the enumerate function.
building_pairs = list(enumerate(heights))Step 3: Sorting
Now we need to sort the list of buildings based on height. We can sort the list in descending order of heights using the sorted function. In this case, we specify the height as the key argument for sorting.
sorted_buildings = sorted(building_pairs, key=lambda x: x[1], reverse=True)Step 4: Extracting Results
From the sorted list, extract the indices to create a result list. This can be easily done using list comprehension.
result = [index for index, height in sorted_buildings]Step 5: Output the Result
Finally, we need to print the order of the buildings. All the related codes can be integrated and provided in the form of a function.
Final Code
def building_order(heights):
building_pairs = list(enumerate(heights))
sorted_buildings = sorted(building_pairs, key=lambda x: x[1], reverse=True)
result = [index for index, height in sorted_buildings]
return result
# Example usage
heights = [3, 1, 4, 1, 5]
print(building_order(heights))
Result Check
Running the code above will output [4, 3, 0, 1, 2], which represents the correct order based on the provided building heights.
Result Analysis
The indices were paired and sorted according to the heights in the array, thereby effectively deriving the order of building construction.