Bernice Waweru

Posted on

# 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 !!

## Top comments (0)

Do you want us to help make DEV a better place?

Fill out this survey and help us by becoming a tag moderator here at DEV.