57. Insert Interval
1. Description
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
2. Example
Example 1:
Input: intervals = [[1,3],[6,9]], newInterval = [2,5]
Output: [[1,5],[6,9]]
Example 2:
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
Example 3:
Input: intervals = [], newInterval = [5,7]
Output: [[5,7]]
Example 4:
Input: intervals = [[1,5]], newInterval = [2,3]
Output: [[1,5]]
Example 5:
Input: intervals = [[1,5]], newInterval = [2,7]
Output: [[1,7]]
3. Constraints
- 0 <= intervals.length <= $10^4$
- intervals[i].length == 2
- 0 <= intervals[i][0] <= intervals[i][1] <= $10^5$
- intervals is sorted by intervals[i][0] in ascending order.
- newInterval.length == 2
- 0 <= newInterval[0] <= newInterval[1] <= $10^5$
4. Solutions
My Accepted Solution
n = i_intervals.size()
Time complexity: O($nlg_2n$)
Space complexity: O(n)
// Reuse '56. Merge Intervals' code, but it is very slow, since lots of operations are unrequired, like sorting
// Actually, I think it will be helpful to use binary search to locate which interval to merge, but I failed
class Solution
{
public:
// vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval)
vector<vector<int>> insert(vector<vector<int>>& i_intervals, vector<int>& i_newInterval)
{
i_intervals.push_back(i_newInterval);
sort(i_intervals.begin(), i_intervals.end(), [](vector<int> left, vector<int> right){return left[0] < right[0];});
vector<vector<int>> results = {i_intervals.front()};
for(auto i : i_intervals)
{
if(results.back()[1] >= i.front())
{
results.back()[1] = max(results.back()[1], i.back());
}
else
{
results.push_back(i);
}
}
return results;
}
};
4.1 Straight-forward
n = i_intervals.size()
Time complexity: O(n)
Space complexity: O(1)
class Solution
{
public:
// vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval)
vector<vector<int>> insert(vector<vector<int>>& i_intervals, vector<int>& i_newInterval)
{
auto range = equal_range(i_intervals.begin(), i_intervals.end(), i_newInterval,
[](vector<int> left, vector<int> right){return left.back() < right.front();}
);
auto iterLeft = range.first, iterRight = range.second;
if (iterLeft == iterRight)
{
i_intervals.insert(iterLeft, i_newInterval);
}
else
{
iterRight--;
(*iterRight)[0] = min(i_newInterval[0], (*iterLeft)[0]);
(*iterRight)[1] = max(i_newInterval[1], (*iterRight)[1]);
i_intervals.erase(iterLeft, iterRight);
}
return i_intervals;
}
};