Question
There is a pile of n wooden sticks. The length and weight of each stick are known in advance. The sticks are to be processed by a woodworking machine in one by one fashion. It needs some time, called setup time, for the machine to prepare processing a stick. The setup times are associated with cleaning operations and changing tools and shapes in the machine. The setup times of the woodworking machine are given as follows:
- The setup time for the first wooden stick is 1 minute.
- Right after processing a stick of length l and weight w , the machine will need no setup time for a stick of length l' and weight w' if l <=l' and w <=w' .
Otherwise, it will need 1 minute for setup.
You are to find the minimum setup time to process a given pile of n
wooden sticks. For example, if you have
five sticks whose pairs of length and weight are (4,9), (5,2), (2,1), (3,5),
and (1,4) then the minimum setup
time should be 2 minutes since there is a sequence of pairs (1,4),
(3,5), (4,9), (2,1), (5,2).
Input
The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case consists of two lines: The first line has an integer n, 1<=n<=5000, that represents the number of wooden sticks in the test case, and the second line contains 2n positive integers l_{1}, w_{1}, l_{2}, w_{2}, …, l_{n}, w_{n}, each of magnitude at most 10000, where l_{i} and w_{i} are the length and weight of the i th wooden stick, respectively. The 2n integers are delimited by one or more spaces.
Output
The output should contain the minimum setup time in minutes, one per line.
Sample Input
3 5 4 9 5 2 2 1 3 5 1 4 3 2 2 1 1 2 2 3 1 3 2 2 3 1
Sample Output
2 1 3
Analysis
This question is a little similar to [CC150v5] 9.10 Stack Up the Boxes, yet different.
Solution
Solution quoted from 脚本百事通:
按长度从小到大排序, 若长度相同, 则按重量从小到大排序(先按重量再按长度也行)
然后, 我们针对当前木棍, 与剩下的木棍比较, 满足 w1 <= w2 && l1 <= l2 的, 就更新一下当前棍, 并标记~
当所有木棍都被编组后 输出到底设置了几次~
Code
The following Java code is written by me
public int count(Pair[] points) {
Arrays.sort(points, new PointComparator());
// now the array is sorted with Point.x
int total = 0;
int p = 0;
int len = points.length;
while (p < len) {
// find the next non-null point
while (p < len && points[p] == null) {
p++;
}
if (p == len) {
break;
}
// use points[p] as the first elements in the queue
Pair temp = copy(points[p]);
points[p] = null;
total++;
// then mark all elements that follow points[p]
for (int k = p + 1; k < len; k++) {
if (points[k] == null || points[k].y < temp.y) {
continue;
}
temp = copy(points[k]);
points[k] = null;
}
p++;
}
return total;
}
Pair copy(Pair p) {
Pair newP = new Pair(p.x, p.y);
return newP;
}
class PointComparator implements Comparator<Pair> {
@Override
public int compare(Pair p1, Pair p2) {
return p1.x - p2.x;
}
}