56. Merge Intervals.md

Merge Intervals

Medium

Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]

Output: [[1,6],[8,10],[15,18]]

Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].

Example 2:

Input: intervals = [[1,4],[4,5]]

Output: [[1,5]]

Explanation: Intervals [1,4] and [4,5] are considered overlapping.

Constraints:

• 1 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

---

Brute Force Approach

Complexity

• Time complexity: O(nlogn) + O(2n)

• Space complexity: O(n)

The steps are as follows:

1. First, we will group the closer intervals by sorting the given array of intervals(if it is not already sorted).
2. After that, we will select one interval at a time using a loop(say i) and insert it into our answer list(if the answer list is empty or the current interval cannot be merged with the last interval of the answer list). While traversing and inserting we will skip the intervals that lie in the last inserted interval of our answer list.
3. Now, for each interval arr[i], using another loop (say j) we are going to check the rest of the intervals(i.e. From index i+1 to n-1) if they can be merged with the selected interval.
4. Inside loop j, we will continue to merge all the intervals that lie in the selected interval. 
   1. **How to check if the current interval can be merged with the selected interval:**We will compare the current interval’s start with the end of the selected interval. If the start is smaller or equal to the end, we can conclude the current interval can be a part of the selected interval. So, we will update the selected interval’s end with the maximum(current interval’s end, selected interval’s end) in the answer list(not in the original array).
5. We will break out of loop j, from the first element that cannot be a part of the selected interval.
   1. How to check if the current interval is not a part of the selected interval: We will compare the current interval’s start with the end of the selected interval. If the start is greater than the end, we can conclude the current interval cannot be a part of the selected interval.
6. Finally, we will return the answer list.

Intuition:

The intuition of this approach is pretty straightforward. We are just grouping close intervals by sorting the given array. After that, we merge an interval with the other by checking if one can be a part of the other interval. For this checking, we are first selecting a particular interval using a loop and then we are comparing the rest of the intervals using another loop.

Code

// Brute Force Approach
// Time complexity -> O(nlogn) + O(2n) and Space -> O(n)
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> ans;
        sort(intervals.begin(),intervals.end());

        for(int i=0;i<intervals.size();i++)
        {
            int start=intervals[i][0];
            int end=intervals[i][1];

            if(!ans.empty() && end<=ans.back()[1])
            {
                continue;
            }
            for(int j=i+1;j<intervals.size();j++)
            {
                if(intervals[j][0]<=end)
                {
                    end=max(end,intervals[j][1]);
                }
                else
                {
                    break;
                }
            }
            ans.push_back({start,end});
        }

        return ans;

    }
};

Time Complexity: O(NlogN) + O(2N), where N = the size of the given array.
Reason: Sorting the given array takes  O(NlogN) time complexity. Now, after that, we are using 2 loops i and j. But while using loop i, we skip all the intervals that are merged with loop j. So, we can conclude that every interval is roughly visited twice(roughly, once for checking or skipping and once for merging). So, the time complexity will be 2N instead of N2.

Space Complexity: O(N), as we are using an answer list to store the merged intervals. Except for the answer array, we are not using any extra space.

Optimized Approach

Complexity

• Time complexity: O(nlogn) + O(n)

• Space complexity: O(n)

Intuition:

In the previous approach, while checking the intervals, we first selected an interval using a loop and then compared it with others using another loop. But in this approach, we will try to do the same using a single loop. Let’s understand how:

We will start traversing the given array with a single loop. At the first index, as our answer list is empty, we will insert the first element into the answer list. While traversing afterward we can find two different cases:

Case 1: If the current interval can be merged with the last inserted interval of the answer list: In this case, we will update the end of the last inserted interval with the maximum(current interval’s end, last inserted interval’s end) and continue moving afterward**.** 

Case 2: If the current interval cannot be merged with the last inserted interval of the answer list: In this case, we will insert the current interval in the answer array as it is. And after this insertion, the last inserted interval of the answer list will obviously be updated to the current interval.

Note: Within the previous approach, we have already discussed how to check if the current interval can or cannot be merged with the other interval.

The steps are as follows:

1. First, we will group the closer intervals by sorting the given array of intervals(if it is not already sorted).
2. After that, we will start traversing the array using a loop(say i) and insert the first element into our answer list(as the answer list is empty).
3. Now, while traversing we will face two different cases:
   1. Case 1: If the current interval can be merged with the last inserted interval of the answer list: In this case, we will update the end of the last inserted interval with the maximum(current interval’s end, last inserted interval’s end) and continue moving afterward**.** 
   2. Case 2: If the current interval cannot be merged with the last inserted interval of the answer list: In this case, we will insert the current interval in the answer array as it is. And after this insertion, the last inserted interval of the answer list will obviously be updated to the current interval.
4. Thus the answer list will be updated with the merged intervals and finally, we will return the answer list.

Since we have sorted the intervals, the intervals which will be merging are bound to be adjacent. We kept on merging simultaneously as we were traversing through the array and when the element was non-overlapping we simply inserted the element in our answer list.

Code

// Optimized Approach
// Time complexity -> O(nlogn) + O(n) and Space -> O(n)
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> ans;
        sort(intervals.begin(),intervals.end());

        for(int i=0;i<intervals.size();i++)
        {
            if(ans.empty() || ans.back()[1] < intervals[i][0])
            {
                ans.push_back(intervals[i]);
            }
            else
            {
                ans.back()[1]=max(ans.back()[1],intervals[i][1]);
            }
        }
        return ans;
    }
};

Time Complexity: O(NlogN) + O(N), where N = the size of the given array.
Reason: Sorting the given array takes  O(NlogN) time complexity. Now, after that, we are just using a single loop that runs for N times. So, the time complexity will be O(N).

Space Complexity: O(N), as we are using an answer list to store the merged intervals. Except for the answer array, we are not using any extra space.

Important Links

1. Solution Link
2. Video Link