Problem Statement

You are given an array of intervals where intervals[i] = [starti, endi], representing the start and the end of the ith interval. Your task is to merge all overlapping intervals and return an array of the merged intervals such that no two intervals overlap.

Examples

Example 1:

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

Explanation:
    1------3
       2------------6
                       8-----10
                                   15----18
Since interval [1, 3] and [2, 6] overlap, merge them into [1, 6]

Example 2:

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

Explanation:
    1-------------4
                  4----5
              
Intervals [1, 4] and [4, 5] are considered overlapping,
so merge them into [1, 5].

    1------------------5

Different Approaches

1️⃣ Greedy Algorithm with Sorting

Intuition:

• To merge overlapping intervals, we need to process them in sorted order. Sorting intervals by their starting points ensures that once we process an interval, all the next intervals either overlap or start after it.
• We can iterate through the intervals and merge overlapping ones by adjusting the end value of the current interval.

Steps:

1. Sort the intervals based on the start value.
2. Initialize an empty result array.
3. Iterate through the sorted intervals:
   • If the current interval does not overlap with the last interval in the result array, add it to the result.
   • If it overlaps, merge them by updating the end value of the last interval in the result array.
4. Return the result array containing the merged intervals.

Dry Run:

Initialization:

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

Step 1: Sorting:

After sorting the intervals based on the start time, it become as follows:
intervals = [
             [1,3],
             [2,6],
             [8,10],
             [15,18]
            ]

Step 2: Iterating through sorted intervals:

Start with an empty merged list.

First Iteration:
     Process [1, 3]: Since merges is empty, add [1, 3] to merged.

merged = +----------+
         |  [1, 3]  |
         +----------+

Second Iteration:
     Process [2, 6]: It overlaps with [1, 3] because 2 <= 3.
     Merge them with end equal to max[3, 6],
     which would become [1, 6].

merged = +----------+
         |  [1, 6]  |
         +----------+


Third Iteration:
     Process [8, 10]: It does not overlap with the
     [1, 6], so add [8, 10] to merged.

merged = +----------+
         |  [1, 6]  |
         +----------+
         |  [8, 10] | back()
         +----------+

Fourth Iteration:
     Process [15, 18]: It does not overlap with the
     [8, 10], so add [15, 18] to merged.

merged = +----------+
         |  [1, 6]  |
         +----------+
         |  [8, 10] |
         +----------+
         |  [15, 18]| back()
         +----------+

Step 3: Final merged intervals:

merged = [
          [1, 6],
          [8, 10],
          [15, 18]
         ]

Code:

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        // Step 1: Sort intervals by the start value
        sort(intervals.begin(), intervals.end());
        
        vector<vector<int>> merged;
        
        // Step 2: Process each interval
        for (auto interval : intervals) {
            // If the merged array is empty or the current interval doesn't overlap
            // with the previous one, add it to the merged array
            if (merged.empty() || merged.back()[1] < interval[0]) {
                merged.push_back(interval);
            }
            // If there is an overlap, merge the intervals by updating the 'end' of the last interval
            else {
                merged.back()[1] = max(merged.back()[1], interval[1]);
            }
        }
        
        return merged;
    }
};

Complexity Analysis:

• Time Complexity: O(n log n)
  • The sorting step dominates the time complexity, where n is the number of intervals.
  • The merge process itself is O(n) because we go through the sorted intervals only once.
• Space Complexity: O(n)
  • We use extra space for the result array, which in the worst case could contain all the intervals.