Insert Interval
You are given a list of ‘N’ non-overlapping intervals (each interval can be represented using two integers ‘start’ and ‘end’), sorted in ascending order (based on ‘start’ values). Your task is to insert a given interval in the list, such that all the intervals are present in sorted order.

In case the given interval overlaps with other intervals, merge all necessary intervals to produce a list containing only non-overlapping intervals.

Example:

Let’s say the list of intervals is: [[1,3], [5,7], [8,12]] and we need to insert the interval [4,6] into the list. [4,6] must be inserted in the second position. After insertion, since [4,6] overlaps with [5,7], we merge them into one interval [4,7]. So, our resulting list is: [[1,3], [4,7], [8,12]]

Input Format:

The first line of input contains an integer ‘T’ representing the number of test cases. The first of every test case contains the positive integer ‘N’ denoting the number of intervals present in the list. Next ‘N’ lines contain two space-separated integers, ‘start’ and ‘end’, denoting the starting and the ending point of the interval present in the list. The next line contains two space-separated integers, start and end, denoting the starting and the ending point of the interval which is to be inserted into the list.

Output Format:

For each test case, return the list after inserting the given interval.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Insert Interval

You are given a list of ‘N’ non-overlapping intervals (each interval can be represented using two integers ‘start’ and ‘end’), sorted in ascending order (based on ‘start’ values). Your task is to insert a given interval in the list, such that all the intervals are present in sorted order.

In case the given interval overlaps with other intervals, merge all necessary intervals to produce a list containing only non-overlapping intervals.

Example:

Let’s say the list of intervals is: [[1,3], [5,7], [8,12]] and we need to insert the interval [4,6] into the list. [4,6] must be inserted in the second position. After insertion, since [4,6] overlaps with [5,7], we merge them into one interval [4,7]. So, our resulting list is:  [[1,3], [4,7], [8,12]]

Input Format:

The first line of input contains an integer ‘T’ representing the number of test cases.

The first of every test case contains the positive integer ‘N’ denoting the number of intervals present in the list.

Next ‘N’ lines contain two space-separated integers, ‘start’ and ‘end’, denoting the starting and the ending point of the interval present in the list. 

The next line contains two space-separated integers, start and end, denoting the starting and the ending point of the interval which is to be inserted into the list.

Output Format:

For each test case, return the list after inserting the given interval.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10 
1 <= N <= 5 * 10^4
1 <= start <= end <= 10^5

Time Limit: 1 sec

Accepted Answer

I didn't have any experience with Python, so I didn't know how to write the syntax.
Step 1: One can do this by using the slice indexing in the list

Accepted Answer

Using Stack

A simple approach to solve this problem is by using a stack.
The idea is to one by one insert the intervals into the stack. At each step, we merge the required intervals and make sure that they remain in sorted order.
In the end, the stack contains the resulting intervals in descending order.
So, we reverse the stack and return the resulting list.

Algorithm:

We start by inserting the given interval into the stack.
Now, iterate over the intervals present in the list:
- Let’s assume that 'CURRENT' stores the current interval in the list and ‘PREVIOUS’ stores the interval presently at the top of the stack.
- If the current interval lies after the previous interval i.e. ‘PREVIOUS.end’ < 'CURRENT.start’, then push the current interval into the stack and move on to the next interval in the list.
- Otherwise, pop the top element (i.e. ‘PREVIOUS’) from the stack.
  - If the previous interval lies after the current interval i.e. ‘PREVIOUS.start’ > ‘CURRENT.end’: then push the current and previous intervals into the stack (in the same order).
  - Otherwise, the two intervals overlap with each other, so merge them and push the new interval into the stack.
Empty the elements of the stack into a list in reverse order.
Return the resulting list.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the length of the list.

O(N) extra space is required for the stack. We are also making an array to store the intervals after inserting the given interval. Thus, overall space complexity is O(N + N) = O(N).

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the length of the list.

We are iterating over the complete list of intervals, which will take O(N) time. Hence, the overall complexity is O(N).

Java (SE 1.8)

/*
    Time Complexity: O(N)
    Space Complexity: O(N)

    where 'N' is the number of intervals in the list.
*/
    
import java.util.*;

