Distancia mínima tal que por cada cliente haya al menos un proveedor a una distancia dada

Posted on by Rudeus Greyrat

Dados N y M números de puntos en la línea recta, denotan las posiciones de los clientes y vendedores respectivamente. Cada proveedor brinda servicio a todos los clientes, que se encuentran a una distancia que no es más de R del proveedor. La tarea es encontrar el R mínimo tal que para cada cliente haya al menos un vendedor a la distancia que no sea mayor que R .

Ejemplos:

Entrada: N = 3, M = 2, cliente[] = {-2, 2, 4}, vendedor[] = {-3, 0}
Salida: 4
Explicación: 4 es la distancia mínima tal que cada cliente recibe servicio por al menos un proveedor. 

Entrada: N = 5, M = 3, cliente [] = {1, 5, 10, 14, 17}, vendedor [] = {4, 11, 15}
Salida: 3
Explicación: 3 es la distancia mínima tal que cada el cliente recibe servicio de al menos un proveedor.

 

Enfoque: este problema se puede resolver utilizando el enfoque de dos punteros . Siga los pasos a continuación para resolver el problema dado. 

  • Tome dos punteros, i para la array de clientes y j para la array de proveedores.
  • Comience a mover el puntero i y para cada cliente muevo el índice j mientras cliente [i] > proveedor[j ] .
  • Ahora, cuando proveedor[j] >= cliente[i] ,
    • así que verifique la distancia correcta entre ellos, que es vendedor [j] – cliente [i ] si j < m .
    • Compruebe la distancia izquierda, es decir , cliente[i] – vendedor[j – 1] si j > 0 .
    • Encuentre el mínimo de estos dos, es decir, el rango más corto con el que se puede cubrir el cliente[i] ; logrado por la comparación de la distancia de esos dos vendedores adyacentes.
    • Luego maximice esta propiedad tanto como sea posible para obtener la respuesta.
  • Finalmente imprima la respuesta encontrada.

A continuación se muestra la implementación del enfoque anterior.

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.
Producción

4

Complejidad temporal: O(N + M)
Espacio auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por nikhilkumarmishra120 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *