Merge Intervals in Python

Given a list of intervals where intervals[i] = [starti, endi], merge all overlapping intervals and return a list of the intervals that remain, sorted by their start.

Two intervals overlap when they share at least one point. Intervals that only touch, like [1,4] and [4,5], share the point 4, so they overlap too and merge into [1,5].

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: [1,3] and [2,6] overlap, so they merge into [1,6]. The other two overlap nothing.

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: The two intervals touch at 4, which counts as overlapping.

Example 3:

Input: intervals = [[6,8],[1,9],[2,4],[4,7]]
Output: [[1,9]]
Explanation: The input isn't sorted. [1,9] covers every other interval, so they all merge into it.

Constraints:

• 1 <= intervals.length <= 105
• 0 <= starti <= endi <= 106