Merge overlapping intervals

You are given an array of intervals, where each interval is represented as a pair of integers [start, end] with start <= end. The intervals may be unsorted and may overlap. Task: - Merge all overlapping intervals. - Return a new array of non-overlapping intervals that cover exactly the same ranges as the input. - The result should be sorted in ascending order by interval start. Example: - Input: [[1,3], [2,6], [8,10], [15,18]] - Output: [[1,6], [8,10], [15,18]] Constraints (you may assume reasonable values if not specified by the interviewer): - 1 <= number of intervals <= 10^4 - Interval endpoints are integers in a range such as [-10^9, 10^9]. Design an algorithm to perform this merge efficiently and discuss its time and space complexity.