Please do the solution in Java.
Test case: {1,10,8,6,6,2,5,1} should return 4 intersections.
1 Suppose we are given two sets of n points, one set {P1, P2, . . . , Pr} on the line y = 0) and the other set {91, 92, ..., In} on the line y = 1. Consider the n line segments connecting each point pi to the corresponding point qi. Describe and analyze a divide-and-conquer algorithm to determine how many pairs of these line segments intersect, in O(n log n) time. See the example below. 4,944 47 93 P4 P3 PS P, P, PP2 Seven segments with endpoints on parallel lines, with 11 intersecting pairs. Your input consists of two arrays P[1.. n) and Q[1.. n) of e-coordinates; you may assume that all 2n of these numbers are distinct. No proof of correct ness is necessary, but you should justify the running time. Solution: We begin by sorting the array P[1.. n] and permuting the array Q[1.. n] to maintain correspon- dence between endpoints, in O(n log n) time. Then for any indices i
Q[j]. Thus, our goal is to compute the number of pairs of indices i Q[j]. Such a pair is called an inversion. We count the number of inversions in Q using the following extension of mergesort; as a side effect, this algorithm also sorts Q. If n Q[j] where i [n/2] as follows: Color the elements in the Left half Q[1.. n/2] bLue. Color the elements in the Right half Q[n/2 +1.. n] Red. Merge Q[1.. n/2) and Q[n/2 +1.. n), maintaining their colors. For each blue element Q[i], count the number of smaller red elements Q[j]. The last substep can be performed in O(n) time using a simple for-loop: COUNTREDBLUE(A[1.. n]): count=0 total + 0 for it 1 ton if A[i] is red count count +1 else total total + count return total In fact, we can execute the third merge-and-count step directly by modifying the MERGE al- gorithm, without any need for "colors". Here changes to the standard MERGE algorithm are indicated in red. MERGEANDCOUNT2(A[1.. n), m): it 1; i+m+1; total 0 for kr 1 ton if j>n B[k] + A[i]; it i+1; total + total+ j - m - 1 else if i > m B[k] + A[j]; j+j+1 else if A[i] Q[j]. Thus, our goal is to compute the number of pairs of indices i Q[j]. Such a pair is called an inversion. We count the number of inversions in Q using the following extension of mergesort; as a side effect, this algorithm also sorts Q. If n Q[j] where i [n/2] as follows: Color the elements in the Left half Q[1.. n/2] bLue. Color the elements in the Right half Q[n/2 +1.. n] Red. Merge Q[1.. n/2) and Q[n/2 +1.. n), maintaining their colors. For each blue element Q[i], count the number of smaller red elements Q[j]. The last substep can be performed in O(n) time using a simple for-loop: COUNTREDBLUE(A[1.. n]): count=0 total + 0 for it 1 ton if A[i] is red count count +1 else total total + count return total In fact, we can execute the third merge-and-count step directly by modifying the MERGE al- gorithm, without any need for "colors". Here changes to the standard MERGE algorithm are indicated in red. MERGEANDCOUNT2(A[1.. n), m): it 1; i+m+1; total 0 for kr 1 ton if j>n B[k] + A[i]; it i+1; total + total+ j - m - 1 else if i > m B[k] + A[j]; j+j+1 else if A[i]
