Minimum swaps such that at least K points reach target within T time – GeeksforGeeks

Given N points moving along the X axis to the right whose initial position and speed are given in two arrays X[] (sorted in increasing order) and V[]. If at any time a point with a higher speed reaches a slow moving point then they will both continue moving with the slower speed. The task is to find out the minimum number of swaps we can perform on two consecutive points such that at least K points reach target B in at most T time.

Note: Swaps can be performed only when two points are next to each other i.e., at x and x+1 in the axis.

Examples:

Input: N = 5, K = 3, B = 10, T = 5, X[] = {0, 2, 5, 6, 7}, V[] = {1, 1, 1, 1, 4}
Output: 0
Explanation: Sheep 5, 4 and 3 will reach the barn before or at 5 secs.

Input: N = 5, K = 3, B = 10, T = 5, X[] = {0, 2, 3, 4, 7}, V[] = {2, 1, 1, 1, 4}
Output: -1
Explanation: At max 2 sheep can reach the barn within or at 5 secs so the answer is -1.

Approach: Follow the below idea to solve the problem:

This problem can be solved using greedy approach. Start checking from the point which is closest to the target. For every point check if that point can reach target in T time. If a point can’t reach the target, it has to be swapped back.

Use the formula distance = speed * time to get which point can reach target at T time .

Follow the below steps to implement the idea:

• Initialize integer variable ans = 0, for counting the number of swaps required.
• Start iterating on the position array backward:
  • For every point get the distance it will travel in T time  
  • Let d be the distance it will travel in T time, if d is at least (B – X[i]), conclude that the point will reach the target in T time. 
  • If there is any point before it that is slower than it and can’t reach the target in time, we have to swap that slow point.
• Keep counter of the point reaching B at time T.
• If the counter gets equal to K, we break out of the loop and return ans.
• If it is not possible to satisfy the condition, return -1.

Below is the implementation of the above approach.

Time complexity: O(N)
Auxiliary Space: O(1)