Lexi's Leetcode solutions

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

Posted on: October 19, 2013

这个题是非常常见的面试题,自己试着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之类的,就更长了。回头看看能不能写简洁点。

Advertisements
Tags: , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: