Dummy and verbose solution. But I think this problem throws out some technics to learn


  • 0
    R

    So my solution is find the first interval with end less or equal than new one's start and last interval with start greater or equal than new one's end. I know this is pretty dummy comparing to those top posts, but I think it combines 2 binary search questions: find first and find last. Best running time would be better than linear search method, which is O(logn) while the worst is still O(N). Good for practicing.

    /**
     * Definition for an interval.
     * public class Interval {
     *     int start;
     *     int end;
     *     Interval() { start = 0; end = 0; }
     *     Interval(int s, int e) { start = s; end = e; }
     * }
     */
    public class Solution {
        public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
            List<Interval> result = new ArrayList<>();
            if (intervals == null || intervals.isEmpty()) {
                result.add(newInterval);
                return result;
            }
            int start = findLastLessEqualThanStart(intervals, newInterval);
            int end = findFirstGreaterEqualThanEnd(intervals, newInterval);
            if (start == -1 && end == -1) {
                result.add(newInterval);
            } else if (start == -1) {
                if (intervals.get(end).start <= newInterval.end) {
                    newInterval.end = intervals.get(end).end;
                    end += 1;
                }
                result.add(newInterval);
                for (int i = end; i < intervals.size(); i++) {
                    result.add(intervals.get(i));
                }
            } else if (end == -1) {
                if (intervals.get(start).end >= newInterval.start) {
                    newInterval.start = intervals.get(start).start;
                    start -= 1;
                }
                for (int i = 0; i <= start; i++) {
                    result.add(intervals.get(i));
                }
                result.add(newInterval);
            } else {
                if (intervals.get(start).end >= newInterval.start) {
                    newInterval.start = intervals.get(start).start;
                    start -= 1;
                }
                if (intervals.get(end).start <= newInterval.end) {
                    newInterval.end = intervals.get(end).end;
                    end += 1;
                }
                for (int i = 0; i <= start; i++) {
                    result.add(intervals.get(i));
                }
                result.add(newInterval);
                for (int i = end; i < intervals.size(); i++) {
                    result.add(intervals.get(i));
                }
            }
            return result;
        }
        
        int findLastLessEqualThanStart(List<Interval> intervals, Interval newInterval) {
            int i = 0, j = intervals.size() - 1;
            while (i + 1 < j) {
                int mid = i + (j - i) / 2;
                int midStart = intervals.get(mid).start;
                if (newInterval.start > midStart) {
                    i = mid;
                } else if (newInterval.start < midStart) {
                    j = mid - 1;
                } else {
                    return mid;
                }
            }
            if (intervals.get(j).start <= newInterval.start) {
                return j;
            } else if (intervals.get(i).start <= newInterval.start) {
                return i;
            } else {
                return -1;
            }
        }
        
        int findFirstGreaterEqualThanEnd(List<Interval> intervals, Interval newInterval) {
            int i = 0, j = intervals.size() - 1;
            while (i + 1 < j) {
                int mid = i + (j - i) / 2;
                int midEnd = intervals.get(mid).end;
                if (newInterval.end < midEnd) {
                    j = mid;
                } else if (newInterval.end > midEnd) {
                    i = mid + 1;
                } else {
                    return mid;
                }
            }
            if (intervals.get(i).end >= newInterval.end) {
                return i;
            } else if (intervals.get(j).end >= newInterval.end) {
                return j;
            } else {
                return -1;
            }
        }
    }
    

Log in to reply
 

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