Given an array of `intervals`

where `intervals[i] = [start`

, merge all overlapping intervals, and return _{i}, end_{i}]*an array of the non-overlapping intervals that cover all the intervals in the input*.

**Example 1:**

Input:intervals = [[1,3],[2,6],[8,10],[15,18]]Output:[[1,6],[8,10],[15,18]]Explanation:Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].

**Example 2:**

Input:intervals = [[1,4],[4,5]]Output:[[1,5]]Explanation:Intervals [1,4] and [4,5] are considered overlapping.

**Constraints:**

`1 <= intervals.length <= 10`

^{4}`intervals[i].length == 2`

`0 <= start`

_{i}<= end_{i}<= 10^{4}

Visualize the input as a continuous list of numbers as shown below

If you are given an input [1,3] [2,6] [8,10] you can see that the numbers which overlap are in the range [1,6]

Let’s start using this logic to get our pseudo code.

If the second digit of the first range, is less than or equal to the first digit of the second range, then they are in the same interval.

If yes, let’s get a new interval by adding the first digit of the first range, and the second digit of the second range.

We can use the code below to generate the merged intervals.

```
func merge(_ intervals: [[Int]]) -> [[Int]] {
var newArray = intervals
newArray.sort { a, b in
a[0] < b[0]
}
var mergedList: [[Int]] = [[Int]]()
for interval in newArray {
if mergedList.isEmpty || mergedList.last![1] < interval[0] {
print(interval)
mergedList.append(interval)
} else {
let last = mergedList.count
mergedList[last-1][1] = max(mergedList.last![1], interval[1])
}
}
return mergedList
}
```

The complexity is O(NlogN). This is because of the sorting and looping through the values once.

The space complexity is O(N)

## Leave a Reply