Merge overlapping interval
Given 'N' number of intervals, where each interval contains two integers denoting the boundaries of the interval. The task is to merge all the overlapping intervals and return the list of merged intervals sorted in ascending order.

Two intervals will be considered to be overlapping if the starting integer of one interval is less than or equal to the finishing integer of another interval, and greater than or equal to the starting integer of that interval.

Example:

for the given 5 intervals - [1,4], [3,5], [6,8], [10,12], [8,9]. Since intervals [1,4] and [3,5] overlap with each other, we will merge them into a single interval as [1,5]. Similarly [6,8] and [8,9] overlaps, we merge them into [6,9]. Interval [10,12] does not overlap with any interval. Final List after merging overlapping intervals: [1,5], [6,9], [10,12]

Input Format:

The first line of input contains an integer 'T' representing the number of the test case. Then the test case follows. The first line of each test case contains an integer 'N', the number of intervals. The second line of the test case contains 'N' integers, the starting integer of 'N' intervals. The third line of the test case contains 'N' integers, the ending integer of 'N' intervals.

Output Format:

For each test case, print 'S' lines, each contains two single space-separated integers 'a', and 'b', where 'S' is the size of the merged array of intervals, 'a' is the start time of an interval and 'b' is the end time of the same interval. Print the output of each test case in a separate line.

Constraints:

1

Question

Merge overlapping interval

Given 'N' number of intervals, where each interval contains two integers denoting the boundaries of the interval. The task is to merge all the overlapping intervals and return the list of merged intervals sorted in ascending order.

Two intervals will be considered to be overlapping if the starting integer of one interval is less than or equal to the finishing integer of another interval, and greater than or equal to the starting integer of that interval.

Example:

for the given 5 intervals - [1,4], [3,5], [6,8], [10,12], [8,9].
Since intervals [1,4] and [3,5] overlap with each other, we will merge them into a single interval as [1,5].

Similarly [6,8] and [8,9] overlaps, we merge them into [6,9].

Interval [10,12] does not overlap with any interval.

Final List after merging overlapping intervals: [1,5], [6,9], [10,12]

Input Format:

The first line of input contains an integer 'T' representing the number of the test case. Then the test case follows.

The first line of each test case contains an integer 'N', the number of intervals.

The second line of the test case contains 'N' integers, the starting integer of 'N' intervals.

The third line of the test case contains 'N' integers, the ending integer of 'N' intervals.

Output Format:

For each test case, print 'S' lines, each contains two single space-separated integers 'a', and 'b', where 'S' is the size of the merged array of intervals, 'a' is the start time of an interval and 'b' is the end time of the same interval.

Print the output of each test case in a separate line.

Constraints:

1 <= T <= 100
1 <= N <= 1000
0 <= start, finish <= 10^9

Where 'T' denotes the number of test cases, 'N' denotes the number of intervals respectively, 'start' and 'finish' are the starting and finishing times for intervals.   

Time Limit: 1 sec

Accepted Answer

1. First I gave him the brute force solution
2. Interviewer asked me to optimize the solution.
3. I gave him the optimized solution and interviewer was happy.

Accepted Answer

Brute Force

We are given the function MERGEINTERVALS(), which takes a 2D vector representing the vector of intervals and returns another 2D vector which is the vector of merged intervals.
We create another function ISOVERLAP() to check if the current interval overlaps with the other interval.
Now we create an empty 2D vector “RES” to store finally merged intervals and another boolean vector “VIS” to mark if the current interval is visited or not.
To begin with, we mark each interval in VIS as false or unvisited.
Now we run a loop for the total number of intervals and find non visited intervals.
For each non-visited interval, if there exists an overlapping interval with the current interval we will merge both intervals,
After merging, we update the current interval with the largest of both intervals and mark them visited.
Every merged interval is then stored in the final 2D vector “RES”.
Finally, we sort “RES” and return it as our answer.

Space Complexity: O(n)Explanation:

O(N), where N is the number of intervals.

In the worst case, we will be using an extra array of size N to mark intervals visited. Hence, the overall space complexity is O(N).

Time Complexity: O(n^2)Explanation:

O(N^2), where N is the number of intervals.

In the worst case, for each interval, we will be checking all other intervals. For the N interval, the overall time complexity is O(N^2).

Java (SE 1.8)

/*

    Time Complexity: O(N^2).

    Space Complexity: O(N)



    where N is the number of Intervals.

*/



import java.util.ArrayList;

import java.util.Comparator;



public class Solution 

{

	static boolean isOverlap(int minS, int maxE, ArrayList interval)  

	{

	    if (minS > interval.get(1) || maxE < interval.get(0))

	    {

	        return false;

	    }



	    return true;

	}



	public static ArrayList> mergeIntervals(ArrayList> intervals) 

