Solution For Interval List Intersections

Problem description:

You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. Each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

A closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.

The intersection of two closed intervals is a set of real numbers that is either empty or can be represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].

Example:

Input: firstList = [[0,2],[5,10],[13,23],[24,25]], secondList = [[1,5],[8,12],[15,24],[25,26]] Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

Solution:

The problem can be solved by iterating through both the lists simultaneously, and computing the intersection of the current interval pairs.

To compute the intersection of two intervals, we take the maximum of their start points as the start point of the intersection interval, and the minimum of their end points as the end point of the intersection interval.

We maintain two pointers, i and j, for the two lists. We also maintain an empty list, result, to store the intersection intervals.

We iterate as long as i and j are within their bounds. If the current interval pairs (firstList[i], secondList[j]) intersect, we append the intersection interval to the result list. We then increment the pointer for the interval that ends the earliest. If the current interval pairs do not intersect, we increment the pointer for the interval that ends the earliest.

Once we have finished iterating through the lists, we return the result list.

Here is the Python implementation:

class Solution:
def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
i, j = 0, 0
result = [] while i < len(firstList) and j < len(secondList):
start = max(firstList[i][0], secondList[j][0])
end = min(firstList[i][1], secondList[j][1])
if start <= end:
result.append([start, end])
if firstList[i][1] < secondList[j][1]:
i += 1
else:
j += 1
return result

Time Complexity: O(m+n), where m and n are the lengths of the two input lists.

Space Complexity: O(1), as we are only using constant space to keep track of pointers and result list.

Step by Step Implementation For Interval List Intersections

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class Solution {
    public Interval[] intervalIntersection(Interval[] A, Interval[] B) {
        // check for empty inputs
        if (A == null || A.length == 0 || B == null || B.length == 0) {
            return new Interval[0];
        }
        
        // create a list to store the results
        List result = new ArrayList<>();
        
        // pointers to keep track of the current interval in each array
        int i = 0, j = 0;
        
        // while the pointers have not reached the end of either array
        while (i < A.length && j < B.length) {
            // find the interval with the smaller start time
            Interval a = A[i];
            Interval b = B[j];
            if (a.start <= b.start) {
                // if the end time of the interval with the smaller start time is greater than or equal to the other interval's start time
                // then there is an intersection
                if (a.end >= b.start) {
                    // create a new interval with the maximum start time and the minimum end time
                    result.add(new Interval(Math.max(a.start, b.start), Math.min(a.end, b.end)));
                }
                // if the end time of the interval with the smaller start time is less than the other interval's start time
                // then move on to the next interval in the array with the smaller start time
                else {
                    i++;
                }
            }
            // if the start time of the interval with the smaller start time is greater than the other interval's start time
            // then move on to the next interval in the array with the greater start time
            else {
                j++;
            }
        }
        
        // convert the list to an array and return
        return result.toArray(new Interval[result.size()]);
    }
}

Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

(Formally, a closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.  The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval.  For example, the intersection of [1, 3] and [2, 4] is [2, 3].)

 

Example 1:



Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Reminder: The inputs and the desired output are lists of Interval objects, and not arrays or lists.
 

Note:

0 <= A.length < 1000
0 <= B.length < 1000
0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

# Python Solution

class Solution:
    def intervalIntersection(self, A: List[List[int]], B: List[List[int]]) -> List[List[int]]:
        
        # create empty list to store results
        result = []
        
        # set two pointers, i and j, to keep track of the current interval in each list
        i = 0
        j = 0
        
        # iterate through the intervals in A and B
        # while both pointers are less than the length of their respective lists
        while i < len(A) and j < len(B):
            
            # find the start and end of the intersection of A[i] and B[j]
            # this is done by taking the maximum of the start of A[i] and B[j]
            # and taking the minimum of the end of A[i] and B[j]
            start = max(A[i][0], B[j][0])
            end = min(A[i][1], B[j][1])
            
            # if the start is less than or equal to the end, this means that there is an intersection
            if start <= end:
                # add the intersection to the result list
                result.append([start, end])
            
            # if the end of A[i] is less than the end of B[j], increment i
            # this is because A[i] ends before B[j], so there can't be any more intersections with B[j]
            # we must check the next interval in A
            if A[i][1] < B[j][1]:
                i += 1
            # else, the end of B[j] is less than the end of A[i], so we increment j
            else:
                j += 1
        
        return result

/**
 * @param {number[][]} A
 * @param {number[][]} B
 * @return {number[][]}
 */
var intervalIntersection = function(A, B) {
    // result will store the output
    let result = [];
    // i and j are used as pointers for the respective arrays
    let i = 0;
    let j = 0;
    
    // while loop to iterate through both the arrays
    while(i < A.length && j < B.length) {
        // find the starting point of the intersection
        let start = Math.max(A[i][0], B[j][0]);
        // find the ending point of the intersection
        let end = Math.min(A[i][1], B[j][1]);
        
        // if start is less than end, it means there is an intersection
        // push the intersection into the result array
        if(start <= end) {
            result.push([start, end]);
        }
        
        // if the ending of the first array is less than the second array,
        // it means the first array is finished and we need to move to the next element in the second array
        if(A[i][1] < B[j][1]) {
            i++;
        }
        // else if the ending of the second array is less than the first array,
        // it means the second array is finished and we need to move to the next element in the first array
        else if(A[i][1] > B[j][1]) {
            j++;
        }
        // else if the ending of both the arrays is equal,
        // it means we need to move to the next element in both the arrays
        else {
            i++;
            j++;
        }
    }
    
    return result;
};

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
public:
    vector intervalIntersection(vector& A, vector& B) {
        int i=0,j=0;
        vector result;
        while(i
Given two lists of closed intervals, each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

(Formally, a closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.  The intersection of two closed intervals is a set of real numbers that is either empty, or can be represented as a closed interval.  For example, the intersection of [1, 3] and [2, 4] is [2, 3].)

 

Example 1:



Input: A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]
Output: [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]
Reminder: The inputs and the desired output are lists of Interval objects, and not arrays or lists.
 

Note:

0 <= A.length < 1000
0 <= B.length < 1000
0 <= A[i].start, A[i].end, B[i].start, B[i].end < 10^9
NOTE: input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

public class Solution {
    public int[][] IntervalIntersection(int[][] A, int[][] B) {
        
    }
}