Merge overlapping time intervals

Problem: Merge Intervals

You are given an array of intervals intervals, where each interval is a pair [start, end] with start <= end.

Merge all overlapping intervals and return a new array of non-overlapping intervals that covers all the intervals in the input.

Overlap definition

Two intervals [a,b] and [c,d] overlap if c <= b (assuming a <= c after sorting).

Input / Output

• Input: intervals: number[][]
• Output: number[][] merged intervals

Example

• Input: [[1,3],[2,6],[8,10],[15,18]]
• Output: [[1,6],[8,10],[15,18]]

Constraints

• 1 <= intervals.length <= 10^5
• Interval values fit in 32-bit signed integers.

Follow-ups

• What is the time complexity of your approach?
• How do you handle already-sorted vs unsorted inputs?