Minimum swaps such that at least K points reach target within T time
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.
C++
// C++ code to implement the approach #include <bits/stdc++.h> using namespace std; // Function to return minimum swaps int minimumSwaps( int X[], int V[], int N, int K, int B, int T) { // Initialize the variables int ans = 0; int ts = 0; int r = 0; // Traverse the array from backwards for ( int i = N - 1; i >= 0; i--) { if (r >= K) break ; // Calculate d distance for sheep // on ith index int d = V[i] * T; if (d >= B - X[i]) { ans += ts; r++; } else { ts++; } } // If r>=K then return ans if (r >= K) return ans; // Else return -1 return -1; } // Driver Code int main() { int K = 3, B = 10, T = 5; int X[] = { 0, 2, 5, 6, 7 }; int V[] = { 1, 1, 1, 1, 4 }; int N = sizeof (X) / sizeof (X[0]); // Function call cout << minimumSwaps(X, V, N, K, B, T) << endl; return 0; } |
Java
// Java code to implement the approach import java.io.*; class GFG { // Function to return minimum swaps public static int minimumSwaps( int [] X, int [] V, int N, int K, int B, int T) { // Initialize the variables int ans = 0 ; int ts = 0 ; int r = 0 ; // Traverse the array from backwards for ( int i = N - 1 ; i >= 0 ; i--) { if (r >= K) break ; // Calculate d distance for sheep // on ith index int d = V[i] * T; if (d >= B - X[i]) { ans += ts; r++; } else { ts++; } } // If r>=K then return ans if (r >= K) return ans; // Else return -1 return - 1 ; } // Driver Code public static void main(String[] args) { int K = 3 , B = 10 , T = 5 ; int [] X = { 0 , 2 , 5 , 6 , 7 }; int [] V = { 1 , 1 , 1 , 1 , 4 }; int N = X.length; // Function call System.out.println(minimumSwaps(X, V, N, K, B, T)); } } // This code is contributed by lokesh. |
Python3
# Python code to implement the approach # Function to return minimum swaps def minimumSwaps(X, V, N, K, B, T): # Initialize the variables ans = 0 ts = 0 r = 0 # Traverse the array from backwards for i in range (N - 1 , - 1 , - 1 ): if (r > = K): break # Calculate d distance for sheep # on ith index d = V[i] * T if (d > = B - X[i]): ans = ans + ts r = r + 1 else : ts = ts + 1 # If r>=K then return ans if (r > = K): return ans # Else return -1 return - 1 # Driver Code if __name__ = = '__main__' : K = 3 B = 10 T = 5 X = [ 0 , 2 , 5 , 6 , 7 ] V = [ 1 , 1 , 1 , 1 , 4 ] N = len (X) # Function call print (minimumSwaps(X, V, N, K, B, T)) # This code is contributed by Abhishek Thakur. |
C#
// C# code implementation using System; namespace GFGs { class GFG { static int MinimumSwaps( int [] X, int [] V, int N, int K, int B, int T) { // Initialize the variables int ans = 0; int ts = 0; int r = 0; // Traverse the array from backwards for ( int i = N - 1; i >= 0; i--) { if (r >= K) break ; // Calculate d distance for sheep // on ith index int d = V[i] * T; if (d >= B - X[i]) { ans += ts; r++; } else { ts++; } } // If r>=K then return ans if (r >= K) return ans; // Else return -1 return -1; } static void Main( string [] args) { int K = 3, B = 10, T = 5; int [] X = { 0, 2, 5, 6, 7 }; int [] V = { 1, 1, 1, 1, 4 }; int N = X.Length; // Function call Console.WriteLine(MinimumSwaps(X, V, N, K, B, T)); } } } // This code is contributed by ksam24000 |
Javascript
// JavaScript code to implement the approach // Function to return minimum swaps function minimumSwaps(X, V, N, K, B, T) { // Initialize the variables let ans = 0; let ts = 0; let r = 0; // Traverse the array from backwards for (let i = N - 1; i >= 0; i--) { if (r >= K) break ; // Calculate d distance for sheep // on ith index let d = V[i] * T; if (d >= B - X[i]) { ans += ts; r++; } else { ts++; } } // If r>=K then return ans if (r >= K) return ans; // Else return -1 return -1; } let K = 3,B = 10,T = 5; let X = [0, 2, 5, 6, 7]; let V = [1, 1, 1, 1, 4]; let N = X.length; console.log(minimumSwaps(X, V, N, K, B, T)); // This code is contributed by lokeshmvs21. |
0
Time complexity: O(N)
Auxiliary Space: O(1)
Contact Us