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]]
Java Solution:
ALSO CHECK: Other LeetCode Solutions in Java
-K Himaanshu Shuklaa.
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 CHECK: Other LeetCode Solutions in Java
-K Himaanshu Shuklaa.
sir pls explannation bhi upload kro solution ka
ReplyDeleteSorry!
DeletePlease check now.