Dada una array arr[] que contiene N enteros y dos enteros X e Y . Considere N segmentos de línea, donde cada segmento de línea tiene un punto inicial y final como arr[i] – X y arr[i] + Y respectivamente.
Dada otra array b[] de M puntos. La tarea es asignar estos puntos a los segmentos de manera que el número de segmentos a los que se les haya asignado un punto sea el máximo. Tenga en cuenta que un punto se puede asignar como máximo a 1 segmento.
Ejemplos:
Entrada: arr[] = {1, 5}, b = {1, 1, 2}, X = 1, Y = 4
Salida: 1
Los segmentos de línea son [1-X, 1+Y], [5-X, 5+Y] es decir, [0, 5] y [4, 9]
El punto 1 se puede asignar al primer segmento [0, 5]
No se pueden asignar puntos al segundo segmento.
Entonces, 2 también se puede asignar al primer segmento, pero no maximizará el no. de segmento
Entonces la respuesta es 1.
Entrada: arr[] = {1, 2, 3, 4}, b = {1, 3, 5}, X = 0, Y = 0
Salida: 2
Enfoque: Ordene ambas arrays de entrada. Ahora, para cada segmento, tratamos de asignarle el primer punto sin asignar posible. Si el segmento actual termina antes que el punto actual, significa que no podremos asignarle ningún punto ya que todos los puntos delante de él son mayores que el punto actual y el segmento ya ha terminado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to return the maximum number of segments
int countPoints(int n, int m, vector<int> a,
vector<int> b, int x, int y)
{
// Sort both the vectors
sort(a.begin(), a.end());
sort(b.begin(), b.end());
// Initially pointing to the first element of b[]
int j = 0;
int count = 0;
for (int i = 0; i < n; i++) {
// Try to find a match in b[]
while (j < m) {
// The segment ends before b[j]
if (a[i] + y < b[j])
break;
// The point lies within the segment
if (b[j] >= a[i] - x && b[j] <= a[i] + y) {
count++;
j++;
break;
}
// The segment starts after b[j]
else
j++;
}
}
// Return the required count
return count;
}
// Driver code
int main()
{
int x = 1, y = 4;
vector<int> a = { 1, 5 };
int n = a.size();
vector<int> b = { 1, 1, 2 };
int m = a.size();
cout << countPoints(n, m, a, b, x, y);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
// Function to return the
// maximum number of segments
static int countPoints(int n, int m, int a[],
int[] b, int x, int y)
{
// Sort both the vectors
Arrays.sort(a);
Arrays.sort(b);
// Initially pointing to the first element of b[]
int j = 0;
int count = 0;
for (int i = 0; i < n; i++)
{
// Try to find a match in b[]
while (j < m)
{
// The segment ends before b[j]
if (a[i] + y < b[j])
break;
// The point lies within the segment
if (b[j] >= a[i] - x && b[j] <= a[i] + y)
{
count++;
j++;
break;
}
// The segment starts after b[j]
else
j++;
}
}
// Return the required count
return count;
}
// Driver code
public static void main(String args[])
{
int x = 1, y = 4;
int[] a = { 1, 5 };
int n = a.length;
int[] b = { 1, 1, 2 };
int m = a.length;
System.out.println(countPoints(n, m, a, b, x, y));
}
}
// This code is contributed by
// Surendra_Gangwar
Python3
# Python3 implementation of the approach # Function to return the maximum # number of segments def countPoints(n, m, a, b, x, y): # Sort both the vectors a.sort() b.sort() # Initially pointing to the first # element of b[] j, count = 0, 0 for i in range(0, n): # Try to find a match in b[] while j < m: # The segment ends before b[j] if a[i] + y < b[j]: break # The point lies within the segment if (b[j] >= a[i] - x and b[j] <= a[i] + y): count += 1 j += 1 break # The segment starts after b[j] else: j += 1 # Return the required count return count # Driver code if __name__ == "__main__": x, y = 1, 4 a = [1, 5] n = len(a) b = [1, 1, 2] m = len(b) print(countPoints(n, m, a, b, x, y)) # This code is contributed by Rituraj Jain
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to return the
// maximum number of segments
static int countPoints(int n, int m, int []a,
int []b, int x, int y)
{
// Sort both the vectors
Array.Sort(a);
Array.Sort(b);
// Initially pointing to the
// first element of b[]
int j = 0;
int count = 0;
for (int i = 0; i < n; i++)
{
// Try to find a match in b[]
while (j < m)
{
// The segment ends before b[j]
if (a[i] + y < b[j])
break;
// The point lies within the segment
if (b[j] >= a[i] - x && b[j] <= a[i] + y)
{
count++;
j++;
break;
}
// The segment starts after b[j]
else
j++;
}
}
// Return the required count
return count;
}
// Driver code
public static void Main()
{
int x = 1, y = 4;
int[] a = {1, 5};
int n = a.Length;
int[] b = {1, 1, 2};
int m = a.Length;
Console.WriteLine(countPoints(n, m, a, b, x, y));
}
}
// This code is contributed by Ryuga
PHP
<?php
// PHP implementation of the approach
// Function to return the maximum number of segments
function countPoints($n, $m, $a, $b, $x, $y)
{
// Sort both the vectors
sort($a);
sort($b);
// Initially pointing to the first element of b[]
$j = 0;
$count = 0;
for ($i = 0; $i < $n; $i++)
{
// Try to find a match in b[]
while ($j < $m)
{
// The segment ends before b[j]
if ($a[$i] + $y < $b[$j])
break;
// The point lies within the segment
if ($b[$j] >= $a[$i] - $x &&
$b[$j] <= $a[$i] + $y)
{
$count++;
$j++;
break;
}
// The segment starts after b[j]
else
$j++;
}
}
// Return the required count
return $count;
}
// Driver code
$x = 1;
$y = 4;
$a = array( 1, 5 );
$n = count($a);
$b = array( 1, 1, 2 );
$m = count($b);
echo countPoints($n, $m, $a, $b, $x, $y);
// This code is contributed by Arnab Kundu
?>
Javascript
<script>
// JavaScript implementation of the approach
// Function to return the
// maximum number of segments
function countPoints(n, m, a, b, x, y)
{
// Sort both the vectors
a.sort(function(a, b){return a - b});
b.sort(function(a, b){return a - b});
// Initially pointing to the
// first element of b[]
let j = 0;
let count = 0;
for (let i = 0; i < n; i++)
{
// Try to find a match in b[]
while (j < m)
{
// The segment ends before b[j]
if (a[i] + y < b[j])
break;
// The point lies within the segment
if (b[j] >= a[i] - x && b[j] <= a[i] + y)
{
count++;
j++;
break;
}
// The segment starts after b[j]
else
j++;
}
}
// Return the required count
return count;
}
let x = 1, y = 4;
let a = [1, 5];
let n = a.length;
let b = [1, 1, 2];
let m = a.length;
document.write(countPoints(n, m, a, b, x, y));
</script>
1
Complejidad de Tiempo: O(N * log(N))
Espacio Auxiliar: O(1), ya que no se ha tomado espacio extra.
Publicación traducida automáticamente
Artículo escrito por Abdullah Aslam y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA