Java binary search solution


  • 0
    J

    The input intervals are not overlapping, thus the start times and end times are both sorted, then binary search can be applied to locate the overlapping area in O(lgN).

    The best case time complexity is O(lgN), and the worst case is still O(N) for the insertion.

    public class Solution {
        public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
            int startIdx = Collections.binarySearch(intervals, new Interval(0, newInterval.start), new Comparator<Interval>() {
                @Override
                public int compare(Interval o1, Interval o2) {
                    return o1.end - o2.end;
                }
            });
    
            if (startIdx < 0 ) startIdx = -startIdx - 1;
    
            if (startIdx == intervals.size()) {
                intervals.add(newInterval);
                return intervals;
            }
            
            List<Interval> res = new ArrayList<>();
            for (int i = 0; i < startIdx; i++) {
                res.add(intervals.get(i));
            }
            
            int endIdx = Collections.binarySearch(intervals, new Interval(newInterval.end, 0), new Comparator<Interval>() {
                @Override
                public int compare(Interval o1, Interval o2) {
                    return o1.start - o2.start;
                }
            });
            
            if (endIdx < 0) {
                endIdx = -endIdx - 1 - 1;
            }
            
            if (endIdx < startIdx) {
                res.add(newInterval);
            } else {
                int left = Math.min(newInterval.start, intervals.get(startIdx).start);
                int right = Math.max(newInterval.end, intervals.get(endIdx).end);
                res.add(new Interval(left, right));
            }
            for (int i = endIdx + 1; i < intervals.size(); i++) {
                res.add(intervals.get(i));
            }
            return res;
        }
    }
    

  • 0
    J

    The better version

    class Solution {
        public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
            List<Interval> res = new ArrayList<>();
            Interval key = new Interval(newInterval.end, newInterval.start);
            int l = Collections.binarySearch(intervals, key, (a, b) -> a.end - b.end);
            if (l < 0) l = -l - 1;
            int r = Collections.binarySearch(intervals, key, (a, b) -> a.start - b.start);
            if (r < 0) r = -r - 2;
            int i = 0;
            while (i < l) res.add(intervals.get(i++));
            if (l > r) res.add(newInterval);
            else res.add(new Interval(Math.min(newInterval.start, intervals.get(l).start),
                                      Math.max(newInterval.end, intervals.get(r).end)));
            i = r + 1;
            while (i < intervals.size()) res.add(intervals.get(i++));
            return res;
        }
    }
    

Log in to reply
 

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