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.

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 <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

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)