[LeetCode 57] Insert Interval (H

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].

Solution

• 注意！！！！ 几个Corner case的处理！！！见代码，容易出错

image.png image.png

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        if (intervals == null || intervals.length == 0 || intervals[0].length == 0) {
            int[][] result = { newInterval };
            return result;
        }
        
        if (newInterval == null || newInterval.length == 0)
            return intervals;
        
        int totalLen = intervals.length;
        int newStart = newInterval[0];
        int newEnd = newInterval[1];
        int index = 0;
        
        List<int[]> result = new ArrayList<> ();
        
        //1. find new start
        while (index < totalLen && newInterval[0] > intervals[index][1]) {
            result.add (intervals[index]);
            index++;
        }
        
        //2. corner base, the new interval is at the end point
        if (index == totalLen) {
            result.add (newInterval);
            return convertToResult (result);
        }
        
        //3. after coner case, get the new start
        newStart = Math.min (newInterval[0], intervals[index][0]);
        
        //4. find the new end
        while (index < totalLen && newInterval[1] >= intervals[index][0]) {
            newEnd = Math.max (newInterval[1], intervals[index][1]);
            index ++;
        }
        result.add (new int[] {newStart, newEnd});
        
        //5. add the following to the result
        while (index < totalLen) {
            result.add (intervals[index]);
            index ++;
        }
        
        return convertToResult (result);
    }
    
    public int[][] convertToResult (List<int[]> list) {
        int[][] result = new int[list.size ()][2];
        
        int index = 0;
        for (int[] entry : list) {
            result[index ++] = entry;
        }
        
        return result;
    }
}