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

题意：合并区间，将给的区间合并成最终版本就可以。

思路：按照区间左侧从小到大排序，如果左侧相同，按照右侧从小到大排序。从左向右，两两合并即可。

public static List<Interval> merge(List<Interval> intervals) {

        List<Interval> result = new ArrayList<Interval>();

        if (intervals == null || intervals.size() == 0) {
            return result;
        }

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

        Interval pre = intervals.get(0);
        for (int i = 0; i < intervals.size(); i++) {
            Interval curr = intervals.get(i);
            if (curr.start > pre.end) {
                result.add(pre);
                pre = curr;
            } else {
                Interval meraged = new Interval(pre.start, Math.max(pre.end, curr.end));
                pre = meraged;
            }
        }
        return result;

    }