public class Solution 
{
    public static ArrayList> insertInterval(ArrayList> intervals, ArrayList newInterval)
    {
        Stack< ArrayList < Integer > > stk = new Stack < ArrayList < Integer > >();

	    // Insert the newInterval into the stack.
	    stk.push(newInterval);

	    for (int i = 0; i < intervals.size(); i++)
	    {
	        ArrayList < Integer > current = intervals.get(i);

	        ArrayList < Integer > previous = stk.peek();

	        if (previous.get(1) < current.get(0))
	        {
	            // Current interval lies after the previous interval.
	            stk.push(current);
	        }
	        else
	        {
	            stk.pop();

	            if (previous.get(0) > current.get(1))
	            {
	                // Previous interval lies after the current interval.
	                stk.push(current);
	                stk.push(previous);
	            }
	            else
	            {
	                // Previous and current intervals overlap. So, merge them.
	                int newStart = Math.min(previous.get(0), current.get(0));
	                int newEnd = Math.max(previous.get(1), current.get(1));

	                ArrayList < Integer > mergedInterval = new ArrayList < Integer > ();
	                mergedInterval.add(newStart);
	                mergedInterval.add(newEnd);

	                stk.push(mergedInterval);
	            }
	        }
	    }

	    int n = stk.size();

	    ArrayList > ans = new ArrayList< ArrayList < Integer > > (n);
        ArrayList < Integer > tmp = new ArrayList < Integer > ();
		for(int i=0;i        	ans.add(tmp);    
        }	
        
	    // Empty the elements of the stack into list in reverse order.
	    for (int i = n - 1; i >= 0; --i)
	    {
	        ans.set(i, stk.peek());
	        stk.pop();
	    }

	    return ans;
    }
}

Python (3.5)

'''

    Time Complexity: O(N)

    Space complexity: O(N)

    

    where N is the number of intervals in the list.

'''





def insertInterval(intervals, newInterval):

    stk = []



    # Insert the newInterval into the stack.

    stk.append(newInterval)



    for i in range(len(intervals)):

        current = intervals[i]

        previous = stk[-1]



        if (previous[1] < current[0]):

            # Current interval lies after the previous interval.

            stk.append(current)

        else:

            stk.pop()



            if (previous[0] > current[1]):

                # Previous interval lies after the current interval.

                stk.append(current)

                stk.append(previous)

            else:

                # Previous and current intervals overlaps. So, merge them.

                newStart = min(previous[0], current[0])

                newEnd = max(previous[1], current[1])

                mergedInterval = [newStart, newEnd]

                stk.append(mergedInterval)



    return stk

C++ (g++ 5.4)

/*
    Time Complexity: O(N)
    Space Complexity: O(N)

    where 'N' is the number of intervals in the list.
*/

#include 

vector> insertInterval(vector> &intervals, vector &newInterval)
{
    stack> stk;

    // Insert the newInterval into the stack.
    stk.push(newInterval);

    for (int i = 0; i < intervals.size(); i++)
    {
        vector current = intervals[i];

        vector previous = stk.top();

        if (previous[1] < current[0])
        {
            // Current interval lies after the previous interval.
            stk.push(current);
        }
        else
        {
            stk.pop();

            if (previous[0] > current[1])
            {
                // Previous interval lies after the current interval.
                stk.push(current);
                stk.push(previous);
            }
            else
            {
                // Previous and current intervals overlap. So, merge them.
                int newStart = min(previous[0], current[0]);
                int newEnd = max(previous[1], current[1]);

                vector mergedInterval = {newStart, newEnd};

                stk.push(mergedInterval);
            }
        }
    }

    int n = stk.size();

    vector> ans(n);

    // Empty the elements of the stack into list in reverse order.
    for (int i = n - 1; i >= 0; --i)
    {
        ans[i] = stk.top();
        stk.pop();
    }

    return ans;
}

Accepted Answer

Traversing and Merging

The previous approach required extra space for the stack. We can avoid this by performing the merge operation in-place.
The idea is to first put all the intervals less than the given interval into a new list.
Then merge all the intervals that intersect with the given interval and add the resulting interval to the new list.
Also, add the remaining intervals, that are greater than the given interval, to the list.
Return the new list of intervals.

