Insert elements from one array to another such that inversions are minimised

Viewed 39

Let say I have array A and B ( always equal size) A = 5 4 2 1

B = 8 3 6 7

I am to insert elements from B in to A while keeping the relative order of A while minimising inversions.

So the answer would be 3 5 4 1 2 6 7 8 (7 inversions)

I have tried sorting B first then poping min(a[0] b[0]) into an array C but cases like A = 99999 1 2 3

B = 5 6 7 8

Gives the wrong 5 6 7 8 99999 1 2 3 (15 inversions)

When the correct is 99999 1 2 3 5 6 7 8 (7 inversions)

I am at a lost please help

0 Answers
Related