LeetCode--057--插入区间(java)

给出一个无重叠的，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

示例 1:

输入: intervals = [[1,3],[6,9]], newInterval = [2,5]
输出: [[1,5],[6,9]]

示例 2:

输入: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出: [[1,2],[3,10],[12,16]]
解释: 这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

方法1：在56的基础上，采用先插入再合并的方式，过于繁琐，可以直接看方法2

 1 class Solution {
 2     public int[][] insert(int[][] intervals, int[] newInterval) {
 3         if(intervals.length == 0){
 4             int[][] res = new int[1][2];
 5             res[0] = newInterval;
 6             return res;
 7         }
 8         List<int[]> list = new ArrayList();
 9         int temp = -1;//
10         boolean flag = false;
11         for(int i = 0;i < intervals.length;i++){
12             if(newInterval[0] < intervals[i][0]){
13                 flag=true;//当没有找到要插入的位置，必插入末尾
14                 temp = i;
15                 break;
16             }
17         }
18         for(int i = 0;i < intervals.length;i++){
19             if(i == temp){
20                 list.add(newInterval);
21             }
22             list.add(intervals[i]);
23         }
24         if(!flag){
25             list.add(newInterval);
26         }
27         int[][] in2 = new int[list.size()][2];
28         for(int i = 0;i < list.size();i++){
29             in2[i][0] = list.get(i)[0];
30             in2[i][1] = list.get(i)[1];
31         }
32         return helper(in2);
33         
34     }
35     public int[][] helper(int[][] in2){
36         List<int[]> res = new ArrayList<>();
37         for(int i = 0;i < in2.length-1;i++ ){
38             if(in2[i+1][0] <= in2[i][1]){
39                 in2[i+1][0] = in2[i][0];
40                 in2[i+1][1] = Math.max(in2[i+1][1],in2[i][1]);
41             }else{
42                 res.add(in2[i]);
43             }
44         }
45         res.add(in2[in2.length - 1]);
46         int[][] res_s =new int[res.size()][2];
47         for(int i = 0;i < res.size();i++){
48             res_s[i][0] = res.get(i)[0];
49             res_s[i][1] = res.get(i)[1];
50         }
51         return res_s;
52     }
53 }

方法2：

 1 class Solution {
 2     public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
 3         List<Interval> result = new ArrayList<Interval>();
 4         boolean isAddedNew = false;  
 5         for(Interval curr : intervals){
 6             if(newInterval.start > curr.end){
 7                 //new > curr
 8                 result.add(curr);
 9             }else if (newInterval.end < curr.start){
10                 //curr > new
11                 if(!isAddedNew){
12                     result.add(newInterval);
13                     isAddedNew = true;
14                 }
15                 result.add(curr);
16             }else{
17                 int newStart = curr.start < newInterval.start ?
18                     curr.start : newInterval.start;
19                 int newEnd = curr.end > newInterval.end ?
20                     curr.end : newInterval.end; 
21                 newInterval.start = newStart;
22                 newInterval.end = newEnd;
23             }
24               
25         }
26         if(!isAddedNew){
27             result.add(newInterval);
28         }
29         return result;
30     }
31 }

2019-05-17 18:14:22