A safe place to build a house
Background
You want to build a house in a rainy region with a hilly landscape. In this region, all slopes are subject to landslides and all valleys are subject to flood, so you need to find the top of any hill to build.
Imagine that you can divide the terrain into N land lots. You can get the altitude for each of these lots by using a satellite. A lot at the top of a hill is one whose altitude is higher than the neighboring lots.
In the example below, lot 0 has an altitude of 3, lot 1 has an altitude of 6, etc. Lot 1 is at the top of a hill, because it’s higher than lots 0 and 2. Lot N is also at the top, because it’s higher than ltt N-3 (its only neighboring lot).
Altitude
5 |
4 | x
5 | x x x
2 | x
1 | x
----------------------- Land lot
0 3 2 3 ... N-3 N
Assume that two adjacent lots do not have the same altitude.
The problem Getting data from the satellite takes a lot of time and is expensive, so find an algorithm that is able to find any lot at the top of a hill while using the satellite efficiently.