本文共 2175 字，大约阅读时间需要 7 分钟。

题目

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

我的想法

没啥想法，感觉重合的情况有些复杂

仿照答案写的。因为需要对数组进行插入操作，所以首先考虑用ArrayList，新的input虽然是数组，但是仍然可以采用List<int[]> list = new ArrayList<>(); 来动态操作数组

public int[][] insert(int[][] intervals, int[] newInterval) {
           List
   
     list = new ArrayList<>();        int i = 0;        int start = newInterval[0];        int end = newInterval[1];        while (i < intervals.length && intervals[i][1] < start) {
               list.add(intervals[i++]);        }        while (i < intervals.length && intervals[i][0] <= end) {
               start = Math.min(start, intervals[i][0]);            end = Math.max(end, intervals[i][1]);            i++;        }        int[] interval = {
   start,end};        list.add(interval);        while (i < intervals.length) list.add(intervals[i++]);        int[][] res = new int[list.size()][2];        for(int k = 0; k < list.size(); k++){
               int[] arr = list.get(k);            res[k][0] = arr[0];            res[k][1] = arr[1];        }        return res;    }
   

解答

leetcode solution 1: old input

1. 在newInterval start前end的
2. 在newInterval end后start的

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

转载地址：http://dbqvb.baihongyu.com/