Merge Overlapping Sub-Intervals

In this article, we will solve the problem of merging overlapping sub-intervals. We are given an array of intervals, our task is to merge all the overlapping intervals and return an array of non-overlapping intervals.

Example:

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

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

Explanation: Intervals [1, 3] and [2, 6] overlap and merge to [1, 6]

Solution:

To solve this problem, we will follow these steps:

Steps to Solve:

1.    Sort the Intervals:

o   First, sort the intervals based on the starting point of each interval.

2.    Initialize a Result Vector:

o   Initialize an empty vector to store the merged intervals.

3.    Merge Intervals:

o   Iterate through the sorted intervals.

o   If the current interval overlaps with the last interval in the result vector, merge them by updating the end of the last interval.

o   If there is no overlap, add the current interval to the result vector.

Time Complexity: O(nlogn)

Space Complexity: O(N)