SEGMENTS - Segments
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.
Input
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.
Output
Your output should consist of a single integer, the smallest value of R that is achievable, followed by a newline.
Example
Input: 3 0 1 5 0 2 -2 1 2 7 Output: 2
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 |
Date: | 2008-01-10 |
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 |