
ZOJ Problem Set  2956
There are a number of disjoint vertical line segments in the plane. We say that two vertical line segments are horizontally visible if they can be connected by a horizontal line segment. A clique is a set of vertical line segments, in which any two segments in the set are horizontally visible. Your job is to find the largest clique. Read the description of a set of vertical segments, you are to compute the largest clique of the segments and output the number of the segments in the largest clique. Input The first line of the input contains exactly one positive integer T equal to the number of data sets. T data sets follow. The first line of each data set contains exactly one integer N (1 <= N <= 4000) equal to the number of vertical line segments. Each of the following N lines consists of exactly 3 nonnegative integers separated by single spaces: X_{i} , Y_{i1} , Y_{i2}  its xcoordinate, ycoordinate of the beginning of a segment and ycoordinate of its end. The coordinates satisfy 0 <= Y_{i1} < Y_{i2} <= 10000. The segments are disjoint. Output The output should consist of exactly N lines, one line for each data set. Each line should contain exactly one integer that is the number of the segments in the largest clique. Sample Input
1 3 1 0 1 2 1 2 3 0 3 Sample Output
3 Author: PENG, Peng Source: ZOJ Monthly, May 2008 