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].

Analysis

  • sort intervals according to start value
  • scan each interval, compare with previous interval, has following conditions: prev: [a,b] cur: [c,d]
    a       b
1.     c d
2.     c    d
3.     c        d
4.          c   d
5.              c    d
  • 情况1&2：do nothing，直接处理下一个interval
  • 情况3&4：merge: 建一个新interval: [a,d], 赋值给prev

  • 情况5：res.add(prev), prev = cur

  • 注意1：只有在发现下个独立的interval时，才把prev push到result中

  • 注意2：所有循环结束后，最后的interval还要push一次

Code

public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals==null || intervals.isEmpty()) return intervals;
        List<Interval> res = new ArrayList<Interval>();
        Collections.sort(intervals, new IntervalComparator());

        Interval prev = intervals.get(0);

        for (Interval cur:intervals){
            if (prev.end < cur.start){
                res.add(prev);
                prev = cur;
            }
            else if (prev.end == cur.start || prev.end < cur.end){
                prev = new Interval(prev.start, cur.end);
            }
        }
        res.add(prev);
        return res;

    }

    private class IntervalComparator implements Comparator<Interval>{
        public int compare(Interval a, Interval b){
            return a.start - b.start;
        }
    }
}

Note

  • 练习comparactor的写法！

Reference