Is this naive algorithm consider good? Any other suggestions? (Python, Accepted)


  • 0
    E

    Basically I search the subset of intervals between newInterval.start and newInterval.end, then replace them with the merged one (the subset and newInterval).
    The first for loop searches for the starting index of the element to merge in intervals.
    The second searches for the ending index.
    There are a couple of boundary conditions so the logic structure becomes a bit messy.
    I know this is kind of naive. But since it's marked as a hard problem, I think there might be some better solutions?

    def insert(self, intervals, newInterval):
        if 0 == len(intervals):
            return [newInterval]
    
        mergeStartIdx, mergeEndIdx = None, None
        for idx, inter in enumerate(intervals):
            if newInterval.start < inter.start:
                if 0 < idx and newInterval.start <= intervals[idx-1].end:
                    mergeStartIdx = idx-1
                else:
                    mergeStartIdx = idx
                break
        else:
            mergeStartIdx = len(intervals)
            if newInterval.start <= intervals[len(intervals)-1].end:
                mergeStartIdx -= 1
        intervals.insert(mergeStartIdx, newInterval)
    
        for idx, inter in enumerate(intervals[mergeStartIdx:]):
            idx = mergeStartIdx + idx
            if newInterval.end < inter.start:
                mergeEndIdx = idx
                break
        else:
            mergeEndIdx = len(intervals)
    
        intervals = intervals[:mergeStartIdx] \
                  + self.merge(intervals[mergeStartIdx:mergeEndIdx]) \
                  + intervals[mergeEndIdx:]
        return intervals
    
    def merge(self, intervals):
        if len(intervals):
            return [Interval(min([i.start for i in intervals]),
                                    max([i.end for i in intervals]))]
        return []
    

    Thanks a lot!


Log in to reply
 

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