Python O(n) solution


  • 0
    F

    This solution runs in O(n) time (best case). The lower time complexity comes with increased space complexity, as we allocate an array with size equal to the range of the intervals. This algorithm is O(n), but where n is the range from the smallest start to the largest end. If this range is large relative to the number of intervals, this is an inefficient answer. It also has a lot of overhead relative to the canonical solution, and python's built in sort is very fast. So it isn't particularly fast on LeetCode.

    The algorithm works by iterating through the list of intervals, for each interval we add 1 to a counter at the index of the interval start, and subtract 1 from a counter at the index of the interval end. In this implementation the start counter and the end counter are stored separately, because we need to be able to detect intervals of zero-length in the next step. We then iterate through the array we stored, keeping a counter. Noting when we increase from below 1 to 1 or greater, this is the beginning of an interval, and when we decrease from above 0 to 0, this is the end of an interval that we add to our result.

    The code. Please feel free to suggest improvements:

    class Solution(object):
        def merge(self, intervals):
            """
            :type intervals: List[Interval]
            :rtype: List[Interval]
            """
            if not intervals or len(intervals) < 2:
                return intervals
            
            lowest = min([x.start for x in intervals])
            highest = max([x.end for x in intervals])
            
            dp = [[0, 0] for _ in range(highest - lowest + 1)]
            
            for interval in intervals:
                dp[interval.start - lowest][0] += 1
                dp[interval.end - lowest][1] -= 1
            
            count, start, res = 0, 0, []
            for index, (s, e) in enumerate(dp):
                prev, count = count, count + s
                if prev < 1 and count >= 1:
                    start = index + lowest
                
                prev, count = count, count + e
                if prev > 0 and count == 0:
                    res.append([start, index+lowest])
            return res
    

  • 0

    Kind of like sort by index. Fast but space consuming. Slower if range of interval is huge because of overhead of creating the array.


Log in to reply
 

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