56. Merge Intervals

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

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

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

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

public List<Interval> merge(List<Interval> intervals) {//List尖括号里的元素是Interval
    if (intervals.size() <= 1)
        return intervals;

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

    int i = 0;
    while (i < intervals.size() - 1) {
        Interval current = intervals.get(i);
        Interval next = intervals.get(i + 1);
        if (next.start <= current.end) { //如[1,3],[2,6]的情况
            int max = Math.max(next.end, current.end);
            current.end = max;
            intervals.remove(i + 1); //可以根据索引值remove
        } else { //如[1,3],[4,6]的情况
            i++;
        }
    }
    return intervals;
}