[leetcode] Insert Interval | 排好序的interval list，插入一个新区间

Posted by: lexigrey on: October 19, 2013

• In: leetcode
• Leave a Comment

这个题是非常常见的面试题，自己试着implement了两种方法，一个O(logn)，一个O(n)，但是写起来都不是很简洁。

O(n)的方法：binary search by start，找到一个要insert的位置(start1<start<=start2)，取那个大的start2（因为它肯定会被start给replace掉，start1则不一定）。插入这个新interval，然后从头到尾检查overlap（两个参数无论谁前谁后都能用这个helper查出来），有就merge，不断吞噬overlap的。代码写起来有点长，不过思路非常清晰，不用考虑任何边界条件（什么a.start <= b.end…那些都烦死人了）。interview的时候可以写这种，因为binary search那段可能都不让你写。

还有一个trick是用iterator可以直接修改正在iterate的list，不会报modification exception，第一次用，很方便。

public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
    int insertPosition = insertByStart(intervals, newInterval.start, 0, intervals.size() - 1);
    intervals.add(insertPosition, newInterval);
    Iterator<Interval> it = intervals.iterator();
    Interval prev = it.next();
    while (it.hasNext()) {
        Interval curr = it.next();
        if (overlap(prev, curr)) {
            prev.start = Math.min(prev.start, curr.start);
            prev.end = Math.max(prev.end, curr.end);
            it.remove();
        } else {
            prev = curr;
        }
    }
    return intervals;
}
private int insertByStart(ArrayList<Interval> intervals, int x, int p, int q) {
    if (p > q)
        return p;
    int mid = (p + q) / 2;
    if (intervals.get(mid).start < x) {
        return insertByStart(intervals, x, mid + 1, q);
    } else {
        return insertByStart(intervals, x, p, mid - 1);
    }
}
private boolean overlap(Interval a, Interval b) {
    return within(a.start, b) || within(a.end, b) || within(b.start, a) || within(b.end, a);
}
private boolean within(int v, Interval b) {
    return v >= b.start && v <= b.end;
}

另一种方法是binary search，找出要start属于的位置，end属于的位置。但是很不好写，需要判断那些this.start >=that.end之类的，就更长了。回头看看能不能写简洁点。

Tags: array, hard, math