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


  • -1
    W
    # 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:]

Log in to reply
 

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