Binary Search Solution


  • 0
    K

    Use binary search to identify at most two intervals to merge. Move the candidate from left to right to finish the merge accordingly.

    List<Interval> bst;
    public SummaryRanges() {
        bst = new ArrayList<Interval>();
    }
    
    public void addNum(int val) {
        if (bst.size() == 0) {
            bst.add(new Interval(val, val));
            return;
        }
        int left = 0;
        int right = bst.size() - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            Interval cur = bst.get(mid);
            if (val >= cur.start && val <= cur.end) {
                return;
            } else if (val > cur.end) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        int start = right < 0 ? 0 : right;
        int end = left >= bst.size() ? bst.size() - 1 : left;
        if (val < bst.get(start).start - 1) {
            bst.add(start, new Interval(val, val));
        } else if (val == bst.get(start).start - 1) {
            bst.get(start).start--;
        } else if (val == bst.get(start).end + 1 && val < bst.get(end).start - 1) {
            bst.get(start).end++;
        } else if (val == bst.get(start).end + 1 && val == bst.get(end).start - 1) {
            bst.get(start).end = bst.get(end).end;
            bst.remove(end);
        } else if (val > bst.get(start).end + 1 && val < bst.get(end).start - 1) {
            bst.add(end, new Interval(val, val));
        } else if (val == bst.get(end).start - 1) {
            bst.get(end).start--;
        } else if (val == bst.get(end).end + 1) {
            bst.get(end).end++;
        } else {
            bst.add(end + 1, new Interval(val, val));
        }
    }
    
    public List<Interval> getIntervals() {
        return new ArrayList<Interval>(bst);
    }

Log in to reply
 

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