Merge Intervals

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: [[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].

1. Sort the Intervals: First, sort the intervals based on their start times. This brings potentially overlapping intervals next to each other.
2. Iterate and Merge: Create a merged list and add the first interval.
3. Compare: For each subsequent interval, check if it overlaps with the last interval in the merged list (i.e., current.start <= last.end).
4. Update: If they overlap, update the last interval's end time to max(last.end, current.end). If they don't, simply append the current interval to the merged list.

Observe how sorting simplifies the problem to a linear merge process.