Consolidate Ranges
MediumIntervals
Problem
A firewall holds a list of blocked port ranges, each [low, high] with both ends included. Over time, administrators added overlapping entries, and the list has become hard to audit.
Merge every group of ranges that share at least one port into a single range, and return the resulting disjoint ranges sorted by low.
Example 1
- Input:
- ranges = [[1, 3], [8, 10], [2, 6], [15, 18]]
- Output:
- [[1, 6], [8, 10], [15, 18]]
[1, 3] and [2, 6] share ports 2 and 3, so they merge into [1, 6].
Example 2
- Input:
- ranges = [[1, 4], [4, 5]]
- Output:
- [[1, 5]]
Both ranges contain port 4.
Example 3
- Input:
- ranges = [[6, 8], [1, 2], [3, 4]]
- Output:
- [[1, 2], [3, 4], [6, 8]]
[1, 2] and [3, 4] share no port, so they stay separate.
Constraints
- 1 ≤ ranges.length ≤ 10^4
- -10^9 ≤ low ≤ high ≤ 10^9
Hint
Show the first hint
Which ranges could possibly merge with a given range if they were listed in order of their low end?
Walkthrough
How to approach it
01Clarify before coding
- Do ranges that only touch at an endpoint merge? Yes, [1, 4] and [4, 5] share port 4. [1, 2] and [3, 4] do not merge.
- Is the input sorted? No.
- Must the output be sorted? Yes, by low end.
02Brute force
Repeatedly scan all pairs, merge any two that overlap, and restart until no pair overlaps.
Cost: O(n³) in the worst case (n merges, each found by an O(n²) scan).
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.