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. 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);    }}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);    }}
Counting the overlapping intervals in the union of two sets
java;performance;interview questions;comparative review;interval
BugsI 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 codeYour 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;}