Insert and merge an interval
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
You are given a list of pairwise non-overlapping closed intervals [si, ei] sorted by start time, and a new interval [s, e]. Insert [s, e] into the list so that the result remains sorted and contains no overlaps (merge when necessary). Return the resulting list of intervals. Analyze time and space complexity and cover edge cases such as insertion at the beginning/end, full containment, and an empty input list.
Quick Answer: This question evaluates array and interval manipulation skills, algorithmic problem-solving, and the ability to reason about merging overlapping ranges in a sorted sequence.
Insert a new interval into sorted non-overlapping closed intervals and merge overlaps.
Constraints
- Inputs are provided as Python literals matching the function signature.
- Return a deterministic exact-match result.
Examples
Input: ([[1,3],[6,9]], [2,5])
Expected Output: [[1, 5], [6, 9]]
Explanation: Merge with first.
Input: ([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8])
Expected Output: [[1, 2], [3, 10], [12, 16]]
Explanation: Merge several.
Input: ([], [4,8])
Expected Output: [[4, 8]]
Explanation: Empty intervals.
Hints
- Choose a representation that makes the core operation simple.
- Handle empty and boundary inputs before the main algorithm.