C++: Insert Interval

Thought Process

To solve the problem of inserting and merging intervals, we first determine the correct position to insert the new interval. This is done by iterating through the existing intervals and finding the first interval whose start is greater than or equal to the start of the new interval. Once the position is found, the new interval is inserted. After insertion, we merge overlapping intervals by comparing the end of the current interval with the start of the next interval. If they overlap, we merge them by updating the end of the current interval. This process continues until all intervals are processed, ensuring that the final list of intervals is non-overlapping. 

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        
        // Find the correct position to put the new intervals
        int position = intervals.size();
        for(int i=0;i<intervals.size();i++){

            if(intervals[i][0] >= newInterval[0]){
                position = i;
                break;
            }
        }
        // Adding the newInterval to the position
        intervals.insert(intervals.begin()+position,newInterval);

        // Merging the intervals
        vector<int> refInterval = intervals[0];
        vector<vector<int>> ans;
        for(int i=1;i<intervals.size();i++){

            vector<int> currentInterval = intervals[i];
            
            int refStart = refInterval[0];
            int refEnd  = refInterval[1];

            int start = currentInterval[0];
            int end   = currentInterval[1];

            if(refEnd < start){
                ans.push_back(refInterval);
                refInterval.swap(currentInterval);
            }
            else{
                refInterval[0] = refStart;
                refInterval[1] = max(refEnd,end);
            }
        }
        ans.push_back(refInterval);
        return ans;
    }
};

Code Complexity

Time Complexity: O(n)

The algorithm iterates through the array once to find the correct position to insert the new interval and then iterates through the array again to merge overlapping intervals. Each operation is O(1) on average.

Space Complexity: O(n)

The space required is proportional to the number of intervals, as we store the merged intervals in a new vector.

Code copied!