Merge Intervals (With Solution)

Problem Statement

Given N intervals, where each interval denotes startTime and endTime. The task is to merge all overlapping intervals possible and return a list of overlapping intervals in sorted order of their startTime.

Examples:

Input:

Explanation: Provided in the image

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

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

Approach 1: Brute Force

First of all, let us try to understand the different types of intervals possible.

The idea is to try to mark each interval as non-visited and for each intervals which is marked as non-visited, find if another interval exists, which overlaps in any form with the current interval.

If such an interval exists, merge both intervals and mark them visited

C++ Code

```bool isOverlap(int minS, int maxE, vector<int> interval)
{
if (minS > interval[1] || maxE < interval[0])
{
return false;
}

return true;
}

vector<vector<int>> mergeIntervals(vector<vector<int>> &intervals)
{
int n = intervals.size();
vector<vector<int>> res;

vector<bool> vis(n, false);

for (int i = 0; i < n; i++)
{
if (vis[i])
{
continue;
}

vis[i] = true;
int minS = intervals[i][0];
int maxE = intervals[i][1];

while (true)
{
int cnt = 0;

for (int j = 0; j < n; j++)
{
if (!vis[j] && isOverlap(minS, maxE, intervals[j]))
{
vis[j] = true;
minS = min(minS, intervals[j][0]);
maxE = max(maxE, intervals[j][1]);
cnt++;
}
}

if (cnt == 0)
{
break;
}
}

vector<int> interval = {minS, maxE};
res.push_back(interval);
}

sort(res.begin(), res.end());
return res;
}```

Java Code

```public static List < Interval > mergeIntervals(Interval[] intervals) {
int n = intervals.length;
List < Interval > res = new ArrayList();

boolean vis[] = new boolean[n];

for (int i = 0; i < n; i++) {
if (vis[i]) {
continue;
}

vis[i] = true;
int minS = intervals[i].start;
int maxE = intervals[i].finish;

while (true) {
int c = 0;

for (int j = 0; j < n; j++) {
if (!vis[j] && isOverlap(minS, maxE, intervals[j])) {
vis[j] = true;
minS = Math.min(minS, intervals[j].start);
maxE = Math.max(maxE, intervals[j].finish);
c++;
}
}

if (c == 0) {
break;
}
}
}

Collections.sort(res, new Comparator < Interval > () {

public int compare(Interval a, Interval b) {
if (a.start == b.start) {
return a.finish - b.finish;
}

return a.start - b.start;
}

});

return res;
}

public static boolean isOverlap(int minS, int maxE, Interval i) {
if (minS > i.finish || maxE < i.start) {
return false;
}

return true;
}```

Python Code

```def isOverlap(minS, maxE, i):

if minS > i.end or maxE < i.start:
return False

return True

def mergeIntervals(intervals):
n = len(intervals)

res = []

vis = [False for i in range(n)]

for i in range(n):
if vis[i] is True:
continue

vis[i] = True
minS = intervals[i].start
maxE = intervals[i].end

while 1:
cnt = 0

for j in range(n):

if vis[j] is False and isOverlap(minS, maxE, intervals[j]):

vis[j] = True
minS = min(minS, intervals[j].start)
maxE = max(maxE, intervals[j].end)
cnt += 1
if cnt == 0:
break

a = Solution(minS, maxE)
res.append(a)

return res```
• Time Complexity: O(N^2), where N is the total size of the interval array
• Space Complexity: O(N), as visiting array is used.

Approach 2: Sorting

Since we need to merge all the possible intervals, instead of finding if an unvisited interval exists that overlaps the current interval, the intervals can be simply sorted according to their starting time.

This ensures that all the intervals are arranged in a contagious fashion.

Let us understand this with an example :

Algorithm:

• Sort the intervals array according to startTime.
• Create an array to store the merged intervals.
• If the current and previous intervals does not overlap each other, append the current interval to the merged array.
• Else, merge both previous and current intervals and insert it into the merged array.

C++ Code

```vector < vector < int >> merge(vector < vector < int >> & intervals) {
sort(intervals.begin(), intervals.end());

vector < vector < int >> merged;
for (auto interval: intervals) {
if (merged.empty() || merged.back()[1] < interval[0]) {
merged.push_back(interval);
} else {
merged.back()[1] = max(merged.back()[1], interval[1]);
}
}
return merged;
}```

Java Code

``` public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
for (int[] interval : intervals) {
if (merged.isEmpty() || merged.getLast()[1] < interval[0]) {
}
else {
merged.getLast()[1] = Math.max(merged.getLast()[1], interval[1]);
}
}
return merged.toArray(new int[merged.size()][]);
}```

Python Code

```def merge(self, intervals: List[List[int]]) -> List[List[int]]:

intervals.sort(key=lambda x: x[0])

merged = []
for interval in intervals:
if not merged or merged[-1][1] < interval[0]:
merged.append(interval)
else:
merged[-1][1] = max(merged[-1][1], interval[1])

return merged```
• Time Complexity: O(NlogN), where N is the total size of the array
• Space Complexity: O(N), where N is the total size of the merged array

FAQ

Q.1: What is the advantage of sorting the input array according to start time?

Ans: Sorting the input array according to start time ensures that all the intervals are in a contagious manner, and helps in merging without having to search for the whole array again.

Q.2: How are the intervals merged?

Ans: The intervals are merged based on their start time and end time.
Let us consider two intervals [a, b] and [x, y]
Both the intervals overlap, if and only if:  b >= x