May 23, 2020

#LeetCode: Interval List Intersections

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

Java Solution:



ALSO CHECKOther LeetCode Solutions in Java

-K Himaanshu Shuklaa.

2 comments: