# Python, Binary Search index the start and end of new interval insert O(log(n))

• ``````# Definition for an interval.
# class Interval(object):
#     def __init__(self, s=0, e=0):
#         self.start = s
#         self.end = e

class Solution(object):
def insert(self, intervals, newInterval):
"""
:type intervals: List[Interval]
:type newInterval: Interval
:rtype: List[Interval]
"""
n=len(intervals)
if n==0:
return [newInterval]
a,b=newInterval.start, newInterval.end
if a>intervals[-1].end:
return intervals+[newInterval]
elif b<intervals[0].start:
return [newInterval]+intervals
intervals[0].start=min(intervals[0].start,a)
intervals[-1].end=max(intervals[-1].end,b)
s1,e1=0,n-1
m1=(s1+e1)/2
while e1-s1>1:
m1=(e1+s1)/2
if a>=intervals[m1].start:
s1=m1
else:
e1=m1
if a>=intervals[e1].start:
s1=e1
s2,e2=s1,n-1
m2=(s2+e2)/2
while e2-s2>1:
m2=(e2+s2)/2
if b<=intervals[m2].end:
e2=m2
else:
s2=m2
if b<=intervals[s2].end:
e2=s2
if a<=intervals[s1].end and b>=intervals[e2].start:
newInterval.start=intervals[s1].start
newInterval.end=intervals[e2].end
return intervals[:s1]+[newInterval]+intervals[e2+1:]
elif a<=intervals[s1].end and b<intervals[e2].start:
newInterval.start=intervals[s1].start
return intervals[:s1]+[newInterval]+intervals[e2:]
elif a>intervals[s1].end and b>=intervals[e2].start:
newInterval.end=intervals[e2].end
return intervals[:s1+1]+[newInterval]+intervals[e2+1:]
elif a>intervals[s1].end and b<intervals[e2].start:
return intervals[:s1+1]+[newInterval]+intervals[e2:]``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.