Question : You will be given a collection of intervals. Now you need to merge all the intervals.

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] overlaps, merge them into [1,6]

Brute Force:
First you need to sort all the intervals . Once you sort the given intervals , you are going to linearly iterate all the intervals .Take a new data structure to store all the merged intervals.
Now once you start iterating the above given intervals , first you will get [1,3] and [2,6] , now you will merge it to [1,6] .After that you are going to check for [8,10] so it doesnot lies in [1,6] , now you will have [1,6],[8,10] .Now again [15 ,18] will be added as new interval.
In this case you will be taking one interval and then compare it with all the remaining intervals.
Time complexity : O(n^2)
Space complexity : O(n)

Optimal Solution :
To make it better also first you need to sort all the intervals again.So sort all the intervals .
After sorting take the first pair and store it in pair variable p , now start lineraly iterating the array of intervals . Now take the pointer at first interval now check , if your first interval merges with p , if yes then merge it , now take the second interval and do the same .In the above example , p=[1,3] , now you will merge [1,3] with p then [2,6] with p . For merging you will check right of your p then right of your current interval ,and if it merges you will put p into the new data structure .Now if it doesnot gets merged you will store the current interval as p i.e. in the above example ,[8,10] will become p next .

You will repeat the above steps for the whole array .
Steps :
1.p=first interval
2.start iterating from first interval
3.if your current interval gets merged with p :
if(it[0]<=temp[1])
{
temp[1]=max(it[1],temp[1]);
}
4. if your current interval doesnot get merged :
else
{
ans.push_back(temp);
temp=it;
}

Code :
Function to merge intervals :

vector<vector<int>> merge(vector<vector<int>>& intervals) {

    vector<vector<int>>ans;
    sort(intervals.begin(),intervals.end());
    vector<int>temp=intervals[0];

    for(auto it : intervals)
    {
        if(it[0]<=temp[1])
        {
            temp[1]=max(it[1],temp[1]);
        }
        else
        {
            ans.push_back(temp);
            temp=it;
        }

    }
    ans.push_back(temp);
    return ans;

}

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