Question:

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.

Thinking:

  1. 首先我们将interval的头部排序。
  2. 然后我们遍历整个数组，如果后一个的后部落在缓存的interval之间，我们就尝试更新当前的interval。
  3. 当我们遇到不落在缓存interval之间的值时，我们存储缓存的interval。
  4. 最后一个interval不会遇到break的条件，我们要手动存储。
/**
 * 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; }
 * }
 */
class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        List<Interval> result = new ArrayList<>();
        if(intervals == null || intervals.size() == 0) return result;
        int len = intervals.size();
        intervals.sort((i1, i2)->Integer.compare(i1.start, i2.start));
        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        for(int i = 1; i < len; i++){
            Interval temp = intervals.get(i);
            if(temp.start <= end){
                end = Math.max(temp.end, end);
            }else{
                result.add(new Interval(start, end));
                start = temp.start;
                end = temp.end;
            }
        }
        result.add(new Interval(start, end));
        return result;
    }
}

二刷

完全记得一刷的结果，直接写。

/**
 * 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; }
 * }
 */
class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        int size = intervals.size();
        List<Interval> result = new LinkedList<>();
        if(size == 0) return result;
        int[] up = new int[size];
        for(int i = 0; i < size; i++)
            up[i] = intervals.get(i).start;
        int[] down = new int[size];
        for(int i = 0; i < size; i++)
            down[i] = intervals.get(i).end;
        Arrays.sort(up);
        Arrays.sort(down);
        int begin = up[0];
        for(int i = 1; i < size; i++){
            if(up[i] > down[i - 1]){
                result.add(new Interval(begin, down[i - 1]));
                begin = up[i];
            }
        }
        result.add(new Interval(begin, down[size - 1]));
        return result;
    }
}