Horje
Minimal distance such that for every customer there is at least one vendor at given distance

Given N and M number of points on the straight line, denoting the positions of the customers and vendors respectively. Each vendor provides service to all customers, which are located at a distance that is no more than R from the vendor. The task is to find minimum R such that for each customer there is at least one vendor at the distance which is no more than R.

Examples:

Input: N = 3, M = 2, customer[] = {-2, 2, 4}, vendor[] = {-3, 0}
Output: 4
Explanation: 4 is the minimum distance such that every customer is given service by at least one vendor. 

Input: N = 5, M = 3, customer [] = {1, 5, 10, 14, 17}, vendor[] = {4, 11, 15}
Output: 3
Explanation: 3 is the minimum distance such that every customer is given service by at least one vendor.

 

Approach: This problem can be solved by using the Two Pointer approach. Follow the steps below to solve the given problem. 

  • Take two pointers, i for the customer array and j for the vendor array.
  • Start moving the i pointer and for every customer i move the j index while customer[i] > vendor[j].
  • Now when vendor[j] >= customer[i],
    • so check the right distance between them which is vendor[j] – customer[i] if j < m.
    • Check the left distance i.e. customer[i] – vendor[j – 1] if j > 0.
    • Find the minimum out of these two i.e the shortest range that the customer[i] can be covered with; achieved by the comparison of the distance of those two adjacent vendors.
    • Then maximize this property as much as possible to get the answer.
  • Finally print the answer found.

Below is the implementation of the above approach.

C++

// C++ program for above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the minimal R.
int findMinDist(int customer[], int vendor[],
                int N, int M)
{
    // Variable to keep track of the minimal r
    int minR = 0;
 
    int i = 0, j = 0;
 
    // Two pointer approach
    while (i < N) {
        if (j < M and vendor[j] < customer[i])
            j++;
        else {
            int left_d = INT_MAX;
            int right_d = INT_MAX;
 
            // Find the distance of customer
            // from left vendor.
            if (j > 0)
                left_d = customer[i]
                         - vendor[j - 1];
 
            // Find the distance of customer
            // from right vendor.
            if (j < M)
                right_d = vendor[j]
                          - customer[i];
 
            // Find the minimum of
            // left_d and right_d.
            int mn_d = min(left_d, right_d);
 
            // Maximize the minimum distance.
            minR = max(minR, mn_d);
 
            // Go to the next customer.
            i++;
        }
    }
    return minR;
}
 
// Driver code
int main()
{
    int customer[] = { -2, 2, 4 };
    int vendor[] = { -3, 0 };
 
    int N = sizeof(customer)
            / sizeof(customer[0]);
    int M = sizeof(vendor)
            / sizeof(vendor[0]);
 
    // Function Call
    cout << findMinDist(customer, vendor,
                        N, M);
 
    return 0;
}

Java

// Java code for the above approach
import java.io.*;
class GFG
{
  static int INT_MAX = 2147483647;
 
  // Function to find the minimal R.
  static int findMinDist(int customer[], int vendor[],
                         int N, int M)
  {
 
    // Variable to keep track of the minimal r
    int minR = 0;
 
    int i = 0, j = 0;
 
    // Two pointer approach
    while (i < N) {
      if (j < M && vendor[j] < customer[i])
        j++;
      else {
        int left_d = INT_MAX;
        int right_d = INT_MAX;
 
        // Find the distance of customer
        // from left vendor.
        if (j > 0)
          left_d = customer[i] - vendor[j - 1];
 
        // Find the distance of customer
        // from right vendor.
        if (j < M)
          right_d = vendor[j] - customer[i];
 
        // Find the minimum of
        // left_d and right_d.
        int mn_d = Math.min(left_d, right_d);
 
        // Maximize the minimum distance.
        minR =Math.max(minR, mn_d);
 
        // Go to the next customer.
        i++;
      }
    }
    return minR;
  }
 
  // Driver code
  public static void main(String[] args)
  {
    int customer[] = { -2, 2, 4 };
    int vendor[] = { -3, 0 };
 
    int N = customer.length;
    int M = vendor.length;
 
    // Function Call
 
    System.out.println(
      findMinDist(customer, vendor, N, M));
  }
}
 
// This code is contributed by Potta Lokesh

Python3

# Python program for above approach
INT_MAX = 2147483647
 
