Número máximo de elementos sin superponer en una Línea

Dadas dos arrays X y L del mismo tamaño N . X _i representa la posición en una línea infinita. L _i representa el rango hasta el cual el i-ésimo elemento puede cubrir en ambos lados. La tarea es seleccionar el número máximo de elementos de modo que no se superpongan dos elementos seleccionados si cubren el segmento del lado derecho o izquierdo.
Nota: la array X está ordenada.
Ejemplos: 
 

Entrada: x[] = {10, 15, 19, 20}, L[] = {4, 1, 3, 1} Salida: 4 
Supongamos que 
el primer elemento cubre el segmento del lado izquierdo [6, 10] 
el segundo elemento cubre el lado izquierdo segmento 14, 15] 
El tercer elemento cubre el segmento del lado izquierdo [16, 19] 
El cuarto elemento cubre el segmento del lado derecho [20, 21]
Entrada: x[] = {1, 3, 4, 5, 8}, L[] = { 10, 1, 2, 2, 5} 
Salida: 4 
 

Enfoque: 
Este problema se puede resolver con avidez . Siempre podemos hacer que el primer elemento cubra el segmento izquierdo y el último elemento cubra el segmento derecho. Para los otros elementos primero, intente dar el segmento izquierdo si es posible, de lo contrario intente dar el segmento derecho. Si ninguno de ellos es posible, entonces deje el elemento. 
A continuación se muestra la implementación del enfoque anterior: 
 

// CPP program to find maximum number of
// elements without overlapping in a line
#include <bits/stdc++.h>
using namespace std;
 
// Function to find maximum number of
// elements without overlapping in a line
int Segment(int x[], int l[], int n)
{
    // If n = 1, then answer is one
    if (n == 1)
        return 1;
     
    // We can always make 1st element to cover
    // left segment and nth the right segment
    int ans = 2;
         
         
    for (int i = 1; i < n - 1; i++)
    {
        // If left segment for ith element doesnt overlap
        // with i - 1 th element then do left
        if (x[i] - l[i] > x[i - 1])
            ans++;
 
        // else try towards right if possible
        else if (x[i] + l[i] < x[i + 1])
        {
            // update x[i] to right endpoint of
            // segment covered by it
            x[i] = x[i] + l[i];
            ans++;
        }
    }
     
    // Return the required answer
    return ans;
}
 
// Driver code
int main()
{
    int x[] = {1, 3, 4, 5, 8}, l[] = {10, 1, 2, 2, 5};
     
    int n = sizeof(x) / sizeof(x[0]);
 
    // Function call
    cout << Segment(x, l, n);
 
    return 0;
}

// Java program to find maximum number of
// elements without overlapping in a line
import java.util.*;
 
class GFG
{
 
// Function to find maximum number of
// elements without overlapping in a line
static int Segment(int x[], int l[], int n)
{
    // If n = 1, then answer is one
    if (n == 1)
        return 1;
     
    // We can always make 1st element to cover
    // left segment and nth the right segment
    int ans = 2;
         
    for (int i = 1; i < n - 1; i++)
    {
        // If left segment for ith element
        // doesn't overlap with i - 1 th
        // element then do left
        if (x[i] - l[i] > x[i - 1])
            ans++;
 
        // else try towards right if possible
        else if (x[i] + l[i] < x[i + 1])
        {
            // update x[i] to right endpoint of
            // segment covered by it
            x[i] = x[i] + l[i];
            ans++;
        }
    }
     
    // Return the required answer
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    int x[] = {1, 3, 4, 5, 8},
        l[] = {10, 1, 2, 2, 5};
     
    int n = x.length;
 
    // Function call
    System.out.println(Segment(x, l, n));
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program to find maximum number of
# elements without overlapping in a line
 
# Function to find maximum number of
# elements without overlapping in a line
def Segment(x, l, n):
     
    # If n = 1, then answer is one
    if (n == 1):
        return 1
 
    # We can always make 1st element to cover
    # left segment and nth the right segment
    ans = 2
     
    for i in range(1, n - 1):
         
        # If left segment for ith element doesnt overlap
        # with i - 1 th element then do left
        if (x[i] - l[i] > x[i - 1]):
            ans += 1
 
        # else try towards right if possible
        elif (x[i] + l[i] < x[i + 1]):
             
            # update x[i] to right endpoof
            # segment covered by it
            x[i] = x[i] + l[i]
            ans += 1
 
    # Return the required answer
    return ans
 
# Driver code
x = [1, 3, 4, 5, 8]
l = [10, 1, 2, 2, 5]
 
n = len(x)
 
# Function call
print(Segment(x, l, n))
 
# This code is contributed
# by Mohit Kumar

// C# program to find maximum number of
// elements without overlapping in a line
using System;
     
class GFG
{
 
// Function to find maximum number of
// elements without overlapping in a line
static int Segment(int []x, int []l, int n)
{
    // If n = 1, then answer is one
    if (n == 1)
        return 1;
     
    // We can always make 1st element to cover
    // left segment and nth the right segment
    int ans = 2;
         
    for (int i = 1; i < n - 1; i++)
    {
        // If left segment for ith element
        // doesn't overlap with i - 1 th
        // element then do left
        if (x[i] - l[i] > x[i - 1])
            ans++;
 
        // else try towards right if possible
        else if (x[i] + l[i] < x[i + 1])
        {
            // update x[i] to right endpoint of
            // segment covered by it
            x[i] = x[i] + l[i];
            ans++;
        }
    }
     
    // Return the required answer
    return ans;
}
 
// Driver code
public static void Main(String[] args)
{
    int []x = {1, 3, 4, 5, 8};
    int []l = {10, 1, 2, 2, 5};
     
    int n = x.Length;
 
    // Function call
    Console.WriteLine(Segment(x, l, n));
}
}
 
// This code is contributed by PrinciRaj1992

<script>
 
// JavaScript program to find maximum number of
// elements without overlapping in a line
 
// Function to find maximum number of
// elements without overlapping in a line
function Segment(x, l, n) {
    // If n = 1, then answer is one
    if (n == 1)
        return 1;
 
    // We can always make 1st element to cover
    // left segment and nth the right segment
    let ans = 2;
 
 
    for (let i = 1; i < n - 1; i++) {
        // If left segment for ith element doesnt overlap
        // with i - 1 th element then do left
        if (x[i] - l[i] > x[i - 1])
            ans++;
 
        // else try towards right if possible
        else if (x[i] + l[i] < x[i + 1]) {
            // update x[i] to right endpolet of
            // segment covered by it
            x[i] = x[i] + l[i];
            ans++;
        }
    }
 
    // Return the required answer
    return ans;
}
 
// Driver code
 
let x = [1, 3, 4, 5, 8], l = [10, 1, 2, 2, 5];
 
let n = x.length;
 
// Function call
document.write(Segment(x, l, n));
 
// This code is contributed by _saurabh_jaiswal
 
</script>

Producción:  

 4 

Complejidad de tiempo: O(N)