grid47 Exploring patterns and algorithms
Nov 1, 2024
6 min read
Solution to LeetCode 57: Insert Interval Problem
You are given an array of non-overlapping intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval, and intervals are sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval. Insert newInterval into intervals such that intervals is still sorted and there are no overlapping intervals. Merge overlapping intervals if necessary and return the updated list of intervals.
Problem
Approach
Steps
Complexity
Input: The input consists of an array of intervals sorted by their starting values and a new interval to insert.
Example: [[2, 4], [6, 8]], newInterval = [5, 7]
Constraints:
• 0 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= starti <= endi <= 10^5
• intervals is sorted by starti in ascending order.
• newInterval.length == 2
• 0 <= start <= end <= 10^5
Output: The output should be a list of intervals after inserting the new interval and merging any overlapping intervals.
Example: [[2, 4], [5, 8]]
Constraints:
• The list should be sorted by the starting values of the intervals.
• All intervals in the list should be non-overlapping after the insertion.
Goal: The goal is to merge overlapping intervals after inserting the new interval into the list.
Steps:
• 1. Iterate through the intervals and insert the new interval in the correct position based on its start value.
• 2. Merge the new interval with any overlapping intervals as needed.
• 3. Return the final list of intervals after the insertion.
Goal: The solution must handle intervals in sorted order and ensure no overlaps after the insertion.
Steps:
• Intervals are sorted by start time, so insertion must maintain this order.
• Intervals may be empty, and the solution should handle edge cases where no intervals exist.
Assumptions:
• The input intervals are sorted by their start times.
• The new interval may overlap with multiple intervals.
• Input: [[2, 4], [6, 8]], newInterval = [5, 7]
• Explanation: In this case, the new interval overlaps with the interval [6, 8], so they are merged into [5, 8]. The result is [[2, 4], [5, 8]].
• Explanation: Here, the new interval [4, 8] overlaps with [5, 6] and [8, 10], and the merged interval becomes [4, 10]. The result is [[1, 3], [4, 10]].
Approach: The approach involves inserting the new interval and merging overlapping intervals using a two-pass approach.
Observations:
• Intervals are already sorted by their start time, which simplifies the insertion process.
• By iterating through the list of intervals, we can find where the new interval fits and merge it with any overlapping intervals.
Steps:
• 1. Initialize an empty result array.
• 2. Add all intervals that end before the new interval starts to the result array.
• 3. Merge the new interval with all overlapping intervals.
• 4. Add all intervals that start after the new interval ends to the result array.
• 5. Return the result array.
Empty Inputs:
• If the input list is empty, the solution should return the new interval as the only interval.
Large Inputs:
• The algorithm should handle up to 10^4 intervals efficiently.
Special Values:
• If the new interval does not overlap with any existing intervals, it should be inserted in the correct position.
Constraints:
• The solution must run efficiently with a time complexity of O(n), where n is the number of intervals.
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
vector<vector<int>> merged;
int i =0;
while (i < intervals.size() && intervals[i][1] < newInterval[0]) {
merged.push_back(intervals[i++]);
}
while (i < intervals.size() && intervals[i][0] <= newInterval[1]) {
newInterval[0] = min(intervals[i][0], newInterval[0]);
newInterval[1] = max(intervals[i][1], newInterval[1]);
i++;
}
merged.push_back(newInterval);
while (i < intervals.size()) {
merged.push_back(intervals[i++]);
}
return merged;
}
This line declares a function named `insert` that takes a vector of intervals `intervals` and a new interval `newInterval` as input and returns a vector of merged intervals.
2 : Result Vector Initialization
vector<vector<int>> merged;
This line initializes an empty vector `merged` to store the merged intervals.
3 : Index Initialization
int i =0;
This line initializes an index `i` to 0, which will be used to iterate over the `intervals` vector.
4 : Iterate Over Non-Overlapping Intervals
while (i < intervals.size() && intervals[i][1] < newInterval[0]) {
This loop iterates over the intervals in `intervals` as long as their end points are less than the start of the `newInterval`. These intervals don't overlap with `newInterval`, so they are added directly to the `merged` vector.
5 : Add Non-Overlapping Intervals
merged.push_back(intervals[i++]);
The current interval `intervals[i]` is added to the `merged` vector, and the `i` index is incremented.
6 : Merge Overlapping Intervals
while (i < intervals.size() && intervals[i][0] <= newInterval[1]) {
This loop iterates over the intervals that overlap with `newInterval`. The start of `newInterval` is updated to the minimum of its current start and the start of the current interval, and the end of `newInterval` is updated to the maximum of its current end and the end of the current interval. This effectively merges the overlapping intervals.
