Java-LeetCode57. 插入区间-滑动窗口

• 算法
  • 1.把前面不能和新插入区间合并的区间添加到结果：区间的右侧小于新插入区间的左侧
  • 2.把中间可以和新插入区间合并的区间与新插入区间合并
    • 区间的右侧大于等于新插入区间的左侧
    • 区间的左侧小于等于新插入区间的右侧
  • 3.把后面不能和新插入区间合并的区间添加到结果

public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
    ArrayList<Interval> result = new ArrayList<>(10);
    int i = 0;
    while (i < intervals.size() && intervals.get(i).end < newInterval.start) {
        result.add(intervals.get(i++));
    }
    while (i < intervals.size() && intervals.get(i).start <= newInterval.end) {
        newInterval = new Interval(Math.min(intervals.get(i).start, newInterval.start),
                                  Math.max(intervals.get(i).end, newInterval.end));
        i++;
    }
    result.add(newInterval);
    while (i < intervals.size()) {
        result.add(intervals.get(i++));
    }
    return result;
}

public int[][] insert(int[][] intervals, int[] newInterval) {
    ArrayList<int[]> list = new ArrayList<>(10);
    int i = 0;
    while (i < intervals.length && intervals[i][1] < newInterval[0]) {
        list.add(intervals[i++]);
    }
    while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
        newInterval = new int[]{
            Math.min(newInterval[0], intervals[i][0]),
            Math.max(newInterval[1], intervals[i][1])};
        i++;
    }
    list.add(newInterval);
    while (i < intervals.length) {
        list.add(intervals[i++]);
    }
    int[][] result = new int[list.size()][];
    for (int j = 0; j < list.size(); j++) {
        result[j] = list.get(j);
    }
    return result;
}