Counting the overlapping intervals in the union of two sets

Question

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]);
               inputList.add(p);
           }
           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);
       }
   }
   

Answer 1

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;
}