# Counting the overlapping intervals in the union of two sets

I had to recently implement a code to count the union of all intervals (if there are overlapping intervals) for an interview. I was provided with the following function stub:

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

}


A[0] and B[0] form one interval, A[1] and B[1] the next one...and so on.

I tried two approaches.

1. Copying all the intervals to an object and using collections to sort it based on the first value of an interval(Array A[]). But if the number of intervals is large, then is it a good idea to do so?

public class Solution {

class Pair {
private int a,b;
Pair() {}
Pair(int a, int b) {
this.a = a;
this.b = b;
}
public int getA() {
return a;
}
public int getB() {
return b;
}
}

class PairListComparator implements Comparator<Pair> {

@Override
public int compare(Pair o1, Pair o2) {
if(o1.a < o2.a)
return -1;
else if(o1.a > o2.a)
return 1;
else {
if(o1.b < o2.b)
return -1;
else if(o1.b > o2.b)
return 1;
else return 0;
}
}

}

ArrayList<Pair> inputList = new ArrayList<Pair>();

Solution() {

}

public void createInputList(int[] A, int[] B) {
for(int i = 0; i < A.length; i++) {
Pair p = new Pair(A[i], B[i]);
}
PairListComparator plc = new PairListComparator();
Collections.sort(inputList, plc);
}

public int evaluateList() {
int count = 0;
int ptr = 0;
for(int i = 1; i < inputList.size(); i++) {
int firstA = inputList.get(i-1).a;
int firstB = inputList.get(i-1).b;
int secondA = inputList.get(i).a;
int secondB = inputList.get(i).b;
if(secondA < firstB) {
int newB = firstB > secondB ? firstB : secondB;
inputList.set(ptr, new Pair(firstA, newB));
ptr++;
}
else {
count++;
}
}
return count;
}

public int solution(int[] A, int[] B) {
// write your code in Java SE 8
if((A.length != B.length) || (A.length == 0))
return 0;
createInputList(A, B);
return evaluateList();
}

public static void main(String[] args) {
// TODO Auto-generated method stub
Solution s = new Solution();
/*
* [1, 12, 42, 70, 36, -4, 43, 15], [5, 15, 44, 72, 36, 2, 69, 24]
*/
int[] a = {1,12,42,70,36,-4,43,15};
int[] b = {5,15,44,72,36,2,69,24};
int cnt = s.solution(a, b);
System.out.println(cnt);
}

}

2. Implementing my own merge sort on the both the arrays. So sorting based on the first value of all intervals(Array A[]). But this was scored quite low (62%) on the performance scale. What is the best possible solution keeping algorithm efficiency $O(n \log n)$ and space $O(n)$ in worst case?

public class Solution {

public void mergesort(int[] A, int[] B, int[] temp, int[] temp2, int start, int end) {
if(start < end) {
int mid = (start + end)/2;
System.out.println(mid + ":" + start + ":" + end);
mergesort(A, B, temp, temp2, start, mid);
mergesort(A, B, temp, temp2, mid+1, end);
merge(A, B, temp, temp2, start, mid+1, end);
}
}

public void merge(int[] A, int B[], int[] temp, int[] temp2, int start, int mid, int end) {
int leftEnd = mid - 1;
int left = start;
int size = end - start + 1;
int k = start;

while(left <= leftEnd && mid <= end) {
if(A[left] <= A[mid]) {
temp[k] = A[left];
temp2[k] = B[left];
k++; left++;
}
else {
temp[k] = A[mid];
temp2[k] = B[mid];
k++; mid++;
}
}
while(left <= leftEnd) {
temp[k] = A[left];
temp2[k] = B[left];
left++; k++;
}
while(mid <= end) {
temp[k] = A[mid];
temp2[k] = B[mid];
mid++; k++;
}
for(int i = 0; i < size; i++) {
A[end] = temp[end];
B[end] = temp2[end];
end--;
}
}

public int evaluateList(int[] A, int[] B) {
int count = 0;
int ptr = -1;
for(int i = 0; i < A.length; i++) {
if(i != 0 && A[i] <= B[i-1]) {
B[ptr] = B[i-1] > B[i] ? B[i-1] : B[i];
A[ptr] = A[i-1];
}
else {
count++; ptr++;
}
}
return count;
}

public int solution(int[] A, int[] B) {
int[] temp = new int[A.length];
int[] temp2 = new int[A.length];
mergesort(A, B, temp, temp2, 0, A.length-1);
//System.out.println(Arrays.toString(A));
//System.out.println(Arrays.toString(B));
return evaluateList(A, B);
}
}

• Hi, welcome to Codereview. Selecting your code and pressing Control-K indents it making it nicer to read. the backtick may be used for inline code Commented Dec 11, 2015 at 22:23
• Ok, I formatted it for you, but remember Control-K next time :) Commented Dec 11, 2015 at 22:31
• Sorry for the formatting. And thanks for correcting it!
Commented Dec 12, 2015 at 0:03
• why you did not use Arrays.sort ? Commented Jul 19, 2018 at 23:37

# Bugs

I tried this test input:

    int[] a = {1, 10, 30, 60 };
int[] b = {2, 20, 40, 70 };


and your program returned 3. Shouldn't the answer be 4 because there are 4 distinct intervals?

Then I tried this test input:

    int[] a = {1,   10, 30, 60 };
int[] b = {100, 20, 40, 70 };


and your program returned 2. I would have expected the answer to be 1 because the first interval is a superset of all the other intervals.

# Corrected code

Your second implementation seemed to be closer to working than the first. I made the following adjustments to your second implementation to fix the above problems:

public int evaluateList(int[] A, int[] B) {
int count = 1;
int maxB  = B[0];

for (int i = 1; i < A.length; i++) {
if (A[i] <= maxB) {
maxB = maxB > B[i] ? maxB : B[i];
} else {
count++;
maxB = B[i];
}
}
return count;
}
`