Coding questions · Amazon
Merge overlapping and adjacent ranges
This question evaluates a candidate's understanding of interval merging and range manipulation, including handling overlapping and adjacent ranges, edge cases like single-point gaps and extreme values, and the ability to analyze time and space complexity.
Given an unsorted list of integer ranges represented as half-open intervals [start, end) with start < end, merge all overlapping or directly adjacent ranges and return the merged list sorted by start. Also return the total length covered by the merged ranges. For example, merging [1, 4), [3, 5), and [5, 7) yields [1, 7) and total length 6. Implement an efficient solution and analyze time and space complexity. Consider edge cases such as single-point gaps, negative values, very large inputs, and stability of the original ordering when ranges are identical.
Merge Overlapping and Adjacent Ranges
Merge unsorted half-open ranges that overlap or directly touch, and return merged ranges plus total covered length.
Examples
Example 1
Input: ([[1,4],[3,5],[5,7]],)
Output: {'ranges': [[1, 7]], 'totalLength': 6}
Explanation: Prompt example.
Example 2
Input: ([[10,12],[1,2],[3,4]],)
Output: {'ranges': [[1, 2], [3, 4], [10, 12]], 'totalLength': 4}
Explanation: Single-point gap does not merge.
Hints
- Choose a representation that makes the core operation simple.
- Handle empty and boundary inputs before the main algorithm.