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 1:


Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]


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

Difficulty: interview

Starter code:

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        

Solutions:
# Definition for an interval.
 # class Interval:
 #     def __init__(self, s=0, e=0):
 #         self.start = s
 #         self.end = e
 
 class Solution:
     def insert(self, intervals, newInterval):
         """
         :type intervals: List[Interval]
         :type newInterval: Interval
         :rtype: List[Interval]
         """
         # my no6, 56ms, beats 100%
         if len(intervals)==0:
             return [newInterval]
         start = 0; end = 0
         foundl = foundr = -1
         for i, n in enumerate(intervals):
             if foundl==-1 and newInterval.start<=n.end:
                 foundl = 1
                 start = i
                 break
             else:
                 continue
         for i, n in enumerate(intervals[::-1]):
             if foundr==-1 and newInterval.end>=n.start:
                 foundr = 1
                 end = len(intervals)-1-i
                 break
             else:
                 continue
         print(start, end,foundl,foundr)
         if foundl==1 and foundr==1:
             if start<=end:
                 s = min(intervals[start].start, newInterval.start)
                 e = max(intervals[end].end, newInterval.end)
                 return intervals[:start]+[Interval(s,e)]+intervals[end+1:]
             else:
                 return intervals[:start]+[newInterval]+intervals[end+1:]
         elif foundl==1:
             return [newInterval]+intervals
         else:
             return intervals+[newInterval]
         
         # others'
         # s, e = newInterval.start, newInterval.end
         # left, right = [], []
         # for i in intervals:
         #     if i.end < s:
         #         left += i,
         #     elif i.start > e:
         #         right += i,
         #     else:
         #         s = min(s, i.start)
         #         e = max(e, i.end)
         # return left + [Interval(s, e)] + right
 
             
         

# Definition for an interval.
 # class Interval:
 #     def __init__(self, s=0, e=0):
 #         self.start = s
 #         self.end = e
 
 class Solution:
     def insert(self, intervals, newInterval):
         """
         :type intervals: List[Interval]
         :type newInterval: Interval
         :rtype: List[Interval]
         """
         if intervals == []:
             return [newInterval]
         
         index = 0
         while index < len(intervals):
             if newInterval.start < intervals[index].start:
                 break
             index += 1
         del_index = 0
         insert_index = 0
         if index == 0:
             s = newInterval.start
             e = newInterval.end
             insert_index = index 
         else:
             if newInterval.start <= intervals[index - 1].end:
                 s = intervals[index - 1].start
                 e = max(intervals[index - 1].end, newInterval.end)
                 insert_index = index - 1
                 del_index += 1
             else:
                 s = newInterval.start
                 e = newInterval.end
                 insert_index = index
             
         while index < len(intervals):
             if intervals[index].start <= e:
                 e = max(e, intervals[index].end)
                 del_index += 1
                 index += 1
             else:
                 break
         i = 0
         while i < del_index:
             intervals.pop(insert_index)
             i += 1
         intervals.insert(insert_index, Interval(s,e))
         return intervals
                     
                 
         

# Definition for an interval.
 # class Interval:
 #     def __init__(self, s=0, e=0):
 #         self.start = s
 #         self.end = e
 
 import operator
 class Solution:
     def insert(self, intervals, newInterval):
         """
         :type intervals: List[Interval]
         :type newInterval: Interval
         :rtype: List[Interval]
         """
         #Leetcode 第56题的思路
         returnedList = []
         if(len(intervals) == 0):
             returnedList.append(newInterval)
             return returnedList
 
         p = 1       #判断是循环结束跳出循环，还是newInterval.end < intervals[i].start跳出循环，前者不进行拼接
         for i in range(len(intervals)):
             if(intervals[i].end < newInterval.start):
                 returnedList.append(intervals[i])
             elif(intervals[i].end == newInterval.start):
                 newInterval.start = intervals[i].start
             elif(newInterval.start < intervals[i].end and newInterval.end > intervals[i].start): #相交
                 newInterval.start = min(newInterval.start, intervals[i].start)
                 newInterval.end = max(newInterval.end, intervals[i].end)
             elif(newInterval.end == intervals[i].start):
                 newInterval.end = intervals[i].end
             elif(newInterval.end < intervals[i].start):
                 p = 0
                 break
 
 
         returnedList.append(newInterval)
         if(p == 0):
             returnedList.extend(intervals[i:])
         return returnedList

