Comprueba si N líneas dadas pueden intersecarse con K líneas verticales

Dadas N líneas horizontales representadas por una array posición[][] de tamaño N, donde posición[i] representa la i ^-ésima línea horizontal que tiene las coordenadas x desde la posición[i][0] hasta la posición[i][1] y un número entero K, que representa el número máximo de líneas verticales que se pueden dibujar, la tarea es verificar si N líneas dadas pueden ser cortadas por un máximo de K líneas verticales.

Ejemplos:

Entrada: N = 4, K = 2, posición[][] = [[1, 4], [6, 8], [7, 9], [10, 15]]
Salida: NO
Explicación: En el ejemplo dado , dibuje líneas en [1, 7, 10]. La línea trazada en 1 intersecará la primera línea, la línea en la posición 7 intersectará tanto la segunda como la tercera línea, y la línea trazada en 10 intersectará la cuarta línea. Por lo tanto, se requiere un mínimo de 3 varillas. Por lo tanto, no es posible

Entrada: N = 5, K = 3, posición[][] = [[1, 6], [3, 5], [2, 4], [8, 12], [10, 24]]
Salida: SÍ

Enfoque: la idea es utilizar un enfoque codicioso para resolver este problema ordenando la array de posiciones[][] y, con 1 línea, cruzar tantas líneas como sea posible y así sucesivamente. Siga los pasos a continuación para resolver el problema:

• Ordene la posición del arreglo [][] en orden ascendente.
• Inicialice las variables ans como 1 para almacenar la respuesta y r como position[0][1] para almacenar el punto final hasta un punto en particular, otras líneas horizontales pueden ser para la intersección con la línea vertical considerada dada.
• Itere sobre el rango [1, N] usando la variable, digamos I , y realice los siguientes pasos:
  • Si position[i][0] es menor que r, establezca el valor de r al mínimo de r o position[i][1].
  • De lo contrario, agregue el valor de ans por 1 y establezca el valor de r como position[i][1].
• Si k es mayor que igual a ans, imprima «SÍ» y «NO» de lo contrario.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to check if it is possible
// to intersect n lines using k vertical lines
void findIfPossible(int n, int k,
                    vector<vector<int> > position)
{
 
    sort(position.begin(), position.end());
 
    int ans = 1;
 
    // Track the point till a particular
    // vertical line can intersect
    int r = position[0][1];
 
    // Iterate over the range
    for (int i = 1; i < n; i++) {
 
        if (position[i][0] <= r) {
 
            r = min(r, position[i][1]);
        }
 
        else {
 
            ans++;
 
            r = position[i][1];
        }
    }
    if (k >= ans)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}
 
// Driver Code
int main()
{
 
    int n = 5;
    int k = 2;
    vector<vector<int> > position = {
        { 2, 5 }, { 4, 6 }, { 7, 16 }, { 9, 10 }, { 10, 17 }
    };
 
    findIfPossible(n, k, position);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG
{
 
  // Function to check if it is possible
  // to intersect n lines using k vertical lines
  static void findIfPossible(int n, int k,
                             int[][] position)
  {
 
    Arrays.sort(position, Comparator.comparingDouble(o -> o[0]));
 
    int ans = 1;
 
    // Track the point till a particular
    // vertical line can intersect
    int r = position[0][1];
 
    // Iterate over the range
    for (int i = 1; i < n; i++) {
 
      if (position[i][0] <= r) {
 
        r = Math.min(r, position[i][1]);
      }
 
      else {
 
        ans++;
 
        r = position[i][1];
      }
    }
    if (k >= ans)
      System.out.println("YES");
    else
      System.out.println("NO");
  }
 
  // Driver Code
  public static void main(String[] args)
  {
    int n = 5;
    int k = 2;
    int[][] position = {
      { 2, 5 }, { 4, 6 }, { 7, 16 }, { 9, 10 }, { 10, 17 }
    };
 
    findIfPossible(n, k, position);
  }
}
 
// This code is contributed by sanjoy_62.

# python program for the above approach
 
# Function to check if it is possible
# to intersect n lines using k vertical lines
def findIfPossible(n, k, position):
    position.sort()
    ans = 1
 
    # Track the point till a particular
    # vertical line can intersect
    r = position[0][1]
 
    # Iterate over the range
    for i in range(1, n):
        if (position[i][0] <= r):
            r = min(r, position[i][1])
        else:
            ans += 1
            r = position[i][1]
    if (k >= ans):
        print("YES")
    else:
        print("NO")
 
# Driver Code
n = 5
k = 2
position = [[2, 5], [4, 6], [7, 16], [9, 10], [10, 17]]
findIfPossible(n, k, position)
 
# This code is contributed by amreshkumar3

// C# program for the above approach
using System;
 
class GFG{
     
static void Sort(int[,] arr)
{
    for(int i = 0; i < arr.GetLength(0); i++)
    {
        for(int j = arr.GetLength(1) - 1; j > 0; j--)
        {
            for(int k = 0; k < j; k++)
            {
                if (arr[i, k] > arr[i, k + 1])
                {
                    int myTemp = arr[i, k];
                    arr[i, k] = arr[i, k + 1];
                    arr[i, k + 1] = myTemp;
                }
            }
        }
    } 
}
 
// Function to check if it is possible
// to intersect n lines using k vertical lines
static void findIfPossible(int n, int k,
                           int[,] position)
{
    Sort(position);
     
    int ans = 1;
     
    // Track the point till a particular
    // vertical line can intersect
    int r = position[0, 1];
     
    // Iterate over the range
    for(int i = 1; i < n; i++)
    {
        if (position[i, 0] <= r)
        {
            r = Math.Min(r, position[i, 1]);
        }
        else
        {
            ans++;
            r = position[i, 1];
        }
    }
    if (k >= ans)
        Console.Write("YES");
    else
        Console.Write("NO");
}
 
// Driver Code
public static void Main(string[] args)
{
    int n = 5;
    int k = 2;
    int[,] position = { { 2, 5 }, { 4, 6 },
                        { 7, 16 }, { 9, 10 },
                        { 10, 17 } };
     
    findIfPossible(n, k, position);
}
}
 
// This code is contributed by code_hunt

<script>
 
// javascript program for the above approach
 
// Function to check if it is possible
// to intersect n lines using k vertical lines
function findIfPossible(n, k, position)
{
     position = position.sort(function(a, b)
     {
    return a[0]-b[0]
    });
 
    var i;
    var ans = 1;
 
    // Track the point till a particular
    // vertical line can intersect
    var r = position[0][1];
 
    // Iterate over the range
    for (i = 1; i < n; i++) {
 
        if (position[i][0] <= r) {
 
            r = Math.min(r, position[i][1]);
        }
 
        else {
 
            ans++;
 
            r = position[i][1];
        }
    }
    
    if (k >= ans)
        document.write("YES");
    else
        document.write("NO");
}
 
// Driver Code
 
    var n = 5;
    var k = 2;
    var position = [[2, 5],[4, 6], [7, 16],[9, 10],[10, 17]];
 
    findIfPossible(n, k, position);
 
// This code is contributed by SURENDRA_GANGWAR.
</script>

YES

Complejidad temporal: O(NlogN)
Espacio auxiliar: O(1)