Merge Overlapping Intervals

You are given a collection of intervals, where each interval is represented by a start and end point. Your task is to merge all overlapping intervals and return a new collection of non-overlapping intervals that cover all the original intervals. This is a common problem in scheduling, resource allocation, and data compression.

Problem Description

You will be provided with a list of intervals. Each interval is an array (or similar structure) containing two integers: [start, end].

The goal is to merge any intervals that overlap. Two intervals [a, b] and [c, d] overlap if b >= c (assuming intervals are sorted by start time). When intervals overlap, they should be merged into a single interval that encompasses both. For example, merging [1, 3] and [2, 6] would result in [1, 6].

The final output should be a list of intervals where no two intervals overlap, and every interval in the output is a consolidation of one or more of the original overlapping intervals.

Key Requirements:

• Merge all overlapping intervals.
• Return a list of intervals that are completely non-overlapping.
• The order of the output intervals should ideally be sorted by their start times, but this is not strictly mandatory if the non-overlapping property is maintained.

Edge Cases to Consider:

• An empty list of intervals.
• A list with only one interval.
• Intervals that are completely contained within other intervals (e.g., [2, 4] within [1, 5]).
• Intervals that touch at their endpoints (e.g., [1, 2] and [2, 3]).

Examples

Example 1:

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Intervals [1,3] and [2,6] overlap, merging them into [1,6]. The remaining intervals do not overlap.

Example 2:

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] overlap (or touch at the endpoint), merging them into [1,5].

Example 3:

Input: [[1,4],[0,4]]
Output: [[0,4]]
Explanation: Intervals [1,4] and [0,4] overlap, and [1,4] is contained within [0,4] after sorting by start time, resulting in [0,4].

Constraints

• 1 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= start_i <= end_i <= 10^4
• The input intervals can be in any order.

Notes

• Consider how sorting the intervals by their start times might simplify the merging process.
• Think about how to efficiently check for overlaps and combine intervals.
• The problem is language-agnostic, so focus on the logic and data structures.