# Definition for an interval.
 # class Interval:
 #     def __init__(self, s=0, e=0):
 #         self.start = s
 #         self.end = e
 
 class Solution:
     def insert(self, intervals, newInterval):
         """
         :type intervals: List[Interval]
         :type newInterval: Interval
         :rtype: List[Interval]
         """
         
         ans = []
         
         # some boundary conditions
         if intervals == []:
             return [newInterval]
         elif newInterval.end < intervals[0].start:
             return [newInterval] + intervals
         elif newInterval.start > intervals[-1].end:
             return intervals + [newInterval]
         
         new_start = newInterval.start
         new_end = newInterval.end
         
         for i in range(0, len(intervals)):
             if intervals[i].end < new_start: # intertval[i].start <= interval[i].end < new_start
                 ans.append(intervals[i])
             elif i and (intervals[i-1].end < new_start) and (new_end < intervals[i].start): # i >= 1
                 ans.append(newInterval)
                 for j in range(i, len(intervals)):
                     ans.append(intervals[j])
                 return ans
             else:
                 merge_start = min(intervals[i].start, new_start)
                 merge_end = max(intervals[i].end, new_end)
                 break
                 
         #print("i:", i)
         #print(merge_start, merge_end)
         
         notStop = 1
         for ii in range(i+1, len(intervals)):
             if intervals[ii].start > merge_end: # merge_start <= merge_end < intervals[ii].start
                 notStop = 0
                 break
         
         if notStop: # after traversing remaining intervals, merge_intvl overlaps the last (i.e. entire remaining) intervals
             merge_end = max(intervals[-1].end, merge_end) # or index ii
             ans.append(Interval(merge_start, merge_end))
             return ans
 
         merge_end = max(intervals[ii-1].end, merge_end)
         #print("ii:", ii)
         #print(merge_start, merge_end)
         ans.append(Interval(merge_start, merge_end))
         
         
         for iii in range(ii, len(intervals)):
             ans.append(intervals[iii])
         
         return ans

# Definition for an interval.
 # class Interval:
 #     def __init__(self, s=0, e=0):
 #         self.start = s
 #         self.end = e
 
 class Solution:
     def insert(self, intervals, newInterval):
         """
         :type intervals: List[Interval]
         :type newInterval: Interval
         :rtype: List[Interval]
         """
         start, end = newInterval.start, newInterval.end
         left = [i for i in intervals if start > i.end]
         right = [i for i in intervals if end < i.start]
         if left + right != intervals:
             start = min(start, intervals[len(left)].start)
             end = max(end, intervals[~len(right)].end)
         return left + [Interval(start, end)] + right
             
                 
             

# Definition for an interval.
 # class Interval:
 #     def __init__(self, s=0, e=0):
 #         self.start = s
 #         self.end = e
 
 class Solution:
     def insert(self, intervals, newInterval):
         """
         :type intervals: List[Interval]
         :type newInterval: Interval
         :rtype: List[Interval]
         """
         s, e = newInterval.start, newInterval.end
         left, right = [], []
         for i in intervals:
             if i.end < s:
                 left += i,
             elif i.start > e:
                 right += i,
             else:
                 s = min(s, i.start)
                 e = max(e, i.end)
         return left + [Interval(s, e)] + right

# Definition for an interval.
 # class Interval:
 #     def __init__(self, s=0, e=0):
 #         self.start = s
 #         self.end = e
 
 class Solution:
     def insert(self, intervals, newInterval):
         """
         :type intervals: List[Interval]
         :type newInterval: Interval
         :rtype: List[Interval]
         """
         start, end = newInterval.start, newInterval.end
         left, right = [], []
         for i in intervals:
             if i.end < start:
                 left.append(i)
             elif i.start > end:
                 right.append(i)
             else:
                 start = min(start, i.start)
                 end = max(end,i.end)
         return left + [Interval(start, end)] + right

