SEGMENTS - Segments

no tags 

There are N horizontal line segments in the plane. The ith segment has some height hi (which may be negative) and runs from x = ai to x = bi (ai < bi). Segments do not contain their endpoints. You must draw a set of vertical lines (note lines and not line segments) so that every given horizontal segment is intersected at least once and at most R times by vertical lines in such a way that R is minimized.


The first line of the input is N (1 ≤ N ≤ 400), the number of horizontal line segments. N lines then follow, where the ith line is "ai bi hi". Each of ai,bi,hi are 32-bit signed integers. Horizontal segments may overlap.


Your output should consist of a single integer, the smallest value of R that is achievable, followed by a newline.


0 1 5
0 2 -2
1 2 7


hide comments
Jelani Nelson (Minilek): 2011-06-15 17:09:50

Yes, that's what it means.

:D: 2011-01-04 14:18:34

It probably means that segment's 'y' coordinate is equal to 'h'

Last edit: 2011-01-04 14:21:17
cjtoribio: 2010-10-30 20:11:59

WHat does the height refers to ?

Added by:Minilek
Time limit:1.524s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:MIT 1st Team Contest 2007