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.