Crossing Segments
Time limit1sMemory limit128 MB
Given segments between two parallel lines that are 2-colorable by non-crossing constraint, find the longest chain where consecutive segments cross.
- Level
Medium7 of 10
- Topics
- Dynamic programming, Sorting, Greedy
- Solved
- No attempts yet
Problem
On a two-dimensional coordinate plane, there are two distinct lines L1 and L2 parallel to the x-axis, and several segments connecting the two lines. This problem considers only segment sets satisfying the following conditions.
- No two segment endpoints overlap.
- The segments can be divided into two sets X and Y so that no two segments in the same set cross each other.
The figure below shows one segment set satisfying these conditions. If the segments are divided into X={A, C, E, F, G} (solid lines) and Y={B, D, H} (dotted lines), no two segments inside the same set cross.
From the given set, choose some segments and arrange them as a list (s1, s2, ..., sk). If every adjacent pair si and si+1 (1 <= i < k) crosses, the list is called a segment chain. The length of a segment chain is the number of segments in it.
Given a segment set satisfying the conditions above, find the maximum possible length of a segment chain.
Input
The first line contains the number of segments N. N is between 1 and 100,000, inclusive.
Each of the next N lines contains one segment. A line gives the x-coordinate of the endpoint on L1 followed by the x-coordinate of the endpoint on L2. Every coordinate is an integer between 1 and 1,000,000, inclusive.
Output
Print the maximum possible length of a segment chain on the first line.