Confusing Algorithm

[Christian Gollwitzer]

Am 22.04.13 16:57, schrieb Oscar Benjamin:
> On 22 April 2013 13:56, Chris Angelico <rosuav at gmail.com> wrote:
>> On Mon, Apr 22, 2013 at 10:39 PM, RBotha <r at ymond.co.za> wrote:

>>> Threads are
>>> straight lines and cannot intersect towers.
>>> Your task is to write a program that finds
>>> the minimal number of threads to cover all
>>> the towers.
 >>>
>>> -Example:
>>> List of towers: 1 5 3 7 2 5 2
>>> Output: 4
 >
>
> I read it differently. I thought the threads would go 1->5->7->5->2.
>


I'd agree with your interpretation. "Threads are straight lines and 
cannot intersect towers" - I read it such that the answer is the "convex 
hull" of the set of points given by the tower height. The convex hull 
can be computed for this 1D problem by initializing with
  line segments between every point and repeatedly pulling up every 
non-convex piece, if I'm not mistaken.

	Christian