# Function to find the minimal R.
def findMinDist(customer, vendor, N, M):
 
    # Variable to keep track of the minimal r
    minR = 0
 
    i = 0
    j = 0
 
    # Two pointer approach
    while (i < N):
        if (j < M and vendor[j] < customer[i]):
            j += 1
        else:
            left_d = 10 ** 9
            right_d = 10 ** 9
 
            # Find the distance of customer
            # from left vendor.
            if (j > 0):
                left_d = customer[i] - vendor[j - 1]
 
            # Find the distance of customer
            # from right vendor.
            if (j < M):
                right_d = vendor[j] - customer[i]
 
            # Find the minimum of
            # left_d and right_d.
            mn_d = min(left_d, right_d)
 
            # Maximize the minimum distance.
            minR = max(minR, mn_d)
 
            # Go to the next customer.
            i += 1
    return minR
 
# Driver code
customer = [-2, 2, 4]
vendor = [-3, 0]
 
N = len(customer)
M = len(vendor)
 
# Function Call
print(findMinDist(customer, vendor, N, M))
 
# This code is contributed by Saurabh Jaiswal

Javascript

<script>
    // JavaScript program for above approach
    const INT_MAX = 2147483647;
 
    // Function to find the minimal R.
    const findMinDist = (customer, vendor, N, M) => {
     
        // Variable to keep track of the minimal r
        let minR = 0;
 
        let i = 0, j = 0;
 
        // Two pointer approach
        while (i < N) {
            if (j < M && vendor[j] < customer[i])
                j++;
            else {
                let left_d = INT_MAX;
                let right_d = INT_MAX;
 
                // Find the distance of customer
                // from left vendor.
                if (j > 0)
                    left_d = customer[i]
                        - vendor[j - 1];
 
                // Find the distance of customer
                // from right vendor.
                if (j < M)
                    right_d = vendor[j]
                        - customer[i];
 
                // Find the minimum of
                // left_d and right_d.
                let mn_d = Math.min(left_d, right_d);
 
                // Maximize the minimum distance.
                minR = Math.max(minR, mn_d);
 
                // Go to the next customer.
                i++;
            }
        }
        return minR;
    }
 
    // Driver code
    let customer = [-2, 2, 4];
    let vendor = [-3, 0];
 
    let N = customer.length;
    let M = vendor.length;
 
    // Function Call
    document.write(findMinDist(customer, vendor, N, M));
 
    // This code is contributed by rakeshsahni
 
</script>

C#

// C# program to implement
// the above approach
using System;
class GFG
{
  static int INT_MAX = 2147483647;
 
  // Function to find the minimal R.
  static int findMinDist(int []customer, int []vendor,
                         int N, int M)
  {
 
    // Variable to keep track of the minimal r
    int minR = 0;
 
    int i = 0, j = 0;
 
    // Two pointer approach
    while (i < N) {
      if (j < M && vendor[j] < customer[i])
        j++;
      else {
        int left_d = INT_MAX;
        int right_d = INT_MAX;
 
        // Find the distance of customer
        // from left vendor.
        if (j > 0)
          left_d = customer[i] - vendor[j - 1];
 
        // Find the distance of customer
        // from right vendor.
        if (j < M)
          right_d = vendor[j] - customer[i];
 
        // Find the minimum of
        // left_d and right_d.
        int mn_d = Math.Min(left_d, right_d);
 
        // Maximize the minimum distance.
        minR =Math.Max(minR, mn_d);
 
        // Go to the next customer.
        i++;
      }
    }
    return minR;
  }
 
  // Driver code
  public static void Main()
  {
    int []customer = { -2, 2, 4 };
    int []vendor = { -3, 0 };
 
    int N = customer.Length;
    int M = vendor.Length;
 
    // Function Call
 
    Console.WriteLine(
      findMinDist(customer, vendor, N, M));
  }
}
 
// This code is contributed by Samim Hossain Mondal.

 
 

Output

4

Time Complexity: O(N + M)
Auxiliary Space: O(1)


 


Reffered: https://www.geeksforgeeks.org

Greedy

Related
Maximize the value left after reducing the Arrays based on given conditions Maximize the value left after reducing the Arrays based on given conditions
Minimize operations to convert (0, 0) to (N, M) by incrementing either or both by K Minimize operations to convert (0, 0) to (N, M) by incrementing either or both by K
Count of rooks that can attack each other out of K rooks placed on a N*N chessboard Count of rooks that can attack each other out of K rooks placed on a N*N chessboard
Find a permutation of 1 to N, such that A is minimum in left half and B is maximum in right half Find a permutation of 1 to N, such that A is minimum in left half and B is maximum in right half
Total time for which the hero will be in shock Total time for which the hero will be in shock

Type:
 Geek
Category:
 Coding
Sub Category:
 Tutorial
Uploaded by:
 Admin
Views:
 12



 

Horje