Merge Intervals-LeetCode#56

766. Merge Intervals

Given a collection of intervals, merge all overlapping intervals.
Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considerred overlapping.

合并间隔，给定间隔的集合，合并所有重叠的间隔。
间隔类 Interval.class 如下

class Interval {
    int start;
    int end;
    Interval() {
        start = 0;
        end = 0;
    }
    Interval(int s, int e) {
        start = s;
        end = e;
    }
}

思路: 比较前一位间隔的end与后一位间隔的start，如果start大于前一位的end，则是一个新的间隔没有重叠。

public class MergeIntervals {
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals.size() <= 1){
            return intervals;
        }
        Collections.sort(intervals, new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                return Integer.compare(o1.start, o2.start);
            }
        });
        List<Interval> res = new ArrayList<>();
        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        for (Interval interval : intervals){
            if (interval.start <= end){
                end = Math.max(end, interval.end);
            }else {
                res.add(new Interval(start, end));
                start = interval.start;
                end = interval.end;
            }
        }
        res.add(new Interval(start, end));
        return res;
    }
    public static void main(String[] args) {
        MergeIntervals mergeIntervals = new MergeIntervals();
        List<Interval> intervals = new ArrayList<>();
        Interval i1 = new Interval();
        Interval i2 = new Interval();
        Interval i3 = new Interval();
        Interval i4 = new Interval();
        i1.start = 1;
        i1.end = 3;
        i2.start = 2;
        i2.end = 6;
        i3.start = 8;
        i3.end = 10;
        i4.start = 15;
        i4.end = 18;
        intervals.add(i1);
        intervals.add(i2);
        intervals.add(i3);
        intervals.add(i4);
        mergeIntervals.merge(intervals);
    }
}