## Merge Intervals

###### DESCRIPTION (credit Leetcode.com)

Write a function to consolidate overlapping intervals within a given array intervals, where each interval intervals[i] consists of a start time starti and an end time endi. The function should return an array of the merged intervals so that no two intervals overlap and all the intervals collectively cover all the time ranges in the original input.

###### EXAMPLES

Input:

`intervals = [[3,5],[1,4],[7,9],[6,8]]`

Output:

`[[1,5],[6,9]]`

Explanation: The intervals [3,5] and [1,4] overlap and are merged into [1,5]. Similarly, [7,9] and [6,8] overlap and are merged into [6,9].

Run your code to see results here

## Explanation

Since this question involves merging intervals that overlap, we want to first sort the intervals by their start time. This allows us to easily check if an interval overlaps with the one before it. Then we create a new array to store the merged intervals.

We iterate through the sorted intervals and check if the current interval overlaps with the last interval in the merged array. If it does, we merge the intervals by updating the end time of the last interval in the merged array to be the maximum of the end times of the current interval and the last interval in the merged array (i.e. max(merged[-1][1], current[1])).

Note the first interval can always be added directly to the merged array.

def mergeIntervals(intervals):sortedIntervals = sorted(intervals, key=lambda x: x[0])merged = []for interval in sortedIntervals:if not merged or interval[0] > merged[-1][1]:merged.append(interval)else:merged[-1][1] = max(interval[1], merged[-1][1])return merged

If it doesn't, we add the current interval directly to the merged array.

def mergeIntervals(intervals):sortedIntervals = sorted(intervals, key=lambda x: x[0])merged = []for interval in sortedIntervals:if not merged or interval[0] > merged[-1][1]:merged.append(interval)else:merged[-1][1] = max(interval[1], merged[-1][1])return merged

### Complexity Analysis

**Time Complexity**: O(n * logn) where n is the number of intervals due to the sorting step.
**Space Complexity**: O(n) for the merged output array.

## Solution

def mergeIntervals(intervals):sortedIntervals = sorted(intervals, key=lambda x: x[0])merged = []for interval in sortedIntervals:if not merged or interval[0] > merged[-1][1]:merged.append(interval)else:merged[-1][1] = max(interval[1], merged[-1][1])return merged

Loading comments...