Merge overlapping intervals
Calendar views, availability pickers and text highlighters all end up with ranges that overlap and need collapsing before they can be drawn, or the same pixels get painted twice and the labels stack.
Implement mergeIntervals(intervals). intervals is an array of [start, end] number pairs, in no particular order, where start is never greater than end. Return a new array of [start, end] pairs covering exactly the same ground, with every overlap merged, sorted by start ascending. Intervals that merely touch — where one ends exactly where the next begins — count as overlapping and must be merged. An empty input returns an empty array. Do not modify the input array or the pairs inside it.
Arguments
intervalsArray<[number, number]>- An array of
[start, end]pairs in any order, withstart <= endon each pair.
Returns
Array<[number, number]> — A new array of merged [start, end] pairs sorted by start ascending.
Examples
mergeIntervals([[1, 3], [2, 6], [8, 10], [15, 18]]);
// [[1, 6], [8, 10], [15, 18]]mergeIntervals([[1, 4], [4, 5]]);
// [[1, 5]] — touching ranges count as overlappingmergeIntervals([[1, 10], [2, 3]]);
// [[1, 10]] — a fully contained range is swallowedWhat it has to do
- Merge intervals that overlap, including ones that only touch at an endpoint.
- Return the result sorted by start value ascending.
- Accept input in any order.
- Return an empty array for an empty input.
- Do not mutate the input array or the pairs it contains.
Notes
- Dominated by the sort: O(n log n) time, O(n) extra space for the result and the sorted copy.
- Copying each pair before sorting is what keeps the input untouched —
.sort()on the original would reorder the caller's array. - The sweep itself relies on the sort: with ranges in start order, you only ever need to compare the next range to the last merged one.
Stuck? The javascript course covers everything this challenge needs.
- 1.merges overlapping ranges
- 2.merges ranges that only touch
- 3.sorts unordered input before merging
- 4.swallows a fully contained range
- 5.returns an empty array and leaves the input alone
These assertions run in your browser the moment you hit Run. Pass all of them to claim the XP.
Discussion
Sign in to postNo comments yet. Be the first to say something.