Merge Intervals

Instructions

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Approach

1. Sort the input by starttime to have an ascending list for comparison.

2. Iterate through sorted intervals and if start of a given interval is less than or equal to the most recent end time stored in the result list then,update the previous end time(ie most recent end time in the result list) based on the max of current prevEnd and end of current interval.

3. If condition is not met append interval to result.

Implementation

def merge(self, intervals: List[List[int]]) -> List[List[int]]:

        intervals.sort()

        result = [intervals[0]]

        for start,end in intervals[1:]:

            prevEnd = result[-1][1]

            if start <= prevEnd:
                result[-1][1] =  max(prevEnd,end)
            else:
                result.append([start,end])
        return result

Happy coding !!