Greedy: Shuffle array so that one array element is greater than other array element

Problem Statement:

You are given 2 array of equal size.

You need to rearrange the first array in such a way that at any point of time a[i] > b[i]

Example

Input: A = [2,7,11,15], B = [1,10,4,11]

Output: [2,11,7,15]

Here a[i] is always greater than b[i]

Solution

First we will insert all the elements from array A into a multiset.

Then for every element in array B, we select the smallest element in A that is greater than B[i].

If there is no such element, then we select the smallest number in A.

Time complexity : O(n logn)

Solution in C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<set>

using namespace std;

vector<int> re_arrange_vector(vector<int>& A, vector<int>& B) 
{
  multiset<int> s(begin(A), end(A));

  for (auto i = 0; i < B.size(); ++i) {
    auto p =  s.upper_bound(B[i]);
    if(p == s.end()) p =s.begin();
    A[i] = *p;
    s.erase(p);
  }

  return A;
}


int main()
{
    vector<int> A = {2,7,11,15};
    vector<int> B = {1,10,4,11};
    
    re_arrange_vector(A, B);
    cout<<"The re-arranged array is ";

    for(int i = 0; i < A.size(); i++) {
      cout<<A.at(i)<<" ";
    }
    cout<<endl;
    return 0;
}

Output:

The re-arranged array is 2 11 7 15