Merge Intervals
An interval is a range of whole numbers with a start and an end. Intervals that share at least one point belong together, and so do intervals that only touch: [1, 4] and [4, 5] become [1, 5]. The goal is to replace every group of overlapping intervals with one interval that covers the whole group.
The trick is order. Once the intervals are sorted by start, anything that overlaps the interval you are building comes right after it. Walk the sorted list and keep the last merged interval: if the next start is at most its end, stretch the end; if not, there is a real gap, so a new interval begins. Sorting costs O(n log n) and the walk is a single pass.
Write a function named mergeIntervals that gets two integer arrays, starts and ends, and returns the merged intervals.
The intervals arrive as two arrays because not every language here accepts a 2D array as an input: interval i is [starts[i], ends[i]], and both arrays have the same length. The intervals are not sorted.
Merge every group of overlapping intervals. Intervals that only touch at an end also count as overlapping. Return the merged intervals as a 2D array [[start, end], ...], sorted by start.
For example, starts = [5, 1, 12, 3] and ends = [7, 4, 14, 6] describe [5, 7], [1, 4], [12, 14] and [3, 6], which merge into [[1, 7], [12, 14]].
Constraints: 1 <= starts.length == ends.length <= 10^4, 0 <= starts[i] <= ends[i] <= 10^4.
Function
- arg1integer-array
- arg2integer-array
- Returnsinteger-2d-array
Examples
- Input
- arg1 = [5, 1, 12, 3]arg2 = [7, 4, 14, 6]
- Output
- [[1, 7], [12, 14]]
- Input
- arg1 = [6, 1]arg2 = [9, 6]
- Output
- [[1, 9]]
+12 hidden tests on Submit
Hints
Open them one at a time. Each one gives away a little more.
Pair every start with its end first, so you work with whole intervals instead of two separate arrays.
Sort the intervals by start. After that, an interval can only overlap the group right before it, never one further back.
Walk the sorted intervals while holding the last merged one. If the next start is less than or equal to its end, set its end to the larger of the two ends. Otherwise that group is finished and the next interval opens a new one.
A full walkthrough of this problem is on its way.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
Python
def mergeIntervals(starts, ends):
# Write code hereCase 1
Case 2
Input
arg1 = [5, 1, 12, 3] arg2 = [7, 4, 14, 6]
Expected
[[1, 7], [12, 14]]