Insert Interval
Problem link: https://leetcode.com/problems/insert-interval/
Problem Statement
You are given a list of non-overlapping intervals sorted by their start time.
Insert a new interval into the intervals such that the list remains sorted and non-overlapping. Merge intervals if necessary.
Input
- intervals: [[start, end]] sorted and non-overlapping
- newInterval: [start, end]
Output
- Return updated list after insertion and merging
Example
intervals = [[1,3],[6,9]]
newInterval = [2,5]
Explanation
New interval overlaps with [1,3], so we merge → [1,5]
Final: [[1,5],[6,9]]
Brute Force
Intuition
Insert the new interval into the list and solve using the classic merge intervals approach.
Approach
- Add newInterval to intervals
- Sort all intervals
- Merge overlapping intervals
- Return result
Dry Run
Input: intervals = [[1,3],[6,9]] newInterval = [2,5]
Step 1: Insert new interval [[1,3],[6,9],[2,5]]
Step 2: Sort intervals [[1,3],[2,5],[6,9]]
Step 3: Merge
- Compare [1,3] and [2,5] → overlap → merge → [1,5]
- Compare [1,5] and [6,9] → no overlap → push [1,5]
Step 4: Final [[1,5],[6,9]]
Code (Java)
import java.util.*;
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> list = new ArrayList<>(Arrays.asList(intervals));
list.add(newInterval);
list.sort((a, b) -> a[0] - b[0]);
List<int[]> result = new ArrayList<>();
int[] current = list.get(0);
for (int i = 1; i < list.size(); i++) {
int[] next = list.get(i);
if (current[1] >= next[0]) {
current[1] = Math.max(current[1], next[1]);
} else {
result.add(current);
current = next;
}
}
result.add(current);
return result.toArray(new int[result.size()][]);
}
}
Complexity Analysis
Sorting dominates → O(N log N). Merging is linear.
Optimal Solution
Intuition
Since intervals are sorted, process them in one pass by dividing into three phases: before overlap, merging, and after.
Approach
- Add intervals ending before newInterval starts
- Merge overlapping intervals
- Add remaining intervals
Dry Run
Input: intervals = [[1,2], [3,5], [6,7], [8,10], [12,16]] newInterval = [4,8]
Step 1: Check before overlap
- [1,2]: 2 < 4? Yes → Add [1,2] to result.
- [3,5]: 5 < 4? No → Potential overlap starts.
- Current Result: [[1,2]]
Step 2: Merge
- [3,5]: 3 <= 8? Yes (Overlap)
- Update newInterval: [min(4,3), max(8,5)] → [3,8]
- [6,7]: 6 <= 8? Yes (Overlap)
- Update newInterval: [min(3,6), max(8,7)] → [3,8]
- [8,10]: 8 <= 8? Yes (Overlap)
- Update newInterval: [min(3,8), max(8,10)] → [3,10]
Step 3: Check next
- [12,16]: 12 <= 10? No → Overlap period is over.
Step 4: Add merged interval
- Add the final version of newInterval ([3,10]) to the result.
- Current Result: [[1,2], [3,10]]
Step 5: Add remaining
- [12,16]: Remaining after the merge. Add to result.
- Final Result: [[1,2], [3,10], [12,16]]
Code (Java)
import java.util.*;
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> result = new ArrayList<>();
int i = 0;
while (i < intervals.length && intervals[i][1] < newInterval[0]) {
result.add(intervals[i]);
i++;
}
while (i < intervals.length && intervals[i][0] <= newInterval[1]) {
newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
i++;
}
result.add(newInterval);
while (i < intervals.length) {
result.add(intervals[i]);
i++;
}
return result.toArray(new int[result.size()][]);
}
}
Complexity Analysis
Single pass → O(N). No sorting required.
Quick Revision (Brute Force)
- Insert → Sort → Merge
- Easy but slower
- O(N log N)
Quick Revision (Optimal)
- 3 phases: before, merge, after
- Single pass
- O(N)