7
\$\begingroup\$

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);
        }
    }
    
\$\endgroup\$
4
  • \$\begingroup\$ 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 \$\endgroup\$
    – Caridorc
    Dec 11, 2015 at 22:23
  • \$\begingroup\$ Ok, I formatted it for you, but remember Control-K next time :) \$\endgroup\$
    – Caridorc
    Dec 11, 2015 at 22:31
  • 1
    \$\begingroup\$ Sorry for the formatting. And thanks for correcting it! \$\endgroup\$
    – adz
    Dec 12, 2015 at 0:03
  • \$\begingroup\$ why you did not use Arrays.sort ? \$\endgroup\$ Jul 19, 2018 at 23:37

1 Answer 1

5
\$\begingroup\$

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;
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.