Overlapping Intervals

Given an arrayof Intervals arr[][], where arr[i] = [start_i, end_i]. The task is to merge all of the overlapping Intervals.

Examples:

Input: arr[][] = [[1,3],[2,4],[6,8],[9,10]]
Output: [[1,4], [6,8], [9,10]]
Explanation: In the given intervals we have only two overlapping intervals here, [1,3] and [2,4] which on merging will become [1,4]. Therefore we will return [[1,4], [6,8], [9,10]].

Input: arr[][] = [[6,8],[1,9],[2,4],[4,7]]
Output: [[1,9]]
Explanation: In the given intervals all the intervals overlap with the interval [1,9]. Therefore we will return [1,9].

Constraints:
1 ≤ arr.size() ≤ 10⁵
0 ≤ start_i ≤ end_i ≤ 10⁵

Approach 01:

class Solution {
  public:
    vector<vector<int>> mergeOverlap(vector<vector<int>>& intervals) {
        int totalIntervals = intervals.size();
        int intervalSize = intervals[0].size();  // Unused but named for clarity
        vector<vector<int>> mergedIntervals;

        sort(intervals.begin(), intervals.end());
        mergedIntervals.push_back(intervals[0]);

        for (int currentIndex = 1; currentIndex < totalIntervals; currentIndex++) {
            vector<int> lastInterval = mergedIntervals.back();

            if (intervals[currentIndex][0] <= lastInterval[1]) {
                mergedIntervals.back().pop_back();
                mergedIntervals.back().push_back(max(intervals[currentIndex][1], lastInterval[1]));
            } else {
                mergedIntervals.push_back(intervals[currentIndex]);
            }
        }

        return mergedIntervals;
    }
};

class Solution:
    def mergeOverlap(self, intervals):
        totalIntervals = len(intervals)
        mergedIntervals = []

        intervals.sort()
        mergedIntervals.append(intervals[0])

        for currentIndex in range(1, totalIntervals):
            lastInterval = mergedIntervals[-1]

            if intervals[currentIndex][0] <= lastInterval[1]:
                lastInterval[1] = max(intervals[currentIndex][1], lastInterval[1])
            else:
                mergedIntervals.append(intervals[currentIndex])

        return mergedIntervals

Time Complexity

• Sorting:
  • The input intervals are sorted based on their start values.
  • Sorting the intervals takes \(O(n \log n)\), where \(n\) is the number of intervals.
• Traversal:
  • After sorting, the function iterates through the intervals to merge overlapping intervals.
  • This traversal takes \(O(n)\).
• Overall Time Complexity:

  The total time complexity is \(O(n \log n)\), as the sorting step dominates the traversal step.

Space Complexity

• Auxiliary Space for Sorting:

  The sorting step may require \(O(n)\) auxiliary space, depending on the sorting algorithm used (e.g., quicksort or mergesort).

• Output Space:

  The function stores the merged intervals in a new vector, which can hold up to \(O(n)\) intervals in the worst case (no intervals are merged).

• Other Variables:

  Additional variables like lastInterval, currentIndex, and temporary references require \(O(1)\) space.

• Overall Space Complexity:

  The space complexity is \(O(n)\), as the output vector dominates the auxiliary space usage.