Merge Intervals in Go

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals and return an array 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