7.Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

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] overlaps, 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.

Solution I: (Brute Force)

1.Sorting the intervals. 2. Comparing one interval with every other interval, and maintaining a bool array for already merged intervals.

class Solution
{
public:
    vector<vector<int>> merge(vector<vector<int>> &intervals)
    {

        int l = intervals.size();
        vector<vector<int>> v;
        vector<bool> vi(l);

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

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

            if (vi[i] == 0)
            {
                for (int j = i + 1; j < intervals.size(); j++)
                {
                    if (intervals[i][1] >= intervals[j][0])
                    {
                        start = min(intervals[i][0], intervals[j][0]);
                        end = max(intervals[i][1], intervals[j][1]);

                        intervals[i][0] = start;
                        intervals[i][1] = end;

                        vi[j] = 1;
                    }
                }

                v.push_back({start, end});
            }
        }
        return v;
    }
};

Time Complexity: O(n log n + n^2) , Space Complexity: O(n)

Solution II: (Optimized solution)

Algorithm: 1. Sort all the intervals 2. Traverse the intervals from the 1st interval. If the interval overlaps, merge it. Else Add the current interval to the output.

class Solution
{
public:
    vector<vector<int>> merge(vector<vector<int>> &intervals)
    {

        int l = intervals.size();
        vector<vector<int>> v;

        if (l == 0)
        {
            return v;
        }

        sort(intervals.begin(), intervals.end());
        int index = 0;
        
        for (int i = 1; i < intervals.size(); i++)
        {
            if (intervals[index][1] >= intervals[i][0])
            {
                intervals[index][0] = min(intervals[index][0], intervals[i][0]);
                intervals[index][1] = max(intervals[index][1], intervals[i][1]);
            }
            else
            {
                v.push_back({intervals[index][0], intervals[index][1]});
                index = i;
            }
        }

        v.push_back({intervals[index][0], intervals[index][1]});

        return v;
    }
};

Time Complexity: O(n log n) , Space Complexity: O(1)