Loading Similar Posts

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)

Entering edit mode

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.

- 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.

```
int solve(int n,int p,vector<int> a)
{
sort(a.begin(),a.end());
int lo=0,hi=2e9+5,ans=-1; // assuming range of ai is 1e9
while(hi >= lo)
{
int mid=(lo+hi)/2;
vector<int> arr(n);
for(int i = 1;i < n;i++)
{
if(a[i]-a[i-1]<=mid)
{
arr[i-1]=1;
arr[i]=1;
}
}
int numPairs=0;
for(int i = 0;i < n;i++)
{
if(arr[i]==0)
continue;
int j=i;
while(j < n && arr[j]==1)
j++;
int cnt=j-i;
numPairs+=cnt/2;
i=j;
}
if(numPairs < p)
lo=mid+1;
else
ans=mid,hi=mid-1;
}
return ans;
}
```

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

Loading Similar Posts