Insert Interval Leetcode Solution

Hello and welcome back to the Daily Leetcode Series! We'll be solving a very simple, but extremely logical problem today. Without further ado, let's get started.

Understanding The Problem

Let's take a look at the problem statement.

You are given an array of non-overlapping intervals intervals where intervals[i] = [start<sub>i</sub>, end<sub>i</sub>] represent the start and the end of the i<sup>th</sup> interval and intervals is sorted in ascending order by start<sub>i</sub>. 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 in ascending order by start<sub>i</sub> and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

This is an extension of a very famous problem, Merge Intervals. Here, we first need to insert a new interval in an array of sorted intervals at the correct position and then make sure there are no overlapping intervals in the resulting array.

Intuition

If you've encountered the Merge Intervals problem before, you'll find this problem to be a cakewalk. Mere two-three lines of code to that solution would be enough to solve this problem as well.

First, let's focus on getting the new interval inserted at the current position. Since the input array is already sorted on the start time of intervals, we can run a simple loop over the array and check for the first interval whose start is greater than the new interval's start . In case we don't find such an interval, we insert the new interval at the end of the array.

Now, to merge overlapping intervals, we'll follow this algorithm:

1. Declare a new array of intervals merged . This will store our final answer of non-overlapping intervals.

2. Loop through the given set of intervals. At each iteration, do the following:

   1. If merged is empty or the start of the current interval is greater than the end of the last inserted interval, simply push the current interval into merged.

   2. Else, set the end of the last inserted interval in merged to the maximum of two values: the current interval's end and the last inserted interval's end . This is the case where we deal with overlapping intervals.

Two intervals will overlap if the start of one interval is less than the end of the other. In this case, the merged interval will have the minimum start and the maximum end of the two.

That's all we need to do! Let's take a look at the code now.

Coding Up The Solution

class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {

        bool inserted = false;
        for(int i = 0;i < intervals.size(); i++){
            if(intervals[i][0] >= newInterval[0]){
                intervals.insert(intervals.begin() + i,newInterval);
                inserted = true;
                break;
            }
        }
        if(!inserted){
            intervals.push_back(newInterval);
        }

        vector<vector<int>> merged;

        for(int i = 0;i < intervals.size(); i++){
            //if merged is empty or the current interval doesn't overlap with the last inserted interval
            if(merged.empty() or intervals[i][0] > merged.back()[1]){
                merged.push_back(intervals[i]);
            }
            //if there is an overlap
            else{
                merged.back()[1] = max(intervals[i][1],merged.back()[1]);
            }
        }

        return merged;

    }
};

That's all for today! Hope you learnt something new. Consider subscribing to my newsletter so you get notified whenever I post a new article!

Cheers!