Algorithms/IntersectionOfRanges.java at master · manjeersrujan/Algorithms · GitHub

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
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class IntersectionOfRanges {

	public static void main(String[] args) {
		int[][] a = { { 3, 5 }, { 9, 20 } };
		int[][] b = { { 4, 5 }, { 7, 10 }, { 11, 12 }, { 14, 15 }, { 16, 20 } };

		int[][] c = new IntersectionOfRanges().intervalIntersection(a, b);

		for (int i = 0; i < c.length; i++) {
			System.out.println(c[i][0] +"," + c[i][1]);

		}
	}

	public int[][] intervalIntersection(int[][] A, int[][] B) {

		int ca = 0;
		int cb = 0;

		List<int[]> list = new ArrayList<>();

		while (ca < A.length && cb < B.length) {

			if ((A[ca][1] < B[cb][0])) {
				ca++;
			} else if (A[ca][1] == B[cb][0]) {
				int[] ar = { A[ca][1], A[ca][1] };
				list.add(ar);
				ca++;
			} else if (A[ca][0] > B[cb][1]) {
				cb++;
			} else if (A[ca][0] == B[cb][1]) {
				int[] ar = { A[ca][0], A[ca][0] };
				list.add(ar);
				cb++;
			} else if (A[ca][0] <= B[cb][0] && A[ca][1] <= B[cb][1]) {
				int[] ar = { B[cb][0], A[ca][1] };
				list.add(ar);
				ca++;
			} else if (A[ca][0] >= B[cb][0] && A[ca][1] <= B[cb][1]) {
				int[] ar = { A[ca][0], A[ca][1] };
				list.add(ar);
				ca++;
			} else if (A[ca][0] >= B[cb][0] && A[ca][1] >= B[cb][1]) {
				int[] ar = { A[ca][0], B[cb][1] };
				list.add(ar);
				cb++;
			} else if (A[ca][0] <= B[cb][0] && A[ca][1] >= B[cb][1]) {
				int[] ar = { B[cb][0], B[cb][1] };
				list.add(ar);
				cb++;
			} else if (A[ca][0] >= B[cb][0] && A[ca][1] <= B[cb][1]) {
				int[] ar = { A[ca][0], A[ca][1] };
				list.add(ar);
				ca++;
			}

		}

		return list.toArray(new int[list.size()][]);

	}
}