-
Notifications
You must be signed in to change notification settings - Fork 2
/
IntervalListIntersection.java
82 lines (72 loc) · 2.52 KB
/
IntervalListIntersection.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
package Leetcode;
import java.util.ArrayList;
import java.util.List;
/**
* @author kalpak
*
* 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 are either empty or represented as a closed interval.
* For example, the intersection of [1, 3] and [2, 4] is [2, 3].
*
* Example 1:
* 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]]
*
* Example 2:
* Input: firstList = [[1,3],[5,9]], secondList = []
* Output: []
*
* Example 3:
* Input: firstList = [], secondList = [[4,8],[10,12]]
* Output: []
*
* Example 4:
* Input: firstList = [[1,7]], secondList = [[3,10]]
* Output: [[3,7]]
*
* Constraints:
*
* 0 <= firstList.length, secondList.length <= 1000
* firstList.length + secondList.length >= 1
* 0 <= starti < endi <= 109
* endi < starti+1
* 0 <= startj < endj <= 109
* endj < startj+1
*
*/
public class IntervalListIntersection {
public static int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
List<int[]> result = new ArrayList<>();
int i = 0, j = 0;
while(i < firstList.length && j < secondList.length) {
int[] tempA = firstList[i];
int[] tempB = secondList[j];
if(tempA[0] <= tempB[1] && tempB[0] <= tempA[1]) {
// Overlap
result.add(new int[]{Math.max(tempA[0], tempB[0]), Math.min(tempA[1], tempB[1])});
}
if(tempA[1] <= tempB[1]) // current range in A has end-value <= to end-value of the current range in B
i++;
else
j++;
}
return result.toArray(new int[result.size()][]);
}
public static void printResult(int[][] result) {
for(int[] i : result) {
System.out.print("["+i[0]+" "+i[1]+"],");
}
System.out.println();
}
public static void main(String[] args) {
int[][] firstList = new int[][]{{0, 2}, {5, 10}, {13, 23}, {24, 25}};
int[][] secondList = new int[][]{{1, 5}, {8, 12}, {15, 24}, {25, 26}};
printResult(intervalIntersection(firstList, secondList));
}
}