56. Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
思路: 先sort排序,再merge。 Merge的过程就是找当前interval的start如果小于或者等于之前interval的end,那么之前的interval就可以extend当前interval,preInterval.end=curInterval.end; 否则的话,就不能merge;为了进行遍历,我们用两个变量preStart,preEnd来保存之前的interval的信息,遍历的时候我们用cur.start跟preEnd进行比较 1) cur.start>=preEnd, merge,然后更新preStart,preEnd 2)preEnd取Max(cur.end, preEnd).
复杂度: time O(nlogn), space O(n)

/**
 * 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> merge(List<Interval> intervals) {
        List<Interval> res = new ArrayList<>();
        if (intervals == null || intervals.size() == 0) return res;
        if (intervals.size() == 1) return intervals;

        Collections.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval i1, Interval i2) {
                if (i1.start == i2.start) {
                    return i2.end - i1.end;
                } 
                return i1.start - i2.start;
            }
        });

        int preStart = intervals.get(0).start;
        int preEnd = intervals.get(0).end;

        for(int i = 1; i < intervals.size(); i++) {
            Interval cur = intervals.get(i);
            if (cur.start > preEnd) {
                res.add(new Interval(preStart, preEnd));
                preStart = cur.start;
                preEnd = cur.end;
            } else {
                preEnd = Math.max(preEnd, cur.end);
            }
        }
        res.add(new Interval(preStart, preEnd));
        return res;
    }
}
Advertisements

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s