houses houses is being built in a row, numbered from 1 to houses. Each house is a non-negative whole number of floors tall, and the zoning rules say:
- house 1 must have height 0;
- neighbouring houses differ in height by at most 1;
- some houses have a cap: a pair caps[i] = [p, h] means house p is at most h tall.
Each house appears in caps at most once, and house 1 never does. Return the greatest height the tallest house on the street can reach.houses=7, caps=[[3, 0], [6, 4]] → 4
Heights 0, 1, 0, 1, 2, 3, 4: house 3 is flat and house 6 stays within 4. The tallest is house 7 with 4 floors.
houses=4, caps=[] → 3
No caps, so heights grow by one: 0, 1, 2, 3.
houses=9, caps=[[5, 1], [9, 0]] → 2
For example 0, 1, 2, 1, 1, 2, 2, 1, 0: no house can rise above 2 on either side of house 5.
p are distincthouses=7, caps=[[3, 0], [6, 4]]
4
Run checks the first 3 tests in your browser. Submit checks all 90 tests on the server, hidden ones included.