Question: Navi OA
0
Entering edit mode
0
Entering edit mode

If it is possible to select P pairs with max instability k then it is definitely possible to select P pairs with instability greater than k . Hence we can do binary search on k which will range from 0 to max(A)-min(A) and for each value of k we can greedily check on the sorted array whether it is possible to select P pairs or not . Overall time complexity would be O(nlogn)

0
Entering edit mode

# Solution

## Description

Given an array of N elements, select P independent pairs out of them such that the max of instability for the selected pair is minimised.

Instability is absolute of difference of elements within the pair.

## Approach

• As we can see, if we select k to be our max instability, if we can select P pairs with k instability, we can select P pairs with instability more than k.
• Hence, we can apply Binary search on max instability here, where mid denotes max instability atmost mid.
• We can sort the array and take only pairs which are adjacent in the sorted array.
• To select P pairs for max instability k, we can just sort the array, and for a contagious segment in which A(i)-A(i-1) <= k, we can select maximum pairs out of them.
• That is, if pairs (1,2),(2,3),(3,4),(4,5),(7,8),(8,9) have abs difference less than k, we can create an array such that if i belongs to any pair, arr[i]=1, else arr[i]=0. Out of contagious 1's in arr, we can select floor(x/2) pairs if x is the length of the contagious 1s.

## C++ Code

``````int solve(int n,int p,vector&lt;int&gt; a)
{
sort(a.begin(),a.end());

int lo=0,hi=2e9+5,ans=-1; // assuming range of ai is 1e9

while(hi &gt;= lo)
{
int mid=(lo+hi)/2;

vector&lt;int&gt; arr(n);

for(int i = 1;i &lt; n;i++)
{
if(a[i]-a[i-1]&lt;=mid)
{
arr[i-1]=1;
arr[i]=1;
}
}

int numPairs=0;

for(int i = 0;i &lt; n;i++)
{
if(arr[i]==0)
continue;
int j=i;

while(j &lt; n &amp;&amp; arr[j]==1)
j++;

int cnt=j-i;
numPairs+=cnt/2;
i=j;
}

if(numPairs &lt; p)
lo=mid+1;
else
ans=mid,hi=mid-1;
}
return ans;
}
``````

Time Complexity : `O(N*log(1e9))`