    {

	    int n = intervals.size();

	    ArrayList> res = new ArrayList<>();

	    boolean[] vis = new boolean[n];



	    for (int i = 0; i < n; i++)

	    {

            // Check if vis[i] is equal to true

	        if (vis[i])

	        {

	            continue;

	        }



	        vis[i] = true;

	        int minS = intervals.get(i).get(0);

	        int maxE = intervals.get(i).get(1);



	        // While there is new interval keep overlapping we will keep checking all other intervals again.

	        while (true)

	        {

	            int cnt = 0;

				

                // Iterate j from 0 to n

	            for (int j = 0; j < n; j++)

	            {

	                if (!vis[j] && isOverlap(minS, maxE, intervals.get(j)))

	                {

	                    vis[j] = true;

	                    minS = Math.min(minS, intervals.get(j).get(0));

	                    maxE = Math.max(maxE, intervals.get(j).get(1));

	                    cnt++;

	                }

	            }

				

                // Check if cnt is equal to 0

	            if (cnt == 0)

	            {

	                break;

	            }

	        }



	        ArrayList interval = new ArrayList<>();

	        interval.add(minS);

	        interval.add(maxE);

	        res.add(new ArrayList<>(interval));

	    }

        

        // Sort the array res

	    res.sort(new Comparator>() {    

	        @Override

	        public int compare(ArrayList o1, ArrayList o2) 

            {

	            return o1.get(0).compareTo(o2.get(0));

	        }               

	});

        

	    return res;

	}

}

C++ (g++ 5.4)

/*

    Time Complexity: O(N^2).

    Space Complexity: O(N)



    where N is the number of Intervals.

*/



#include 



//Function to check if the current interval overlaps with the other interval

bool isOverlap(int minS, int maxE, vector interval)  

{

    if (minS > interval[1] || maxE < interval[0])

    {

        return false;

    }



    return true;

}



vector> mergeIntervals(vector> intervals)

{

    int n = intervals.size();

    vector> res;

    vector vis(n, false);



    for (int i = 0; i < n; i++)

    {	

        // Check if vis[i] is equal to true

        if (vis[i])

        {

            continue;

        }



        vis[i] = true;

        int minS = intervals[i][0];

        int maxE = intervals[i][1];



        // While there is new interval keep overlapping we will keep checking all other intervals again.

        while (true)

        {

            int cnt = 0;

			

            // Iterate j from 0 to n

            for (int j = 0; j < n; j++)

            {

                if (!vis[j] && isOverlap(minS, maxE, intervals[j]))

                {

                    vis[j] = true;

                    minS = min(minS, intervals[j][0]);

                    maxE = max(maxE, intervals[j][1]);

                    cnt++;

                }

            }

			

            // Check if cnt is equal to 0

            if (cnt == 0)

            {

                break;

            }

        }



        vector interval = {minS, maxE};

        res.push_back(interval);

    }

	

    // Sort the array res

    sort(res.begin(), res.end());

    

    return res;

}

Python (3.5)

'''

    Time Complexity: O(N^2).

    Space Complexity: O(N)



    where N is the number of Intervals.

'''



# Function to check if the current interval overlaps with the other interval

def isOverlap(minS, maxE, interval):



    if (minS > interval[1] or maxE < interval[0]):

        return False



    return True





def mergeIntervals(intervals):



    n = len(intervals)

    res = []

    vis = [False for i in range(n)]



    for i in range(n):

        

        # Check if vis[i] is equal to true

        if (vis[i]):

            continue



        vis[i] = True

        minS = intervals[i][0]

        maxE = intervals[i][1]



        # While there is new interval keep overlapping we will keep checking all other intervals again.

        while (True):



            cnt = 0



            # Iterate j from 0 to n

            for j in range(n):



                if (vis[j] == False and isOverlap(minS, maxE, intervals[j])):

                    vis[j] = True

                    minS = min(minS, intervals[j][0])

                    maxE = max(maxE, intervals[j][1])

                    cnt += 1



            # Check if cnt is equal to 0

            if (cnt == 0):

                break



        interval = [minS, maxE]

        res.append(interval)



    # Sort the array res

    res.sort()

    

    return res

Accepted Answer

Sorting Intervals

Our last approach was very simple and easy, but it’s time complexity was high. We can improve our solution by sorting the intervals and then combine them

We are given the function MERGEINTERVALS(), which takes a 2D vector representing the vector of intervals and returns another 2D vector which is the vector of merged intervals.
We will first sort the intervals by non-decreasing order of their start integers.
We will create a 2D vector “RES” which will be our resultant vector storing all the merged intervals. Now, we will add the first interval to our resultant list.
Now, we will run a loop for the total number of intervals and for each interval, we will check whether the current interval is overlapping with the last interval in our resultant list or not.
If it overlaps with the last interval, we will update the end integer of the last interval in the list by the maximum of the end integers of both overlapping intervals.
If it doesn't overlap, we will add the current interval to the “RES” vector.
Finally, we will return our resultant vector “RES” as our final answer.

Space Complexity: O(1)Explanation:

O(1).

In the worst case, we will be using constant extra space. Hence, the overall space complexity is O(1).

Time Complexity: O(nlogn)Explanation:

O(N*log(N)), where N is the number of intervals.

In the worst case, we will be sorting the intervals(N*log(N)) and for each adjacent interval, we will be merging the overlapping intervals O(N). Hence, the overall time complexity is O(N*log(N)).