57. Insert Interval

📝 Problem Details

• Title: 57. Insert Interval
• Link: https://leetcode.com/problems/insert-interval/
• Difficulty: Medium
• Tags/Categories: Intervals

input array intervals where intervals[i] = [start,end] sorted in ascending order by start input array newInterval = [start, end] that has a single element insert newInterval into intervals such that the ascending order is maintained and there aren’t any overlapping intervals (merge them if necessary) return intervals after insertion

💭What Were My Initial Thoughts?

- the input array is already sorted by start time 
- the problem is similar to merge intervals, but instead of merging all intervals, we first insert the newInterval
- suggests a greedy approach where:
	- we insert the new interval at the right position
	- merge any overlapping intervals

💡 Explanation of Solution

• Add all intervals before newInterval (no overlap)

  • If an interval ends before newInterval starts, add it to the result unchanged.

• Merge overlapping intervals

  • If an interval overlaps with newInterval, merge them by updating start and end.

• Insert the merged newInterval

  • Once merging is done, push the updated newInterval into the result.

• Add remaining intervals

  • Append any intervals that start after newInterval without changes.

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

💻 Implementation of Solution

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        vector<vector<int>> result;
        int i=0;
        int n = intervals.size();
 
        // add all intervals before newInterval (no overlap)
        // while we are in bounds and the current interval's end is less than the newIntervals start
        while(i < n && intervals[i][1] < newInterval[0]) {
            result.push_back(intervals[i]);
            i++;
        }
 
        // merge overlapping intervals
        // while we are in bounds and the current interval's start is less than the newIntervals end
        while(i < n && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = min(newInterval[0], intervals[i][0]);
            newInterval[1] = max(newInterval[1], intervals[i][1]);
            i++;
        }
        result.push_back(newInterval); // insert merged interval
 
        // add remaining intervals
        while(i < n) {
            result.push_back(intervals[i]);
            i++;
        }
 
        return result;
    }
};