56. Merge Intervals.md

56. Merge Intervals

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;
    }
}

Amazon session

• Method 1: Sort

   class Solution {
   	public int[][] merge(int[][] intervals) {
   		if(intervals == null || intervals.length <= 1) return intervals;
   		Arrays.sort(intervals, (a, b)->{
   			return a[0] == b[0] ? a[1] - b[1]: a[0] - b[0];
   		});
   		int len = intervals.length;
   		List<int[]> result = new ArrayList<>();
   		int start = intervals[0][0];
   		int end = intervals[0][1];
   		for(int i = 1; i < len; i++){
   			if(intervals[i][0] <= end){
   				end = Math.max(intervals[i][1],end);
   			}else{
   				result.add(new int[]{start, end});
   				start = intervals[i][0];
   				end = Math.max(intervals[i][1],end);
   			}
   		}
   		result.add(new int[]{start, end});
   		return result.toArray(new int[result.size()][2]);
   	}
   }

Reference

1. Algorithm | Interval Schedule