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