1. 原题链接

2. 题目要求

该题与上一题的区别在于，插入一个新的interval对象，将此对象与所给列表里的Interval对象进行合并。

3. 解题思路

首先遍历Interval对象列表，找到插入位置。将插入位置之前的列表中的Interval对象直接加入结果列表。

然后查找所要插入Interval对象的end属性在列表中的位置。

最后将列表中剩余的Interval对象全部加入结果列表。

4. 代码实现

import java.util.LinkedList;import java.util.List;public class InsertIntervals57 {    public static void main(String[] args) {        Interval in1 = new Interval(1, 2);        Interval in2 = new Interval(3, 5);        Interval in3 = new Interval(6, 7);        Interval in4 = new Interval(8, 10);        Interval in5 = new Interval(12, 16);        Interval in = new Interval(4, 9);        List
     
       ls = new LinkedList
      
       ();        ls.add(in1);        ls.add(in2);        ls.add(in3);        ls.add(in4);        ls.add(in5);        for (Interval i : insert(ls, in))            System.out.println(i.start + " " + i.end);    }    public static List
       
         insert(List
        
          intervals, Interval interval) {        List
         
           res = new LinkedList
          
           (); if (intervals.size() == 0) { res.add(interval); return res; } int i = 0; // 将插入位置之前的元素直接加入结果列表中 while (i < intervals.size() && intervals.get(i).end < interval.start) { res.add(intervals.get(i++)); } // 将所要插入的元素与李彪中的对象进行合并 while (i < intervals.size() && intervals.get(i).start <= interval.end) { interval = new Interval( // we could mutate newInterval here also Math.min(interval.start, intervals.get(i).start), Math.max(interval.end, intervals.get(i).end)); i++; } res.add(interval); // 将剩余的所有元素插入结果列表 while (i < intervals.size()) res.add(intervals.get(i++)); return res; }}