Insert Interval
Part of Practice: Insert & Merge
You are given a list of intervals, each a pair [start, end], already sorted by start and non-overlapping. You are also given one new interval to insert. Add the new interval to the list so that the result is still sorted and non-overlapping — merging the new interval with any existing intervals it overlaps. Return the resulting list.
Constraints that matter: up to 10,000 intervals. Because the input is already sorted and disjoint, you should not re-sort — a single linear scan is enough. Two intervals overlap if they share even a single point, e.g. [1, 3] and [3, 5].
Examples
- Input:
- intervals = [[1,3],[6,9]], newInterval = [2,5]
- Output:
- [[1,5],[6,9]]
[2,5] overlaps [1,3], so they merge into [1,5]. [6,9] starts after 5, so it is untouched.
- Input:
- intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
- Output:
- [[1,2],[3,10],[12,16]]
[4,8] touches [3,5], [6,7], and [8,10]; all four merge into [3,10].
- Input:
- intervals = [], newInterval = [5,7]
- Output:
- [[5,7]]
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.