2

我试图弄清楚如何以干净的方式编码二进制搜索返回缺失元素的插入点这一事实。

我用它来解决寻找非重叠间隔的最大子集的算法问题。

我所做的是在对间隔进行排序后保持每个间隔的开始时间不与已经选择的间隔结束时间重叠。

虽然我可以进行线性搜索，但我认为在这里使用二进制搜索会更好。我对吗？

所以我做了以下事情，虽然它看起来是正确的，但它很容易出错，我认为可以更好地使用 API。

我正在做的是在结束间隔上进行二进制搜索，然后查看它是否与前一个或下一个重叠（使用二进制搜索返回的插入点）。

我的逻辑正确吗？另外我相信这个算法可以是一个很好的练习，所以我正在寻找一个干净的 java 版本。 

private boolean nonOverlapping(Pair interval, SortedSet<Pair> selectedIntervals) {  
    if(selectedIntervals.isEmpty())  
        return true;  
    if(selectedIntervals.contains(interval)){  
        return true;  
    }       
    Pair[] sortedSelections = selectedIntervals.toArray(new Pair[0]);  
    int pos = Arrays.binarySearch(sortedSelections, interval, new Comparator<Pair>() {  

        @Override  
        public int compare(Pair o1, Pair o2) {  
            return o1.getStart() - o2.getEnd();   
        }  
    });  
    pos = (-pos) -1;  
    if(pos == sortedSelections.length){  
        if(sortedSelections[pos - 1].getEnd() < interval.getStart()){  
            return true;  
        }  

    }           
    else if(sortedSelections[pos].getEnd() > interval.getStart()){  
        if(pos + 1 < sortedSelections.length){  
            if(sortedSelections[pos + 1].getEnd() < interval.getStart()){  
                return false;   
            }   
        }  
        if(pos - 1 >= 0){  
            if(sortedSelections[pos - 1].getEnd() < interval.getStart()){  
                return false;  
            }  
        }  
        return true;  
    }  


    return false;  
}
4

2 回答 2

3

寻找区间范围内最大的非重叠子集的问题是贪心算法的经典应用。标准贪心算法如下：

  1. 按结束时间对所有间隔进行排序。
  2. 按顺序处理所有间隔：
    1. 添加在尽可能早的时间结束的间隔。
    2. 删除与该间隔冲突的所有间隔。
  3. 生成的间隔集是非重叠间隔的最大子集。

It should be clear from this algorithm that the resulting set does not contain any overlapping intervals, since each step of the algorithm removes all conflicting intervals from future consideration.

To see that this is optimal, you can use an exchange argument to show that there cannot be a better solution. You can find details online, such as in this set of lecture slides.

Hope this helps!

于 2013-01-17T20:37:04.503 回答
0

The "normal" comparison for overlapping cannot be utilized?

    @Override  
    public int compare(Pair o1, Pair o2) {  
        return o1.getStart() > o2.getEnd() ? 1
            : o1.getEnd() < o2.getStart() ? -1
            : 0;   
    }

Explanation

This covers

[o2s .. o2e]  [o1s .. o1e]     o1s > o2e  when after  ->  +1
[o1s .. o1e]  [o2s .. o2e]     o1e < o2s  when before ->  -1
otherwise overlap  ->  0

One needs all 4 variables: o1s, o1e, o2s, o2e.

于 2013-01-17T21:36:08.543 回答