57. Insert Interval.md

57. Insert Interval

Question:

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Thinking:

1. 首先构造一个头数组和尾数组，分别将newInterval按序插入。
2. 此时我们就可以参考56. Merge Intervals，去除重复的interval.

/**
 * 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> insert(List<Interval> intervals, Interval newInterval) {
        List<Interval> result = new ArrayList<>();
        int start = newInterval.start;
        int end = newInterval.end;
        int len = intervals.size();
        int[] starts = new int[len + 1];
        int[] ends = new int[len + 1];
        int i = 0;
        for(; i < len; i++)
            starts[i] = intervals.get(i).start;
        starts[i] = start;
        Arrays.sort(starts);
        for(i = 0; i < len; i++)
            ends[i] = intervals.get(i).end;
        ends[i] = end;
        Arrays.sort(ends);
        int saveStart = starts[0];
        int saveEnd = ends[0];
        for(i = 1; i < len + 1; i++){
            if(saveEnd >= starts[i])
                saveEnd = Math.max(saveEnd, ends[i]);
            else{
                result.add(new Interval(saveStart, saveEnd));
                saveStart = starts[i];
                saveEnd = ends[i];
            }
        }
        result.add(new Interval(saveStart, saveEnd));
        return result;
    }
}

二刷

完全和上一道题一样的做法， 只是要注意数组的size增加了。

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

Third Time

• Method 1: Array + Sort

   class Solution {
   	public int[][] insert(int[][] intervals, int[] newInterval) {
   		int len = intervals.length;
   		int[] starts = new int[len + 1];
   		int[] ends = new int[len + 1];
   		// Currently the starts and ends are sorted and non-overlap
   		for(int i = 0; i < len; i++){
   			starts[i] = intervals[i][0];
   			ends[i] = intervals[i][1];
   		}
   		starts[len] = newInterval[0]; 
   		ends[len] = newInterval[1];
   		Arrays.sort(starts);
   		Arrays.sort(ends);
   		List<int[]> temp = new ArrayList<>();
   		int start = starts[0];
   		for(int i = 1; i <= len; i++){
   			if(starts[i] > ends[i - 1]){
   				temp.add(new int[]{start, ends[i - 1]});
   				start = starts[i];
   			}
   		}
   		temp.add(new int[]{start, ends[len]});
   		int[][] res = new int[temp.size()][2];
   		for(int i = 0; i < temp.size(); i++){
   			res[i] = temp.get(i);
   		}
   		return res;
   	}
   }