Confusing Algorithm
Christian Gollwitzer
auriocus at gmx.de
Mon Apr 22 16:33:21 EDT 2013
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
More information about the Python-list
mailing list