#LeetCode: Interval List Intersections

Also Check: Solutions Of May LeetCoding Challenge (2020)

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].)

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.

Algorithm
Let's understand the Algorithm with the example:
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]]

• We will started iterating both the arrays.
• For each pair we need to find the low and a high value.
• In first iteration our pairs would be [0,2] and [1,5].
• Low would be max between A[i][0] (which is 0) and B[j][0] (which is 1), in this case low will be 1.
• High would be min between A[i][1] (which is 2) and B[j][1] (which is 5), in this case low will be 2.
• When the low is less than our equal to high we will add it in the output array list.
• We will increment i when the 2nd element of 1st pair (i.e 2) is less than 2nd element of 2nd pair (i.e 5), else we will increment j.
• Since we have incremented i, in 2nd iteration our pairs would be [5, 10] and [1,5]. Low would be 5(since 5 > 1) and high would be again 5 (5 < 10). In this case we will increment j because 2nd element of 1st pair (i.e 10) is greater than 2nd element of 2nd pair (i.e 5).
• At the end of iteration we will get the output as [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

GIT URL: Java Solution Of Leet Code's Interval List Intersections problem

Java Solution:

ALSO CHECK: Other LeetCode Solutions in Java

-K Himaanshu Shuklaa.