Am 22.04.13 16:57, schrieb Oscar Benjamin:
On 22 April 2013 13:56, Chris Angelico <ros...@gmail.com> wrote:
On Mon, Apr 22, 2013 at 10:39 PM, RBotha <r...@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
--
http://mail.python.org/mailman/listinfo/python-list
