Merge Intervals

Interval
Medium

Approach

Diagrams

Analysis

Time

O(log(n))

Space

O(n)
class Solution:
    def merge(self, intervals):
        nonOverlappingIntervals = []

        intervals.sort()

        for curInterval in intervals:
            if not nonOverlappingIntervals:
                nonOverlappingIntervals.append(curInterval)

            lastInterval = nonOverlappingIntervals[-1]

            if self.doOverlap(lastInterval, curInterval):
                newEnd = max(lastInterval[1], curInterval[1])
                lastInterval[1] = newEnd

            else:
                nonOverlappingIntervals.append(curInterval)

        return nonOverlappingIntervals

    def doOverlap(self, interval, otherInterval):
        start, end = interval
        otherStart, otherEnd = otherInterval
        return not (start > otherEnd or otherStart > end)

Learn

#Sort

Videos