Eliminaciones mínimas requeridas para que los rangos no se superpongan

Dada una lista de rangos con valor inicial y final, la tarea es encontrar la cantidad mínima de rangos que se requieren eliminar para que los rangos restantes no se superpongan.

Ejemplos:

Entrada: entrada = {{1, 2}, {4, 7}, {3, 8}}
Salida: 1
Explicación: La eliminación de {3, 8} hace que {{1, 2} y {4, 7}} no -superposición.

Entrada: entrada = {{ 10, 20 }, { 10, 20 } , { 10, 20 }}
Salida: 2
Explicación: La eliminación de [10, 20] hace que los rangos restantes no se superpongan.

Entrada: entrada = {{1, 2}, {5, 10}, {18, 35}, {40, 45}}
Salida: 0
Explicación: Todos los rangos ya no se superponen.

Acercarse:

• Ordene los rangos por sus valores iniciales.
• Recorra los rangos y verifique si algún rango tiene un punto inicial menor que el punto final del anterior (es decir, hay una superposición).
• Elimina el rango con mayor punto final.

El siguiente código es la implementación del enfoque anterior:

C++

#include <bits/stdc++.h> using namespace std;    int minRemovals(vector<vector<int> >& ranges) {        int size = ranges.size(), rem = 0;        if (size <= 1)         return 0;        // Sort by minimum starting point     sort(ranges.begin(), ranges.end(),          [](const vector<int>& a, const vector<int>& b)                      { return a[0] < b[0]; });        int end = ranges[0][1];     for (int i = 1; i < ranges.size(); i++) {            // If the current starting point is less than         // the previous interval's ending point          // (ie. there is an overlap)         if (ranges[i][0] < end) {             // increase rem             rem++;             // Remove the interval             // with the higher ending point             end = min(ranges[i][1], end);         }         else             end = ranges[i][1];     }        return rem; }    // Driver code int main() {     vector<vector<int> > input = { { 19, 25 },                          { 10, 20 }, { 16, 20 } };     cout << minRemovals(input) << endl; }

Python3

def minRemovels (ranges):        size = len(ranges)     rem = 0        # Sort by minimum starting point     ranges.sort()        end = ranges[0][1]     for i in range(1, size):            # If the current starting point is less         # than the previous interval's ending         # point (ie. there is an overlap)         if (ranges[i][0] < end):                # Increase rem             rem += 1                # Remove the interval             # with the higher ending point             end = min(ranges[i][1], end)                        else:             end = ranges[i][1]        return rem    # Driver Code if __name__ == '__main__':            Input = [ [ 19, 25 ],               [ 10, 20 ],               [ 16, 20 ] ]                      print(minRemovels(Input))    # This code is contributed by himanshu77

Producción:

2

Complejidad de tiempo: O(n log n)