Contar puntos cubiertos por intervalos dados

Considere un plano xy infinito. Infinidad de personas caminan sobre el plano en dirección ascendente o + ve Y. En cada punto entero del eje x, solo camina una persona. Supongamos que existen varias barreras paralelas al eje x. Las barreras se proporcionan como tres tríos.

• X1: el punto x en el que comienza la barrera
• X2: el punto x en el que termina la barrera.
• Y: el punto en el eje Y donde se encuentra la barrera.

Calcula cuántas personas se quedarán atrapadas en cualquier punto debido a las barreras. No se permite el uso de espacio adicional para realizar un seguimiento de diferentes puntos en el eje x.

Ejemplos:

Input : barriers[] = {{3 6 2}, {-7 4 3}
Output : 14
The barrier from 3 to 6 blocks 3, 4, 5, 6, 
so 4 persons blocked till now.
The barrier from -7 to 4 blocks -7,-6,-5,-4,-
3, -2, -1, 0, 1, 2, 3, 4. But, 3 and 4 have 
already been blocked.
So, total persons blocked is 14.

Preguntado en: Microsoft IDC Internship.

Un enfoque simple es usar una array muy larga inicializada en cero. Entonces podemos marcar esos valores por 1 que están en la barrera recorriendo cada barrera. Esto solucionaría el caso de superposición de barreras.

Pero no podemos usar otra array como se mencionó anteriormente. Por lo tanto, usamos clasificación y matemáticas simples. Los siguientes son los pasos:

1. Clasificar todas las barreras por x1 (Punto de partida)
2. Después de clasificar, llegan 3 casos:
……I. La siguiente barrera no se superpone con la anterior. En este caso, simplemente sumamos el número de puntos cubiertos por la barrera actual.
……II. La siguiente barrera se superpone parcialmente a la anterior. En este punto añadimos puntos no superpuestos cubiertos por la barrera actual.
……III. La siguiente barrera se superpone completamente a la barrera anterior. En este caso, simplemente ignoramos la barrera actual.

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

// CPP program to find number of people
// that are stopped by barriers
#include <bits/stdc++.h>
using namespace std;
  
struct Barrier
{
    int x1, x2, y;
};
  
// Compares two Barriers according to x1 
bool compareBarrier(Barrier b1, Barrier b2)
{
    return (b1.x1 < b2.x1);
}
  
// Returns number of people blocked by
// array of barriers arr[0..n-1]
int countStopped(Barrier arr[], int n)
{
    // Sort barriers according to x1.
    sort(arr, arr+n, compareBarrier);
  
    // End point of previous barrier
    // Initializing with some value
    // smaller than lowest x1.
    int prev_end = arr[0].x1 - 1;
  
    // Traverse through all bariers
    int count = 0;
    for (int i=0; i<n; i++)
    {
        // If current barrier doesn't overlap
        // with previous
        if (prev_end < arr[i].x1)
        {
            count += (arr[i].x2 - arr[i].x1 + 1);
            prev_end = arr[i].x2;
        }
  
        // If current barrier overlaps and
        // blocks some more people
        else if (prev_end < arr[i].x2)
        {
            count += (arr[i].x2 - prev_end);
            prev_end = arr[i].x2;
        }
    }
  
    return count;
}
  
// Driver code
int main()
{
    Barrier arr[] = {{3, 6, 2}, {-7, 4, 3}};
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << countStopped(arr, n);
    return 0;
}

Producción :

14

Podemos notar fácilmente que no hay importancia de y en la pregunta, por lo que es posible que no se almacene.

Complejidad de tiempo: O (n Log n)

Este artículo es una contribución de Suprotik Dey . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.