2ms Java BS solution with comments


  • 1
    A

    Add two sentinels to normalize special case like newInterval is the smallest or greatest Interval.
    Use Binary Search to find the start point and end point of intervals that need to be merged

    public class Solution {
        public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
            if(intervals == null || newInterval == null){
                return new ArrayList<>(intervals);
            }
            List<Interval> result = new ArrayList<>();
            intervals.add(0, new Interval(Integer.MIN_VALUE, Integer.MIN_VALUE)); //Add for using when newInterval is the smallest interval
            intervals.add(new Interval(Integer.MAX_VALUE, Integer.MAX_VALUE)); //Add for using when newInterval is the greatest interval
            int startIndex = binarySearch(intervals, newInterval.start, false);//Start compares to end
            int endIndex = binarySearch(intervals, newInterval.end, true);//End compares to start
            //Insert intervals smaller than newInterval
            for(int i = 1; i < startIndex; ++i){
                result.add(intervals.get(i));
            }
            //endIndex is the first Interval in intervals that has start greater than newInterval.end
            if(endIndex < intervals.size() && intervals.get(endIndex).start == newInterval.end){
                ++endIndex;
            }
            //Merge
            result.add(new Interval(Math.min(intervals.get(startIndex).start, newInterval.start), Math.max(intervals.get(endIndex - 1).end, newInterval.end)));
            //Insert intervals greater than newInterval
            for(int i = endIndex; i < intervals.size() - 1; ++i){
                result.add(intervals.get(i));
            }
            return result;
        }
        
        private int binarySearch(List<Interval> intervals, int val, boolean isStart){
            int low = 0;
            int high = intervals.size();
            while(low < high){
                int middle = low + (high - low) / 2;
                Interval interval = intervals.get(middle);
                int curVal = interval.end;
                if(isStart){
                    curVal = interval.start;
                }
                if(val == curVal){
                    return middle;
                }else if(val > curVal){
                    low = middle + 1;
                }else{
                    high = middle;
                }
            }
            return low;
        }
    }

  • 0
    M

    list.get(index) calls take O(n), so the binary search calls aren't fast at all.
    I think this solution is O(n^2)


  • 0
    A

    Good point. But for ArrayList in Java, it's O(1) for get.


Log in to reply
 

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