# Definition for an interval.
 # class Interval:
 #     def __init__(self, s=0, e=0):
 #         self.start = s
 #         self.end = e
 
 class Solution:
     def insert(self, intervals, newInterval):
         """
         :type intervals: List[Interval]
         :type newInterval: Interval
         :rtype: List[Interval]
         """
         left = 0
         right = len(intervals) - 1
         tar = newInterval.start
         while True:
             if left > right:
                 break
             mid = (left + right) // 2
             value = intervals[mid].start
             if value == tar:
                 left = mid
                 break
             elif value > tar:
                 right = mid - 1
             else:
                 left = mid + 1
         intervals.insert(left, newInterval)
         ret = []
         tmp = intervals[0]
         ret.append(tmp)
         it = iter(intervals)
         next(it)
         for i in it:
             if i.start <= ret[-1].end:
                 prev = ret.pop()
                 ret.append(Interval(prev.start, max(i.end, prev.end)))
             else:
                 ret.append(i)
         return ret
             

# Definition for an interval.
 # class Interval:
 #     def __init__(self, s=0, e=0):
 #         self.start = s
 #         self.end = e
 
 class Solution:
     def insert(self, intervals, newInterval):
         """
         :type intervals: List[Interval]
         :type newInterval: Interval
         :rtype: List[Interval]
         """
         if not intervals:
             return [newInterval]
         v = []
         a =newInterval.start
         b =newInterval.end
         flag =0
         s=a
         e=b
         for i in intervals:
             if i.start<=a<=i.end:
                 s = i.start
             if i.start<=b<=i.end:
                 e = i.end
                 v.append(Interval(s,e))
                 flag =1
             if not flag and i.start >b:
                 v.append(Interval(s,e))
                 flag =1
             if i.end<a or i.start>b:
                 v.append(i)
         if not flag:
             v.append(Interval(s,e))
         return v

# Definition for an interval.
 # class Interval:
 #     def __init__(self, s=0, e=0):
 #         self.start = s
 #         self.end = e
 
 class Solution:
     def insert(self, intervals, newInterval):
         """
         :type intervals: List[Interval]
         :type newInterval: Interval
         :rtype: List[Interval]
         """
         res = []
         for interval in intervals:
             if self.merge(interval, newInterval):
                 newInterval = Interval(min(interval.start, newInterval.start), max(interval.end, newInterval.end))
             else:
                 if newInterval != None and newInterval.end < interval.start:
                     res.append(newInterval)
                     newInterval = None
                 res.append(interval)
         if newInterval != None:
             res.append(newInterval)
         return res
     
     def merge(self, a, b):
         if b is None or a.start > b.end or a.end < b.start:
             return False
         return True

class Solution:
     def insert(self, intervals, newInterval):
         start = len(intervals)
         for i in range(len(intervals)):
             if newInterval.start<intervals[i].start:
                 start = min(start, i)
             if not (newInterval.start > intervals[i].end or newInterval.end < intervals[i].start):
                 newInterval = Interval(min(newInterval.start, intervals[i].start), max(newInterval.end, intervals[i].end))
                 start, intervals[i] = min(i,start), []
         intervals = [ele for ele in intervals if ele!=[]]
         intervals.insert(start,newInterval)
         return intervals

# Definition for an interval.
 # class Interval:
 #     def __init__(self, s=0, e=0):
 #         self.start = s
 #         self.end = e
 
 class Solution:
     def insert(self, intervals, newInterval):
         """
         :type intervals: List[Interval]
         :type newInterval: Interval
         :rtype: List[Interval]
         """
         intervals.append(newInterval)
         if len(intervals) <= 1:
           return intervals
         
         intervals.sort(key=lambda x:x.start)
         
         i = 0
         while i < len(intervals) - 1:
           left = intervals[i]
           right = intervals[i+1]
           if left.end >= right.start:
             intervals[i] = Interval(s=left.start, e=max(left.end, right.end))
             del intervals[i+1]
           else:
             i += 1
         
         return intervals

# Definition for an interval.
 # class Interval:
 #     def __init__(self, s=0, e=0):
 #         self.start = s
 #         self.end = e
 
 class Solution:
     def insert(self, intervals, newInterval):
         """
         :type intervals: List[Interval]
         :type newInterval: Interval
         :rtype: List[Interval]
         """
         result = []
         for interval in intervals:
             if newInterval and newInterval.end >= interval.start and newInterval.start <= interval.end:
                 newInterval.start = min(interval.start, newInterval.start)
                 newInterval.end = max(interval.end, newInterval.end)
             else:
                 if newInterval and newInterval.end < interval.start:
                     result.append(newInterval)
                     result.append(interval)
                     newInterval = None
                 else:
                     result.append(interval)
         if newInterval:
             result.append(newInterval)
         return result