Intervals Intersection

Problem Statement

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.

Solution

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 Code

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();
    }
}

C++ Code

#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;
} 

Python Code

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()

Output

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

Time Complexity

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.

Space Complexity

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