CODEWITHSUNDEEP
javaarraysalgorithmdata-structuresbinary-search
Cratylus
Cratylus

Reputation: 54094

Cleaner code when using missing element's position returned by binary search

I am trying to figure out how to code in a clean way the fact that a binary search returns the insertions point for a missing element.

I use this for the algorithmic problem of finding the maximum subset of non-overlapping intervals.

What I do is after sorting the intervals keep each interval the its start time does not overlap with the already selected intervals end time.

Although I could do a linear search, I thought that using a binary search would be better here. Am I right?

So I did the following that although it seems correct, it is error prone and I think there could be better usage of the APIs.

What I am doing is binary search on the end interval and then see if it overlaps with the previous or next (using the insertion point returned by binary search).

Is my logic correct? Also I believe this algorithm can be a good exercise so I am looking a clean java version. 

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;  
}

Upvotes: 2

Views: 166

Answers (2)

Joop Eggen
Joop Eggen

Reputation: 109613

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.

Upvotes: 0

templatetypedef
templatetypedef

Reputation: 373442

The problem of finding the largest nonoverlapping subset of a range of intervals is a classic application of a greedy algorithm. The standard greedy algorithm is the following:

  1. Sort all of the intervals by their end time.
  2. Processing all intervals in order:
    1. Add the interval that ends at the earliest possible time.
    2. Remove all intervals that conflict with that interval.
  3. The resulting set of intervals is a maximum subset of nonoverlapping intervals.

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!

Upvotes: 3

Related Questions