求个解决数据段交叉的方案

Question

本帖最后由 still_r 于 2009-07-30 13:36:40 编辑

Answer 1

如果都是整型数值：
/*
把start和end之间的数放到一个Set中去(不包括start和end)，如果Set中已有该数值，则有交叉，全部放完不重复，则没有交叉
*/
Set<Integer> set = new HashSet<Integer>();
for(Object o:list){
    for(int i=o.getStart()+1;i<o.getEnd();i++){
        if(set.contains(i)){
            return "有交叉";
        }else{
            set.add(i);
        }
    }
}
return "没有交叉";

Answer 2

更正一下，是包含start不包含end或者包含end不包含start，也就是半开半闭区间
for(int i=o.getStart();i<o.getEnd();i++)

Answer 3

再想一个方案：
先把List给sort一下，按照o.getStart()的正序排列
Collections.sort(list, new Comparator(){
    //比较方法return o1.getStart()-o2.getStart();
});
然后遍历List，看看相临的两个元素A，B，A.getEnd()是否小于等于B.getStart()，如果不是，就是有交叉。这个方案应该比上一个效率差，先排序再遍历，应该没有用散列表装数快。但是如果区间大，这个的优势就大了，比如每个元素的getEnd()-getStart()都特别大，那上面的解决方案就要循环好多次。

Answer 4

区间不是很大 我之前想的是先取出所有Start排序,然后把Start End放到一个Map里 
然后迭代判断o1.getEnd<o2.getStart ```