# Merge all overlapping intervals

[Question]: 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: –

```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] overlap, merge them into [1,6].

Constraints:
1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104```
``````//Time Complexity: O(N*logN) + O(N), where N = the size of the given array.
//Reason: Sorting the given array takes  O(N*logN) time complexity. Now, after that, we are just using a single loop that runs for N times. So, the time complexity will be O(N).
//Space Complexity: O(N), as we are using an answer list to store the merged intervals. Except for the answer array, we are not using any extra space.
func mergeOverlappingIntervals(_ intervals: [[Int]]) -> [[Int]] {

guard !intervals.isEmpty else { return [] }
var intervals = intervals.sorted(by: { \$0[0] < \$1[0] })// We are sorting the array hence we get sorted intervals

var ans = [[Int]]() // Answer stored
var start = intervals[0][0] // First object
var end = intervals[0][0] // First object

for interval in intervals {
if end < interval[0] {
ans.append([start, end])
start = interval[0]
end = interval[1]
} else {
end = max(end, interval[1])// Increment end till we get max
}
}

ans.append([start, end])
return ans
}

let arrMergeIntervals = [[1, 3], [8, 10], [2, 6], [15, 18]];
var ansMergeInterals = mergeOverlappingIntervals(arrMergeIntervals);
print("The merged intervals are:", ansMergeInterals) // [[1, 6], [8, 10], [15, 18]]``````