java - 使用二分搜索返回的缺失元素位置时的代码更清晰

Question

我试图弄清楚如何以一种干净的方式进行编码，即二分搜索返回缺失元素的插入点。

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

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

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

所以我做了以下操作，虽然看起来是正确的，但很容易出错，我认为可以更好地使用 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;  
}  

Answer 1

寻找一系列区间的最大非重叠子集的问题是 greedy algorithm 的一个经典应用。 。标准的贪心算法如下:

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

从该算法中应该可以清楚地看出，结果集不包含任何重叠间隔，因为算法的每个步骤都会从将来的考虑中删除所有冲突的间隔。

要查看这是最佳解决方案，您可以使用交换参数来表明没有更好的解决方案。您可以在网上查找详细信息，例如in this set of lecture slides .

希望这有帮助!