Puntos mínimos que se seleccionarán de modo que la eliminación de los segmentos de línea que pasan a través de ellos vacíe la array dada

Dada una array 2D arr[][] , donde cada fila tiene la forma {inicio, fin} que representa los puntos inicial y final de cada segmento de línea en el eje X. En un solo paso, seleccione un punto en el eje X y elimine todos los segmentos de línea que pasan por ese punto. La tarea es encontrar el número mínimo de dichos puntos que deben seleccionarse para eliminar todos los segmentos de línea de la array .

Ejemplos:

Entrada: arr[][]= { {9, 15}, {3, 8}, {1, 6}, {7, 12}, {5,10} } 
Salida: 2 
Explicación: 
Seleccione el punto arr[2 ][1](= (6, 0) en el eje X y elimine los segmentos de línea segundo(= arr[1]), tercero(= arr[2]) y quinto(= arr[4]). 
Seleccione el punto arr[3][1](= (12, 0)) en el eje X y elimine el primer(=arr[0]) y el cuarto(=arr[3]) segmentos de línea 
. cuenta es 2.

Entrada: arr[][]={ {1, 4}, {5, 7}, {9, 13} } 
Salida: 3

Planteamiento: El problema se puede resolver usando la técnica Greedy . Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, diga cntSteps para contar el número total de pasos necesarios para eliminar todos los segmentos de línea.
• Ordene la array arr[][] según los puntos finales de los segmentos de línea .
• Inicialice una variable, diga Points = arr[0][1] para almacenar los puntos del eje X.
• Recorra la array y verifique si el valor de arr[i][0] es mayor que Puntos o no. Si se determina que es cierto, incremente el valor cntSteps en 1 y actualice el valor de Points = arr[i][1] .
• Finalmente, imprima el valor de cntSteps .

// C++ program to implement
// the above approach
 
 
#include <bits/stdc++.h>
using namespace std;
 
 
// Comparator function
bool comp(vector<int> &x, vector<int> y)
{
    return x[1] < y[1];
}
 
 
// Function to count the minimum number of
// steps required to delete all the segments
int cntMinSteps(vector<vector<int> > &arr,
                                   int N)
{
     
 
    // Stores count of steps required
    // to delete all the line segments
    int cntSteps = 1;
     
 
    // Sort the array based on end points
    // of line segments
    sort(arr.begin(), arr.end(), comp);
     
 
    // Stores point on X-axis
    int Points = arr[0][1];
     
 
    // Traverse the array
    for(int i = 0; i < N; i++) {
         
 
        // If arr[1][0] is
        // greater than Points
        if(arr[i][0] > Points) {
             
 
            // Update cntSteps
            cntSteps++;
             
 
            // Update Points
            Points = arr[i][1];
        }
    }
     
    return cntSteps;
     
}
 
 
// Driver Code
int main() {
     
    vector<vector<int> > arr
       = { { 9, 15 }, { 3, 8 },
            { 1, 6 }, { 7, 12 },
                      { 5, 10 } };
                             
    int N = arr.size();
     
    cout<< cntMinSteps(arr, N);
    return 0;
}

// Java program to implement
// the above approach
import java.util.*;
 
class GFG{
 
// Function to sort by column
public static void sortbyColumn(int arr[][],
                                int col)
{
     
    // Using built-in sort function Arrays.sort
    Arrays.sort(arr, new Comparator<int[]>()
    {
        @Override
         
        // Compare values according to columns
        public int compare(final int[] entry1, 
                           final int[] entry2)
        {
             
            // To sort in descending order revert 
            // the '>' Operator
            if (entry1[col] > entry2[col])
                return 1;
            else
                return -1;
        }
    });  // End of function call sort().
}
 
// Function to count the minimum number of
// steps required to delete all the segments
static int cntMinSteps(int[][] arr, int N)
{
     
    // Stores count of steps required
    // to delete all the line segments
    int cntSteps = 1;
     
    // Sort the array based on end points
    // of line segments
    sortbyColumn(arr, 1);
     
    // Stores point on X-axis
    int Points = arr[0][1];
     
    // Traverse the array
    for(int i = 0; i < N; i++)
    {
         
        // If arr[1][0] is
        // greater than Points
        if(arr[i][0] > Points)
        {
             
            // Update cntSteps
            cntSteps++;
             
            // Update Points
            Points = arr[i][1];
        }
    }
    return cntSteps;
}
 
// Driver Code
public static void main(String[] args)
{
    int[][] arr = { { 9, 15 }, { 3, 8 },
                    { 1, 6 }, { 7, 12 },
                    { 5, 10 } };
                             
    int N = arr.length;
     
    System.out.print(cntMinSteps(arr, N));
}
}
 
// This code is contributed by shikhasingrajput

// C# program to implement
 // the above approach
class GFG {
    // A C# Function to sort the array by specified column.
    static public int[,] Sort_By_Column(int [,] array, int [,] sort_directive)
    {
        // number of rows iside array
        int array_rows = array.GetLength(0);
        // number of columns inside array
        int array_columns = array.Length/array_rows;
        // number of columns to be sorted
        int sort_directive_columns = sort_directive.GetLength(0);
        //
        for(int i=0;i<array_rows-1;i++)
        {
            for(int j=i+1;j<array_rows;j++)
            {
                for(int c=0;c<sort_directive_columns;c++)
                {
                    //
                    // sort array values in descending sort order
                    //
                    if(sort_directive[c,1]==-1 &&
                       array[i,sort_directive[c,0]].CompareTo(array[j,sort_directive[c,0]])<0)
                    {
                        //
                        // if values are in ascending sort order
                        // swap values
                        //
                        for(int d=0;d<array_columns;d++)
                        {
                            int h = array[j,d];
                            array[j,d]=array[i,d];
                            array[i,d]=h;
                        }
 
                        break;
                    }
                    //
                    // if values are in correct sort order break
                    //
                    else if(sort_directive[c,1]==-1 &&
                            array[i,sort_directive[c,0]].CompareTo(array[j,sort_directive[c,0]])>0)
                        break;
                    //
                    // sort array values in ascending sort order
                    //
                    else if(sort_directive[c,1]==1 &&
                            array[i,sort_directive[c,0]].CompareTo(array[j,sort_directive[c,0]])>0)
                    {
                        //
                        // if values are in descending sort order
                        // swap values
                        //
                        for(int d=0;d<array_columns;d++)
                        {
                            int h = array[j,d];
                            array[j,d]=array[i,d];
                            array[i,d]=h;
                        }
 
                        break;
                    }
                    //
                    // if values are in correct sort order break
                    //
                    else if(sort_directive[c,1]==1 &&
                            array[i,sort_directive[c,0]].CompareTo(array[j,sort_directive[c,0]])<0)
                        break;
                    //
                    // if values are equal
                    // select next sort directive
                    //
                }
            }
        }
 
        return array;
    }
     
     
    // Function to count the minimum number of
    // steps required to delete all the segments
    static public int cntMinSteps(int [,]arr, int N)
    {
 
        // Stores count of steps required
        // to delete all the line segments
        int cntSteps = 1;
 
        // Sort the array based on end points
        // of line segments
        int [,] SORT_DIRECTIVE=new int[1,2]{
            {1, 1}
        };
        Sort_By_Column(arr, SORT_DIRECTIVE);
         
        // Stores point on X-axis
        int Points = arr[0,1];
 
        // Traverse the array
        for (int i = 0; i < N; i++) {
 
            // If arr[1][0] is
            // greater than Points
            if (arr[i,0] > Points) {
 
                // Update cntSteps
                cntSteps = cntSteps + 1;
 
                // Update Points
                Points = arr[i,1];
            }
        }
 
        return cntSteps;
    }
 
    // Driver code
    static void Main()
    {
        int[,] arr = new int[,]{ { 9, 15 },
                                 { 3, 8 },
                                 { 1, 6 },
                                 { 7, 12 },
                                 { 5, 10 } };
        int N = arr.GetLength(0);
        System.Console.WriteLine(cntMinSteps(arr, N));
    }
}
 
// The code is contributed by Gautam goel (gautamgoel962)

# Python3 program to implement
# the above approach
 
# Comparator function
def comp(x, y):
    return x[1] < y[1]
   
# Function to count the
# minimum number of steps
# required to delete all
# the segments
def cntMinSteps(arr, N):
   
    # Stores count of steps
    # required to delete all
    # the line segments
    cntSteps = 1
 
    # Sort the array based
    # on end points of line
    # segments
    arr.sort(reverse = False)   
 
    # Stores point on X-axis
    Points = arr[0][1]   
 
    # Traverse the array
    for i in range(N):
       
        # If arr[1][0] is
        # greater than Points
        if(arr[i][0] > Points):
           
            # Update cntSteps
            cntSteps += 1
             
            # Update Points
            Points = arr[i][1]
     
    return cntSteps
 
# Driver Code
if __name__ == '__main__':
   
    arr = [[9, 15], [3, 8],
           [1, 6], [7, 12],
           [5, 10]]           
    N = len(arr)
    print(cntMinSteps(arr, N))
 
# This code is contributed by bgangwar59

<script>
 
// JavaScript program to implement
// the above approach
 
// Comparator function
function comp(x, y){
    return x[1] - y[1]
}
 
// Function to count the
// minimum number of steps
// required to delete all
// the segments
function cntMinSteps(arr, N){
 
    // Stores count of steps
    // required to delete all
    // the line segments
    let cntSteps = 1
 
    // Sort the array based
    // on end points of line
    // segments
    arr.sort(comp)
 
    // Stores point on X-axis
    let Points = arr[0][1]
 
    // Traverse the array
    for(let i=0;i<N;i++){
     
        // If arr[1][0] is
        // greater than Points
        if(arr[i][0] > Points){
         
            // Update cntSteps
            cntSteps += 1
             
            // Update Points
            Points = arr[i][1]
        }
    }
     
    return cntSteps
}
 
// Driver Code
 
let    arr = [[9, 15], [3, 8],
        [1, 6], [7, 12],
        [5, 10]]       
let    N = arr.length
document.write(cntMinSteps(arr, N))
 
// This code is contributed by shinjanpatra
 
</script>

2

Complejidad de tiempo: O(N * log(N))  
Espacio auxiliar: O(N)