https://community.topcoder.com/stat?c=problem_statement&pm=1918&rd=5006
http://www.cnblogs.com/lautsie/p/3256269.html
http://stackoverflow.com/questions/11248764/how-is-the-flowergarden-pr0blem-on-topcoder-a-dp-one
http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=tccc04_online_rd_1
private Flower[] flowers;
public int[] getOrdering(int[] height, int[] bloom, int[] wilt) {
flowers = new Flower[height.length];
for (int i = 0; i < height.length; i++) {
flowers[i] = new Flower(height[i], bloom[i], wilt[i]);
}
Arrays.sort(flowers, new Comparator<Flower>() {
public int compare(Flower f1, Flower f2) {
if (livesOverlap(f1, f2)) {
f1.born = f2.born = Math.min(f1.born, f2.born);
f1.die = f2.die = Math.max(f1.die, f2.die);
return f1.height - f2.height;
} else return (f2.height - f1.height);
}
});
int[] order = new int[flowers.length];
for (int i = 0; i < flowers.length; i++) {
order[i] = flowers[i].height;
}
return order;
}
private boolean livesOverlap(Flower f1, Flower f2) {
return Math.min(f1.die, f2.die) >= Math.max(f1.born, f2.born);
}
private static class Flower {
int height;
int born;
int die;
private Flower(int height, int born, int die) {
this.height = height;
this.born = born;
this.die = die;
}
}
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
找了半天网上思路，是个三层的循环，n^3。
2.基本思路就是先找到在第一个位置的花。这样就双层遍历，找到所有和其他不冲突的花中最高的一个，然后放到结果的首位。然后去掉此花，继续使用此方法对余下花朵。
3.要注意的是首先不能直接排序，比如a和b，b和c有冲突，但a和c不一定有冲突。
4.判断两段是否重叠的最简单式子是!(a.start > b.end || b.start > a.end)
2.基本思路就是先找到在第一个位置的花。这样就双层遍历，找到所有和其他不冲突的花中最高的一个，然后放到结果的首位。然后去掉此花，继续使用此方法对余下花朵。
3.要注意的是首先不能直接排序，比如a和b，b和c有冲突，但a和c不一定有冲突。
4.判断两段是否重叠的最简单式子是!(a.start > b.end || b.start > a.end)
思路来自：http://apps.topcoder.com/forums/?module=Thread&threadID=655393&start=0&mc=6#1766488 里面还有一个图形的方法
public int[] getOrdering(int[] height, int[] bloom, int[] wilt) { int len = height.length; if (len == 0) return height; // assert length != 0 int order[] = new int[len]; boolean used[] = new boolean[len]; for (int i = 0; i < len; i++) { int mxH = 0; int pos = -1; for (int j = 0; j < len; j++) { if (used[j]) continue; boolean found = true; for (int k = 0; k < len; k++) { if (used[k]) continue; boolean blocking = !(bloom[j] > wilt[k] || bloom [k] > wilt[j]); if (height[j] > height[k] && blocking) { found = false; break; } } if (found) { if (height[j] > mxH) { mxH = height[j]; pos = j; } } } order[i] = height[pos]; used[pos] = true; } return order; }http://stackoverflow.com/questions/11248764/how-is-the-flowergarden-pr0blem-on-topcoder-a-dp-one
http://www.topcoder.com/tc?module=Static&d1=match_editorials&d2=tccc04_online_rd_1
This problem is pretty simple to solve -- as long as you are solving the correct problem! A subtle ambiguity in the problem statement made the problem seem more difficult than it really was. For those of you who missed the broadcast, the problem statement will be updated soon to make the statement clear for the practice room. In short, you are looking to make flowers which are closest to the front of the garden as tall as possible, not trying to put the tallest flower as close as possible.
Sorting the flowers in this garden isn't as simple as writing a sort comparison routine, because you can't always tell what the ordering will be with just two elements. In reality, the ordering is easy to compute if you think about the flowers one at a time. The first step is to determine which flowers cannot go in front of other flowers. This is done by comparing the bloom date of each flower with the bloom and wilt date of every other flower. If two flowers conflict, then the bloom date of one will lay between the bloom and wilt date of the other. Within a conflict, the larger of the two cannot be placed in front of the other, or blockage will occur.
When figuring out which type of flower to place next, you can only place flowers that can go in front of all the flowers left to place. Of those, you should place the type which is tallest. For the next type, the flower type just placed no longer can be blocked, so it could allow more flower types to be placed. Because there can be no circular dependencies, this algorithm can be used to place the entire garden.
https://github.com/irpap/TopCoder/blob/master/FlowerGarden/src/FlowerGarden.javaprivate Flower[] flowers;
public int[] getOrdering(int[] height, int[] bloom, int[] wilt) {
flowers = new Flower[height.length];
for (int i = 0; i < height.length; i++) {
flowers[i] = new Flower(height[i], bloom[i], wilt[i]);
}
Arrays.sort(flowers, new Comparator<Flower>() {
public int compare(Flower f1, Flower f2) {
if (livesOverlap(f1, f2)) {
f1.born = f2.born = Math.min(f1.born, f2.born);
f1.die = f2.die = Math.max(f1.die, f2.die);
return f1.height - f2.height;
} else return (f2.height - f1.height);
}
});
int[] order = new int[flowers.length];
for (int i = 0; i < flowers.length; i++) {
order[i] = flowers[i].height;
}
return order;
}
private boolean livesOverlap(Flower f1, Flower f2) {
return Math.min(f1.die, f2.die) >= Math.max(f1.born, f2.born);
}
private static class Flower {
int height;
int born;
int die;
private Flower(int height, int born, int die) {
this.height = height;
this.born = born;
this.die = die;
}
}
