Merge overlapping intervals
Coding problemMediumAsked in: Amazon, Google, Microsoft, Nutanix, Zoho
Given a list of intervals, each written as [start, end] with start at most end, merge every group of intervals that overlap or touch, and return the merged intervals sorted by start.
Two intervals touch when one ends exactly where the other starts: [1, 4] and [4, 5] merge into [1, 5]. The input is in any order. An empty list gives an empty list.
Examples
Example 1
Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Example 2
Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Example 3
Input: intervals = [[5,6],[1,2]]
Output: [[1,2],[5,6]]
The result is sorted by start.
Constraints
- The list holds between 0 and 100,000 intervals
- Each start and end is between -1,000,000,000 and 1,000,000,000, with start at most end
Run checks the 3 examples. Submit also runs the hidden tests: edge cases, large inputs and a time limit.
Run your code to see the results here. Ctrl or Cmd + Enter runs; add Shift to submit.