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); } }
`
may be used for inline code \$\endgroup\$