Clean Binary Search Solution


  • 0
    W
    class Solution {
        public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
            
            List<Interval> res = new ArrayList<Interval>();
            int n = intervals.size();
            
            // find the position of the first overlapping element of intervals with newInterval
            int i = findFirstOverlappingPos(intervals, newInterval); 
            // add the elements of intervals that are before the first overlapping position to res
            for(int j = 0; j < i; j++) {
                res.add(intervals.get(j));
            }
            
            // merge overlapped elements of intervals with newInterval
            if(i < n) {
                newInterval.start = Math.min(intervals.get(i).start, newInterval.start);
            }
            // find the position of the last overlapping element of intervals with newInterval
            i = findLastOverlappingPos(intervals, newInterval, i);
            if(i >= 0) {
                newInterval.end = Math.max(intervals.get(i).end, newInterval.end);
            }
            res.add(newInterval);
    
            // add the elements of intervals that are after the first overlapping position to res
            for(i = i + 1; i < n; i++) {
                res.add(intervals.get(i));
            }
            
            return res;
        }
        
        public int findLastOverlappingPos(List<Interval> intervals, Interval newInterval, int l) {
            
            int origL = l;
            
            int r = intervals.size() - 1;
            
            while(l <= r) {
                int m = l + (r - l)/2;
                if(intervals.get(m).start <= newInterval.end) {
                    if(m == (intervals.size() - 1) || 
                       intervals.get(m + 1).start > newInterval.end) {
                       return m;
                    } else {
                        l = m + 1;
                    }
                } else {
                    r = m - 1;
                }
            }
            
            return origL - 1;
        }
        
        public int findFirstOverlappingPos(List<Interval> intervals, Interval newInterval) {
            
            int origR = intervals.size() - 1;
            
            int l = 0;
            int r = origR;
            
            while(l <= r) {
                int m = l + (r - l)/2;
                if(newInterval.start <= intervals.get(m).end) {
                    if(m == 0 || intervals.get(m - 1).end < newInterval.start) {
                        return m;
                    } else {
                        r = m - 1;
                    }
                } else {
                    l = m + 1;
                }
            }
            
            return origR + 1;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.