Problem Description
Explanation:
To solve this problem, we can use binary search to find the maximum possible height of the tallest building. We need to consider the restrictions and compute the maximum height that can be achieved. The main idea is to iterate through the restrictions and calculate the maximum allowed height at each position based on the adjacent restrictions.
- Sort the restrictions by their position.
- Initialize two arrays
leftandrightto store the maximum height achievable from the left and right side respectively. - For each restriction, calculate the maximum height that can be achieved at that position based on the adjacent restrictions.
- The maximum possible height at a position
iis the minimum of the heights calculated from the left and right side. - Use binary search to find the maximum possible height of the tallest building.
:
Solutions
class Solution {
public int maxBuilding(int n, int[][] restrictions) {
Arrays.sort(restrictions, (a, b) -> a[0] - b[0]);
int m = restrictions.length;
int[] left = new int[m + 1];
int[] right = new int[m + 1];
left[0] = 0;
right[0] = 0;
for (int i = 0; i < m; i++) {
left[i + 1] = Math.min(restrictions[i][0] - 1, restrictions[i][1]);
}
for (int i = m - 1; i >= 0; i--) {
right[i] = Math.min(restrictions[i][0] - 1, restrictions[i][1]);
}
for (int i = 1; i <= m; i++) {
left[i] = Math.min(left[i], left[i - 1] + restrictions[i - 1][0] - restrictions[i - 2][0]);
}
for (int i = 1; i < m; i++) {
right[i] = Math.min(right[i], right[i + 1] + restrictions[i][0] - restrictions[i - 1][0]);
}
int maxHeight = 0;
for (int i = 0; i < m; i++) {
int leftHeight = left[i];
int rightHeight = right[i];
int distance = restrictions[i][0] - restrictions[i - 1][0];
int totalHeight = restrictions[i][1] + Math.max(leftHeight, rightHeight) + (distance - Math.abs(leftHeight - rightHeight)) / 2;
maxHeight = Math.max(maxHeight, totalHeight);
}
int lastPosition = restrictions[m - 1][0];
int lastHeight = restrictions[m - 1][1];
maxHeight = Math.max(maxHeight, lastHeight + n - lastPosition);
return maxHeight;
}
}Loading editor...