15. Insert Interval
β GFG solution to the Insert Interval problem: efficiently insert and merge overlapping intervals in a sorted array using linear traversal technique. π
The problem can be found at the following link: π Question Link
π§© Problem Description
Geek has an array of non-overlapping intervals intervals[][]
where intervals[i] = [starti, endi]
represent the start and the end of the ith event and intervals is sorted in ascending order by starti
. He wants to add a new interval newInterval[] = [newStart, newEnd]
where newStart
and newEnd
represent the start and end of this interval.
Help Geek to insert newInterval
into intervals such that intervals is still sorted in ascending order by starti
and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).
π Examples
Example 1
Input: intervals[][] = [[1, 3], [4, 5], [6, 7], [8, 10]], newInterval[] = [5, 6]
Output: [[1, 3], [4, 7], [8, 10]]
Explanation: The newInterval [5, 6] overlaps with [4, 5] and [6, 7].
So, they are merged into one interval [4, 7].
Example 2
Input: intervals[][] = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], newInterval[] = [4, 9]
Output: [[1, 2], [3, 10], [12, 16]]
Explanation: The new interval [4, 9] overlaps with [3, 5], [6, 7] and [8, 10].
So, they are merged into one interval [3, 10].
π Constraints
$1 \le \text{intervals.size()} \le 10^5$
$0 \le \text{starti} \le \text{endi} \le 10^9$
$0 \le \text{newStart} \le \text{newEnd} \le 10^9$
β
My Approach
The optimal approach uses Linear Traversal with Three-Phase Processing to efficiently handle interval insertion and merging:
Three-Phase Linear Processing
Phase 1 - Add Non-overlapping Intervals Before:
Traverse intervals from left and add all intervals that end before
newInterval
starts.Condition:
intervals[i][1] < newInterval[0]
These intervals don't overlap with
newInterval
.
Phase 2 - Merge Overlapping Intervals:
Process all intervals that overlap with
newInterval
.Condition:
intervals[i][0] <= newInterval[1]
Merge by taking minimum start and maximum end.
Update
newInterval
bounds during merging process.
Phase 3 - Add Remaining Intervals:
Add all remaining intervals after the overlap region.
These intervals start after
newInterval
ends.
Insert Merged Interval:
Add the final merged
newInterval
between phases 2 and 3.
π Time and Auxiliary Space Complexity
Expected Time Complexity: O(n), where n is the number of intervals. We traverse the intervals array exactly once, processing each interval in constant time.
Expected Auxiliary Space Complexity: O(n), where n is the number of intervals. In the worst case, we need to store all intervals in the result array. The algorithm uses constant extra space beyond the output storage.
π§ Code (C)
Interval* insertInterval(Interval* intervals, int intervalsSize, Interval newInterval, int* returnSize) {
Interval* result = (Interval*)malloc((intervalsSize + 1) * sizeof(Interval));
int i = 0, idx = 0;
while (i < intervalsSize && intervals[i].end < newInterval.start)
result[idx++] = intervals[i++];
while (i < intervalsSize && intervals[i].start <= newInterval.end) {
newInterval.start = (intervals[i].start < newInterval.start) ? intervals[i].start : newInterval.start;
newInterval.end = (intervals[i].end > newInterval.end) ? intervals[i].end : newInterval.end;
i++;
}
result[idx++] = newInterval;
while (i < intervalsSize) result[idx++] = intervals[i++];
*returnSize = idx;
return result;
}
π§βπ» Code (C++)
class Solution {
public:
vector<vector<int>> insertInterval(vector<vector<int>>& intervals, vector<int>& newInterval) {
vector<vector<int>> result;
int i = 0, n = intervals.size();
while (i < n && intervals[i][1] < newInterval[0]) result.push_back(intervals[i++]);
while (i < n && intervals[i][0] <= newInterval[1]) {
newInterval[0] = min(newInterval[0], intervals[i][0]);
newInterval[1] = max(newInterval[1], intervals[i++][1]);
}
result.push_back(newInterval);
while (i < n) result.push_back(intervals[i++]);
return result;
}
};
β Code (Java)
class Solution {
public ArrayList<int[]> insertInterval(int[][] intervals, int[] newInterval) {
ArrayList<int[]> result = new ArrayList<>();
int i = 0;
while (i < intervals.length && intervals[i][1] < newInterval[0])
result.add(intervals[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]);
}
result.add(newInterval);
while (i < intervals.length) result.add(intervals[i++]);
return result;
}
}
π Code (Python)
class Solution:
def insertInterval(self, intervals, newInterval):
result = []
i = 0
while i < len(intervals) and intervals[i][1] < newInterval[0]:
result.append(intervals[i])
i += 1
while i < len(intervals) and intervals[i][0] <= newInterval[1]:
newInterval[0] = min(newInterval[0], intervals[i][0])
newInterval[1] = max(newInterval[1], intervals[i][1])
i += 1
result.append(newInterval)
while i < len(intervals):
result.append(intervals[i])
i += 1
return result
π§ Contribution and Support
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: π¬ Any Questions?. Let's make this learning journey more collaborative!
β If you find this helpful, please give this repository a star! β
πVisitor Count
Last updated