Greedy: Insert new interval

Problem Statement:

You are given set of non overlapping interval.

You are given a new interval.

You need to insert the new interval and the intervals are still sorted by ascending order.

Example:

Input: interval = [[1, 3], [6, 10]] new interval = [2, 5]

Output: [[1, 5], [6, 10]]

Solution Explanation:

We will solve the problem by using greedy approach.

A greedy approach makes, locally optimized choices at each step and then leading to a globally optimal solution.

The given array will be sorted at their start times and non overlapping.

So we can use this concept to insert new interval.

We will divide the problem into 3 steps:

Step 1: Identify the interval that end before the new interval starts.

Step 2: Merge all the interval overlap with new interval.

Step 3: Add the remaining interval that start after the new interval ends.

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

Code Solution

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

vector<vector<int>> solution(vector<vector<int>>& intervals, vector<int>& newInterval) 
{
    int n = intervals.size();

    vector<vector<int>> res;
    int i = 0;

    // step 1
    while (i < n && intervals[i][1] < newInterval[0]) 
    {
        res.push_back(intervals[i]);
        i++;
    }

    // step 2
    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++;
    }

    res.push_back(newInterval); \

    // step 3
    while (i < n) 
    {
        res.push_back(intervals[i]);
        i++;
    }

    return res;
}

int main() 
{
    vector<vector<int>> intervals = {{1, 3}, {6, 10}};
    vector<int> newInterval = {2, 5};
    
    vector<vector<int>> res = solution(intervals, newInterval);

  	for (vector<int> interval: res) 
  	{
      	cout << interval[0] << " " << interval[1] << "\n";
    }
    return 0;
}

Output

1 5
6 10