DEV Community

loading...

Interval List Intersections - LeetCode

chakrihacker profile image Subramanya Chakravarthy ・1 min read

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

This problem can be divided into two steps, finding intervals from two lists and looping through lists

Let's see what kind of overlaps can occur

types-of-overlaps

From the image the condition for overlap is

overlap-condition

In order to get start and end of the overlapping range

start and end of overlap

Now we need to figure out how to loop through the lists A and B

You can use two pointers technique. See below image to understand better

Two pointers technique

Here's the code

/**
 * @param {number[][]} A
 * @param {number[][]} B
 * @return {number[][]}
 */
var intervalIntersection = function(A, B) {
    let res = new Array()
    let i = 0, j = 0
    while(i < A.length && j < B.length) {
        let lo = Math.max(A[i][0], B[j][0])
        let hi = Math.min(A[i][1], B[j][1])
        if(lo <= hi) {
            res.push([lo, hi])
        }

        if(A[i][1] < B[j][1]) {
            i++ // A length is over go to next one
        } else {
            j++
        }
    }
    return res
};

Discussion

pic
Editor guide