Possible O(logN) solution with binary search


  • 2
    G

    Looking at the problem, the O(N) solution is pretty straightforward, and I thought it's for sure going to TLE. Therefore I come up with an O(logN) solution.

    From the problem we know:

    • "start" of the intervals are sorted
    • intervals are not overlapped (i.e. the end of an interval is smaller than the start of next interval, otherwise they are overlapped and should be merged into one)

    from the 2 facts we can draw the following conclusion

    • "end" of the intervals are also sorted

    (proof: For all i, end_i > start_i > end_(i-1) => end_i > end_(i-1). "end" values are sorted)

    When you have sorted integer, you can apply binary search and find the place you need to insert. You will need to do it twice: once for start of interval, once for end of interval

    1. start of interval: last_interval_before_insert.end < newInterval.start
    2. end of interval: first_interval_after_insert.start > newInterval.end

    After you find the start/end of the interval, everything in between should be merged.

    The general idea is like that but my code is too ugly so I don't feel like posting them :(


  • 1
    G

    I think this should be a clear example.

    def binarySearch(intervals, val):
        left, right = 0, len(intervals)-1
        while left <= right:
            mid = (left + right) / 2
            if intervals[mid].start <= val <= intervals[mid].end:
                return mid
            elif val < intervals[mid].start:
                right = mid - 1
            else:
                left = mid + 1
                
        return left
    
    class Solution(object):
        def insert(self, intervals, newInterval):
            """
            :type intervals: List[Interval]
            :type newInterval: Interval
            :rtype: List[Interval]
            """
            if len(intervals) == 0:
                return [newInterval]
            
            left = binarySearch(intervals, newInterval.start)
            right = binarySearch(intervals, newInterval.end)
            length = len(intervals)
            
            merge_left = left < length and intervals[left].end >= newInterval.start
            merge_right = right < length and intervals[right].start <= newInterval.end
            l = left if merge_left or left >= length else left+1
            r = right+1 if merge_right else right
            
            start = min(intervals[left].start, newInterval.start) if merge_left else newInterval.start
            end = max(intervals[right].end, newInterval.end) if merge_right else newInterval.end
            
            return intervals[:l] + [Interval(start, end)] + intervals[r:]

  • 0
    L

    I got the same idea of finding start and end. But creation of new array still take O(n). So still don't think O(lgN) is possible.


Log in to reply
 

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