Merge overlapping intervals
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given an array of intervals, where each interval is represented as a pair of integers [start, end] with start <= end. The intervals may be unsorted and may overlap.
Task:
- Merge all overlapping intervals.
- Return a new array of non-overlapping intervals that cover exactly the same ranges as the input.
- The result should be sorted in ascending order by interval start.
Example:
- Input: [[1,3], [2,6], [8,10], [15,18]]
- Output: [[1,6], [8,10], [15,18]]
Constraints (you may assume reasonable values if not specified by the interviewer):
- 1 <= number of intervals <= 10^4
- Interval endpoints are integers in a range such as [-10^9, 10^9].
Design an algorithm to perform this merge efficiently and discuss its time and space complexity.
Quick Answer: This question evaluates proficiency in interval manipulation, array-based data structures, algorithm design, and time/space complexity analysis, focusing on merging overlapping numeric ranges into non-overlapping sorted intervals.
Merge closed overlapping intervals and return them sorted by start.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([[1,3],[2,6],[8,10],[15,18]],)
Expected Output: [[1, 6], [8, 10], [15, 18]]
Explanation: Overlapping intervals merge.
Input: ([[1,4],[4,5]],)
Expected Output: [[1, 5]]
Explanation: Closed intervals touching at an endpoint merge.
Input: ([],)
Expected Output: []
Explanation: Empty input returns empty output.
Hints
- Clarify edge cases before coding.
- Keep the return value deterministic.