# Merge Intervals

In this chapter, we will learn how to merge the given intervals.

#### Problem Statement:

Given a list of intervals, merge all the overlapping intervals to produce a list that has only mutually exclusive intervals.

Example 1:

``````Input: intervals: [[1,4], [2,5], [7,9]]
Output: [[1,5], [7,9]]
Explanation: Since the first two intervals [1,4] and [2,5] overlap, we merged them into
one [1,5].``````

Example 2:

``````Input: intervals: [[6,7], [2,4], [5,9]]
Output: [[2,4], [5,9]]
Explanation: Since the intervals [6,7] and [5,9] overlap, we merged them into one [5,9].``````

Example 3:

``````Input: intervals: [[1,4], [2,6], [3,5]]
Output: [[1,6]]
Explanation: Since all the given intervals overlap, we merged them into one.``````

#### Solution:

Let’s take an example of two intervals (‘a’ and ‘b’) such that a.start <= b.start. There are four possible scenarios:

Our goal is to merge the intervals whenever they overlap. For the above-mentioned three overlapping scenarios (2, 3, and 4), this is how we will merge them:

The diagram above clearly shows a merging approach. Our algorithm will look like this:

1. Sort the intervals on the start time to ensure `a.start <= b.start`.
2. If `a` overlaps `b` (i.e. `b.start <= a.end`), we need to merge them into a new interval `c` such that:
``````c.start = a.start
c.end = max(a.end, b.end)``````

3. We will keep repeating the above two steps to merge `c` with the next interval if it overlaps with `c`.

#### Code:

``````import java.io.*;
import java.util.*;

class Innoskrit {

public static int[][] merge(int[][] intervals) {

if (intervals.length < 2)
return intervals;

// sort the intervals by start time
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> mergedIntervals = new ArrayList<>();

int[] prevInterval = intervals[0];

int i = 1;
while (i < intervals.length) {
int[] interval = intervals[i];
if (interval[0] <= prevInterval[1]) { // overlapping intervals, adjust the 'end'
prevInterval[1] = Math.max(interval[1], prevInterval[1]);
} else { // non-overlapping interval, add the previous interval and reset
prevInterval = interval;
}
i += 1;
}

return mergedIntervals.toArray(new int[mergedIntervals.size()][]);
}

public static void main(String[] args) {
int[][] intervals = new int[][] {{1, 4}, {2, 5}, {7, 9}};
for (int[] interval : Innoskrit.merge(intervals))
System.out.print("[" + interval[0] + "," + interval[1] + "] ");
System.out.println();

intervals = new int[][] {{6, 7}, {2, 4}, {5, 9}};
for (int[] interval : Innoskrit.merge(intervals))
System.out.print("[" + interval[0] + "," + interval[1] + "] ");
System.out.println();

intervals = new int[][] {{1, 4}, {2, 6}, {3, 5}};
for (int[] interval : Innoskrit.merge(intervals))
System.out.print("[" + interval[0] + "," + interval[1] + "] ");
System.out.println();
}
}``````
``````class Innoskrit:

def merge(intervals):

if len(intervals) < 2:
return intervals

# sort the intervals on the start time
intervals.sort(key = lambda x : x[0])

mergedIntervals = []
prev_interval = intervals[0]
for i in range(1, len(intervals)):
interval = intervals[i]
if interval[0] <= prev_interval[1]:  # overlapping intervals, adjust the 'end'
prev_interval[1] = max(interval[1], prev_interval[1])
else:  # non-overlapping interval, add the previous internval and reset
mergedIntervals.append(prev_interval)
prev_interval = interval

mergedIntervals.append(prev_interval)

return mergedIntervals

if __name__ == '__main__':

intervals = [[1, 4], [2, 5], [7, 9]]
for i in Innoskrit.merge(intervals):
print(i, end = " ")
print()

for i in Innoskrit.merge([[6, 7], [2, 4], [5, 9]]):
print(i, end = " ")
print()

for i in Innoskrit.merge([[1, 4], [2, 6], [3, 5]]):
print(i, end = " ")
print()``````
``````#include<bits/stdc++.h>
using namespace std;

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

if (intervals.size() < 2) {
return intervals;
}

// sort the intervals by start time
sort(intervals.begin(), intervals.end(),
[](const vector<int> &x, const vector<int> &y) { return x[0] < y[0]; });

vector<vector<int>> mergedIntervals;

vector<int> prevInterval = intervals[0];
int i = 1;
while (i < intervals.size()) {
vector<int> interval = intervals[i];
if (interval[0] <= prevInterval[1]) {  // overlapping intervals, adjust the 'end'
prevInterval[1] = max(interval[1], prevInterval[1]);
} else {  // non-overlapping interval, add the previous interval and reset
mergedIntervals.push_back(prevInterval);
prevInterval = interval;
}
i += 1;
}

mergedIntervals.push_back(prevInterval);

return mergedIntervals;
}
};

int main(int argc, char *argv[]) {
vector<vector<int>> intervals = {{1, 3}, {2, 5}, {7, 9}};
for (auto interval : Innoskrit::merge(intervals)) {
cout << "[" << interval[0] << "," << interval[1] << "] ";
}
cout << endl;

intervals = {{6, 7}, {2, 4}, {5, 9}};
for (auto interval : Innoskrit::merge(intervals)) {
cout << "[" << interval[0] << "," << interval[1] << "] ";
}
cout << endl;

intervals = {{1, 4}, {2, 6}, {3, 5}};
for (auto interval : Innoskrit::merge(intervals)) {
cout << "[" << interval[0] << "," << interval[1] << "] ";
}
cout << endl;
}``````

Output:

``````[1,5] [7,9]
[2,4] [5,9]
[1,6]``````

#### Time Complexity:

The time complexity of the above algorithm is `O(N * logN)`, where ‘N’ is the total number of intervals. We are iterating the intervals only once which will take `O(N)`, in the beginning though, since we need to sort the intervals, our algorithm will take `O(N * logN)`.

#### Space Complexity:

The space complexity of the above algorithm will be `O(N)` as we need to return a list containing all the merged intervals. We will also need `O(N)` space for sorting. In the case of Java, depending on its version, `Arrays.sort()` either uses Merge sort or Timsort, and both these algorithms need `O(N)` space. Overall, our algorithm has a space complexity of `O(N)`.

#### Innoskrit

We're building a next-level EdTech Startup.