Insert Interval

Geek has an array ofnon-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:

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].

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],[8,10].

Constraints:
1 ≤ intervals.size() ≤ 10⁵
0 ≤ start[i], end[i] ≤ 10⁹

Approach 01:

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int>> insertInterval(vector<vector<int>> &intervals, vector<int> &newInterval) {
        vector<vector<int>> mergedIntervals;
        intervals.push_back(newInterval); // Add the new interval to the list
        sort(intervals.begin(), intervals.end()); // Sort intervals by start time
        
        int currentStart = intervals[0][0];
        int currentEnd = intervals[0][1];
        
        for (int i = 1; i < intervals.size(); i++) {
            if (currentEnd >= intervals[i][0]) {
                // Merge overlapping intervals
                currentEnd = max(currentEnd, intervals[i][1]);
            } else {
                // Add the merged interval to the result
                mergedIntervals.push_back({currentStart, currentEnd});
                currentStart = intervals[i][0];
                currentEnd = intervals[i][1];
            }
        }
        // Add the last interval
        mergedIntervals.push_back({currentStart, currentEnd});
        return mergedIntervals;
    }
};

class Solution:
    def insertInterval(self, intervals, newInterval):
        mergedIntervals = []
        intervals.append(newInterval)  # Add the new interval to the list
        intervals.sort()  # Sort intervals by start time
        
        currentStart = intervals[0][0]
        currentEnd = intervals[0][1]
        
        for i in range(1, len(intervals)):
            if currentEnd >= intervals[i][0]:
                # Merge overlapping intervals
                currentEnd = max(currentEnd, intervals[i][1])
            else:
                # Add the merged interval to the result
                mergedIntervals.append([currentStart, currentEnd])
                currentStart = intervals[i][0]
                currentEnd = intervals[i][1]
        
        # Add the last interval
        mergedIntervals.append([currentStart, currentEnd])
        return mergedIntervals

Time Complexity

• Adding the New Interval:
  • The new interval is added to the existing intervals list in \(O(1)\).
• Sorting:
  • The intervals list, containing \(n + 1\) intervals (where \(n\) is the original size), is sorted based on the start time.
  • Sorting takes \(O((n+1) \log(n+1))\), simplified to \(O(n \log n)\).
• Traversal and Merging:
  • The sorted intervals are traversed once to merge overlapping intervals.
  • This traversal takes \(O(n)\).
• Overall Time Complexity:

  The total time complexity is \(O(n \log n)\), dominated by the sorting step.

Space Complexity

• Result Storage:
  • The result vector, mergedIntervals, stores all intervals after merging.
  • This requires \(O(n)\) space in the worst case, where no intervals overlap.
• Sorting Auxiliary Space:
  • Sorting the intervals may require \(O(n)\) additional space, depending on the sorting algorithm used (e.g., quicksort or mergesort).
• Other Variables:
  • Variables such as currentStart, currentEnd, and loop variables require \(O(1)\) space.
• Overall Space Complexity:

  The total space complexity is \(O(n)\), dominated by the result storage and sorting auxiliary space.