In this chapter, we will learn how to find the intersection list of two list of intervals.

3 min read

In this chapter, we will learn how to find the intersection list of two list of intervals.

October 12, 2022

Table Of Contents

Given two lists of intervals, find the **intersection of these two lists**. Each list consists of **disjoint intervals sorted on their start time**.

**Example 1:**

```
Input: arr1 = [[1, 3], [5, 6], [7, 9]], arr2 = [[2, 3], [5, 7]]
Output: [2, 3], [5, 6], [7, 7]
Explanation: The output list contains the common intervals between the two lists.
```

**Example 2:**

```
Input: arr1 = [[1, 3], [5, 7], [9, 12]], arr2 = [[5, 10]]
Output: [5, 7], [9, 10]
Explanation: The output list contains the common intervals between the two lists.
```

This problem follows the Merge Intervals pattern. As we have discussed under Insert Interval, there are four overlapping possibilities between two intervals `a`

and `b`

. A close observation will tell us that whenever the two intervals overlap, one of the interval’s start time lies within the other interval. This rule can help us identify if any two intervals overlap or not.

From the above diagram, the intersection of overlapping interval will be equal to:

```
start = max(a.start, b.start)
end = min(a.end, b.end)
```

So our algorithm will be to iterate through both the lists together to see if any two intervals overlap. If two intervals overlap, we will insert the overlapped part into a result list and move on to the next interval which is finishing early.

Java

Python

C++

```
import java.util.*;
class Innoskrit {
public static int[][] intervalIntersection(int[][] arr1, int[][] arr2) {
List<int[]> ans = new ArrayList<>();
int i = 0, j = 0;
while(i < arr1.length && j < arr2.length) {
int intersection[] = new int[2];
intersection[0] = Math.max(arr1[i][0], arr2[j][0]);
intersection[1] = Math.min(arr1[i][1], arr2[j][1]);
if(intersection[0] <= intersection[1]) {
ans.add(intersection);
}
if(arr1[i][1] < arr2[j][1]) {
i += 1;
} else {
j += 1;
}
}
return ans.toArray(new int[ans.size()][2]);
}
public static void main(String[] args) {
int arr1[][] = new int[][]{{1, 3}, {5, 6}, {7, 9}};
int arr2[][] = new int[][]{{2, 3}, {5, 7}};
for (int[] interval : Innoskrit.intervalIntersection(arr1, arr2))
System.out.print("[" + interval[0] + ", " + interval[1] + "] ");
System.out.println();
}
}
```

```
class Innoskrit:
def intervalIntersection(self, arr1, arr2):
i, j = 0, 0
ans = []
while i < len(arr1) and j < len(arr2):
intersection = []
intersection.append(max(arr1[i][0], arr2[j][0]))
intersection.append(min(arr1[i][1], arr2[j][1]))
if(intersection[0] <= intersection[1]):
ans.append(intersection)
if(arr1[i][1] < arr2[j][1]):
i += 1
else:
j += 1
return ans
if __name__ == "__main__":
arr1 = [[1, 3], [5, 6], [7, 9]]
arr2 = [[2, 3], [5, 7]]
for interval in Innoskrit().intervalIntersection(arr1, arr2):
print(interval, end = " ")
print()
```

```
#include <bits/stdc++.h>
using namespace std;
class Innoskrit {
public:
static vector<vector<int>> intervalIntersection(vector<vector<int>>& arr1, vector<vector<int>>& arr2) {
int i = 0, j = 0;
vector<vector<int>> ans;
while(i < arr1.size() && j < arr2.size()) {
vector<int> intersection;
intersection.push_back(max(arr1[i][0], arr2[j][0]));
intersection.push_back(min(arr1[i][1], arr2[j][1]));
if(intersection[0] <= intersection[1]) {
ans.push_back(intersection);
}
if(arr1[i][1] < arr2[j][1]) {
i += 1;
} else {
j += 1;
}
}
return ans;
}
};
int main() {
vector<vector<int>> arr1 = {{1, 3}, {5, 6}, {7, 9}};
vector<vector<int>> arr2 = {{2, 3}, {5, 7}};
for (auto interval : Innoskrit::intervalIntersection(arr1, arr2)) {
cout << "[" << interval[0] << ", " << interval[1] << "] ";
}
cout << endl;
}
```

**Output**:

`[2, 3] [5, 6] [7, 7] `

As we are iterating through both the lists once, the time complexity of the above algorithm is `O(N + M)`

, where ‘N’ and ‘M’ are the total number of intervals in the input arrays respectively.

Ignoring the space needed for the result list, the algorithm runs in constant space

We're building a next-level EdTech Startup.

© 2022 - All Rights Reserved.