Show problems as
Classic problem #1840HardArrayMathSorting

Maximum Building Height

Real-world version: Tallest Silo in the Stacking Row
Tracked in this browser only
Read Maximum Building Height on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A grain yard has silos silos standing in a straight row, numbered 1 through silos. Each silo is built up from identical rings, so its size is a whole number of rings, never negative. Silo 1 is the loading silo and holds exactly 0 rings.

A shared walkway runs along the row, and it can only span one ring of difference, so two silos standing next to each other differ by at most one ring.

Some silos sit under overhead cables. Each entry caps[i] = [pos, limit] says silo pos may hold at most limit rings. Every listed pos is different, and a silo with no entry has no limit of its own beyond the walkway rule.

The yard wants one silo as tall as the rules allow. Return the largest number of rings a single silo can hold in any arrangement that obeys every rule above.

Examples

Example 1

Input
silos = 6, caps = [[6, 2]]
Output
3

The row 0, 1, 2, 3, 3, 2 obeys every rule: silo 1 holds 0 rings, neighbours never differ by more than one ring, and silo 6 stays within its limit of 2. Its tallest silo holds 3 rings.

Example 2

Input
silos = 10, caps = [[10, 0], [5, 8]]
Output
4

The row 0, 1, 2, 3, 4, 3, 2, 2, 1, 0 keeps silo 5 under its limit of 8 and silo 10 at its limit of 0, and its tallest silo holds 4 rings.

Example 3

Input
silos = 5, caps = []
Output
4

With no cables the row 0, 1, 2, 3, 4 is allowed, and its tallest silo holds 4 rings.

Constraints

  • 2 <= silos <= 10^9
  • 0 <= caps.length <= min(silos - 1, 10^5)
  • caps[i].length == 2
  • 2 <= caps[i][0] <= silos
  • The values caps[i][0] are all different.
  • 0 <= caps[i][1] <= 10^9
  • The answer is at most silos - 1, so it stays below 10^9.

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def tallest_silo(silos: int, caps: list[list[int]]) -> int:
Java
public int tallestSilo(int silos, int[][] caps)

More on the same topics