Algorithm:

Create an empty list to which will store our resulting list.
Iterate over the intervals present in the list:
- If the current interval’s ending point is less than the starting point of the given interval, then add the current interval to the list.
- Otherwise, break from the loop.
Iterate over the list from where we left off in the previous step:
- Merge all the intervals which overlap with the given interval into a single interval and add it to the list.
Add the remaining intervals to the list.
Return the resulting list.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the length of the list.

O(N) extra space is required for the new list.

Time Complexity: O(n)Explanation:

O(N), where ‘N’ is the length of the list.

We are iterating over the complete list of intervals which will take O(N) time. Hence, the overall complexity is O(N).

Python (3.5)

'''

    Time Complexity: O(N)

    Space complexity: O(N)

    

    where N is the number of intervals in the list.

'''





def insertInterval(intervals, newInterval):

    ans = []



    n = len(intervals)



    index = 0



    # Put all the intervals less than the given interval into the 'ans' list.

    while(index < n and intervals[index][1] < newInterval[0]):

        ans.append(intervals[index])

        index += 1



    # Merge all the intervals which overlap with the given interval, into a single interval.

    while(index < n and intervals[index][0] <= newInterval[1]):

        newInterval[0] = min(newInterval[0], intervals[index][0])

        newInterval[1] = max(newInterval[1], intervals[index][1])



        index += 1



    # Add the mergerd interval to the list.

    ans.append(newInterval)



    # Put all the intervals greater than the given interval into the 'ans' list.

    while(index < n):

        ans.append(intervals[index])

        index += 1



    return ans

Java (SE 1.8)

/*
    Time Complexity: O(N)
    Space Complexity: O(N)

    where 'N' is the number of intervals in the list.
*/
    
import java.util.*;

public class Solution 
{
    public static ArrayList> insertInterval(ArrayList> intervals, ArrayList newInterval)
    {
        ArrayList< ArrayList< Integer > > ans = new ArrayList < ArrayList < Integer > >();

	    int n = intervals.size();

	    int index = 0;

	    // Put all the intervals less than the given interval into the 'ans' list.
	    while (index < n && intervals.get(index).get(1) < newInterval.get(0))
	    {
	        ans.add(intervals.get(index));
	        index++;
	    }

	    // Merge all the intervals which overlap with the given interval, into a single interval.
	    while (index < n && intervals.get(index).get(0) <= newInterval.get(1))
	    {
	        newInterval.set(0, Math.min(newInterval.get(0), intervals.get(index).get(0)));
	        newInterval.set(1, Math.max(newInterval.get(1), intervals.get(index).get(1)));

	        index++;
	    }

	    // Add the mergerd interval to the list.
	    ans.add(newInterval);

	    // Put all the intervals greater than the given interval into the 'ans' list.
	    while (index < n)
	    {
	        ans.add(intervals.get(index));
	        index++;
	    }

	    return ans;
    }
}

C++ (g++ 5.4)

/*
    Time Complexity: O(N)
    Space Complexity: O(N)

    where 'N' is the number of intervals in the list.
*/

vector> insertInterval(vector> &intervals, vector &newInterval)
{
    vector> ans;

    int n = intervals.size();

    int index = 0;

    // Put all the intervals less than the given interval into the 'ans' list.
    while (index < n && intervals[index][1] < newInterval[0])
    {
        ans.push_back(intervals[index]);
        index++;
    }

    // Merge all the intervals which overlap with the given interval, into a single interval.
    while (index < n && intervals[index][0] <= newInterval[1])
    {
        newInterval[0] = min(newInterval[0], intervals[index][0]);
        newInterval[1] = max(newInterval[1], intervals[index][1]);

        index++;
    }

    // Add the mergerd interval to the list.
    ans.push_back(newInterval);

    // Put all the intervals greater than the given interval into the 'ans' list.
    while (index < n)
    {
        ans.push_back(intervals[index]);
        index++;
    }

    return ans;
}

In case the given interval overlaps with other intervals, merge all necessary intervals to produce a list containing only non-overlapping intervals.

Example:

Input Format:

Output Format:

Note:

Constraints:

Top S&P Global Software Developer interview questions & answers

Popular interview questions of Software Developer