[LeetCode]Insert Interval

题目链接

因为给定的list中的interval都是sorted并且不想交的，我们可以遍历所有list当中的interval：

• 如果不和newInterval相交，直接推入结果集
• 否则，更新新的merge的interval的start和end

newInterval注意插入对应的位置即可。时间复杂度O(n)，代码如下:

既然list是sorted，我们以可以利用这个性质。对于newInterval = [s, e]，我们可以二分找出大于等于s的最小end对应的interval i1和小于等于end的最大start对应的interval i2，这样从i1到i2所有的interval都是应该和newInterval进行merge的。这样的话时间复杂度为O(log n + k)，k为和newInterval相交的interval的数量。注意实现的时候为了找上界和下界的时候共用一套代码，我们找的是下界的下一个数。代码如下：