guruqu
BAN USERDynamic Programming. Should be O(n^3) time and O(n^2) space.
State would be two dimensional DP(i,j) standing for maximum segments that can fit into [i,j].
State transition would be base on first segment of optimal solution in range [i,j].
DP(i,j) = argmax_k (1+DP(k_start+1,k_end-1)+DP(k_end+1,j)), seg k that fits in [i,j].
Mind some boundary cases, and hopefully this is clear enough for you guys.
public static class Point {
public double x, y;
public Point(double x, double y) {
this.x = x;
this.y = y;
}
}
public static int MaxSetDP(int[] segs) {
int n = segs.length;
if (n == 0)
return 0;
int[][] dp = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = i; j >= 0; j--) {
int max = 0;
// For segment [i,j] search through all segments that fits in [i,j]
// assuming it's the first segment for opitmum solution
// Find the segments with largest fit
for (int k = j; k < i; k++) {
if (segs[k] >= 0 && segs[k] <= i) {
int cmax = 1;
if (segs[k] - k > 2) {
cmax += dp[k + 1][segs[k] - 1];
}
if (segs[k] < i) {
cmax += dp[segs[k] + 1][i];
}
max = Math.max(max, cmax);
}
}
dp[j][i] = max;
}
}
return dp[0][n - 1];
}
public static class AngleCompare implements Comparator<Point> {
@Override
public int compare(Point o1, Point o2) {
if (o1.x >= 0 && o2.x >= 0) {
return o1.y < o2.y ? -1 : 1;
} else if (o1.x < 0 && o2.x < 0) {
return o2.y < o1.y ? -1 : 1;
} else {
return o1.x < o2.x ? 1 : -1;
}
}
}
public static int MaxSetPoints(Point[][] segments){
Point[] array = new Point[segments.length * 2];
for (int i = 0; i < segments.length; i++) {
array[i * 2] = segments[i][0];
array[i * 2 + 1] = segments[i][1];
}
HashMap<Point, Integer> order = new HashMap<>();
// Sort points by clock-wise order
// Comparison function not using any sin,cos function which is slow
Arrays.sort(array, new AngleCompare());
for (int i = 0; i < array.length; i++) {
order.put(array[i], i);
}
// Flatten into integer array,
// Non zero elements indicates start point, value is the end point
// Negative value is an end point
int[] segs = new int[segments.length * 2];
for (Point[] si : segments) {
segs[order.get(si[0])] = order.get(si[1]);
segs[order.get(si[1])] = -1;
}
return MaxSetDP(segs);
}
Isn't this what Starbucks just said? Reducing Max independent set to this?
- guruqu November 04, 2014