Número mínimo de intervalos para cubrir el intervalo objetivo

Dada una array A[] que consta de N intervalos y un intervalo objetivo X , la tarea es encontrar el número mínimo de intervalos de la array A[] dada de modo que cubran por completo el intervalo objetivo. Si no existe tal intervalo, imprima «-1» .

Ejemplos:

Entrada: A[] = {{1, 3}, {2, 4}, {2, 10}, {2, 3}, {1, 1}}, X = {1, 10}
Salida: 2
Explicación:
De los 5 intervalos dados, se pueden seleccionar {1, 3} y {3, 10}. Por lo tanto, los puntos en el rango [1, 3] están cubiertos por el intervalo {1, 3} y los puntos en el rango [4, 10] están cubiertos por el intervalo {2, 10}.

Entrada: A[] = {{2, 6}, {7, 9}, {3, 5}, {6, 10}}, X = {1, 4}
Salida: -1
Explicación: No existe ningún conjunto de intervalos en la array A dada de modo que cubran todo el intervalo objetivo.

Enfoque: el problema dado se puede resolver utilizando un enfoque codicioso . Se puede observar que la elección más óptima del intervalo desde un punto p en el rango objetivo es el intervalo (u, v) tal que u <= p y v es el máximo posible. Usando esta observación, siga los pasos a continuación para resolver el problema dado:

• Ordene la array dada A[] en orden creciente de los puntos iniciales de los intervalos.
• Cree un inicio variable e inicialícelo con el punto de inicio del intervalo objetivo X . Almacena el punto de inicio del intervalo actualmente seleccionado. De manera similar, la variable fin almacena el punto final de la variable actual. Inicialícelo con start – 1 .
• Cree una variable cnt , que almacene el recuento del número de intervalos seleccionados.
• Iterar a través de la array dada A[] usando una variable i .
• Si el punto de inicio del i ^-ésimo intervalo <= inicio, actualice el valor de fin con max(fin, punto final del i ^-ésimo intervalo); de lo contrario, establezca inicio = fin e incremente el valor de cnt en 1 .
• Si el punto inicial del i ^-ésimo intervalo > end o el valor de end ya es mayor que el punto final del intervalo objetivo, rompa el ciclo.
• Devuelve -1 si el valor de end < punto final del intervalo objetivo, de lo contrario, devuelve el valor de cnt .

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 find the minimum number
// of intervals in the array A[] to
// cover the entire target interval
int minimizeSegment(vector<pair<int, int> > A,
                    pair<int, int> X)
{
    // Sort the array A[] in increasing
    // order of starting point
    sort(A.begin(), A.end());
 
    // Insert a pair of INT_MAX to
    // prevent going out of bounds
    A.push_back({ INT_MAX, INT_MAX });
 
    // Stores start of current interval
    int start = X.first;
 
    // Stores end of current interval
    int end = X.first - 1;
 
    // Stores the count of intervals
    int cnt = 0;
 
    // Iterate over all the intervals
    for (int i = 0; i < A.size();) {
 
        // If starting point of current
        // index <= start
        if (A[i].first <= start) {
            end = max(A[i++].second, end);
        }
        else {
 
            // Update the value of start
            start = end;
 
            // Increment the value
            // of count
            ++cnt;
 
            // If the target interval is
            // already covered or it is
            // not possible to move
            // then break the loop
            if (A[i].first > end
                || end >= X.second) {
                break;
            }
        }
    }
 
    // If the entire target interval
    // is not covered
    if (end < X.second) {
        return -1;
    }
 
    // Return Answer
    return cnt;
}
 
// Driver Code
int main()
{
    vector<pair<int, int> > A = {
        { 1, 3 }, { 2, 4 }, { 2, 10 }, { 2, 3 }, { 1, 1 }
    };
    pair<int, int> X = { 1, 10 };
    cout << minimizeSegment(A, X);
 
    return 0;
}

// Java program for the above approach
import java.util.ArrayList;
import java.util.Comparator;
 
class GFG
{
 
  static class Pair
  {
    int first;
    int second;
 
    public Pair(int f, int s)
    {
      this.first = f;
      this.second = s;
    }
  }
 
  // Function to find the minimum number
  // of intervals in the array A[] to
  // cover the entire target interval
  public static int minimizeSegment(ArrayList<Pair> A, Pair X)
  {
 
    // Sort the array A[] in increasing
    // order of starting point
    final Comparator<Pair> arrayComparator = new Comparator<GFG.Pair>() {
      @Override
      public int compare(Pair o1, Pair o2) {
        return Integer.compare(o1.first, o2.first);
      }
    };
 
    A.sort(arrayComparator);
 
    // Insert a pair of INT_MAX to
    // prevent going out of bounds
    A.add(new Pair(Integer.MAX_VALUE, Integer.MIN_VALUE));
 
    // Stores start of current interval
    int start = X.first;
 
    // Stores end of current interval
    int end = X.first - 1;
 
    // Stores the count of intervals
    int cnt = 0;
 
    // Iterate over all the intervals
    for (int i = 0; i < A.size();) {
 
      // If starting point of current
      // index <= start
      if (A.get(i).first <= start) {
        end = Math.max(A.get(i++).second, end);
      } else {
 
        // Update the value of start
        start = end;
 
        // Increment the value
        // of count
        ++cnt;
 
        // If the target interval is
        // already covered or it is
        // not possible to move
        // then break the loop
        if (A.get(i).first > end
            || end >= X.second) {
          break;
        }
      }
    }
 
    // If the entire target interval
    // is not covered
    if (end < X.second) {
      return -1;
    }
 
    // Return Answer
    return cnt;
  }
 
  // Driver Code
  public static void main(String args[]) {
    ArrayList<Pair> A = new ArrayList<Pair>();
    A.add(new Pair(1, 3));
    A.add(new Pair(2, 4));
    A.add(new Pair(2, 10));
    A.add(new Pair(2, 3));
    A.add(new Pair(1, 1));
    Pair X = new Pair(1, 10);
    System.out.println(minimizeSegment(A, X));
  }
}
 
// This code is contributed by saurabh_jaiswal.

# python program for the above approach
 
# Function to find the minimum number
# of intervals in the array A[] to
# cover the entire target interval
def minimizeSegment(A, X):
 
    # Sort the array A[] in increasing
    # order of starting point
 
    A.sort()
 
    # Insert a pair of INT_MAX to
    # prevent going out of bounds
 
    INT_MAX = 2147483647
    A.append([INT_MAX, INT_MAX])
 
    # Stores start of current interval
    start = X[0]
 
    # Stores end of current interval
    end = X[0] - 1
 
    # Stores the count of intervals
    cnt = 0
 
    # Iterate over all the intervals
    for i in range(0, len(A)):
        # If starting point of current
        # index <= start
 
        if (A[i][0] <= start):
            end = max(A[i][1], end)
            i = i + 1
        else:
 
                        # Update the value of start
            start = end
 
            # Increment the value
            # of count
            cnt = cnt + 1
 
            # If the target interval is
            # already covered or it is
            # not possible to move
            # then break the loop
            if (A[i][0] > end or end >= X[1]):
                break
 
        # If the entire target interval
        # is not covered
    if (end < X[1]):
        return -1
 
        # Return Answer
    return cnt
 
 
# Driver Code
if __name__ == "__main__":
    A = [[1, 3], [2, 4], [2, 10], [2, 3], [1, 1]]
 
    X = [1, 10]
 
    print(minimizeSegment(A, X))
     
    # This code is contributed by rakeshsahni

// C# program for the above approach
using System;
using System.Collections.Generic;
 
public class GFG
{
 
  public class Pair
  {
    public int first;
    public int second;
 
    public Pair(int f, int s) {
      this.first = f;
      this.second = s;
    }
  }
 
  // Function to find the minimum number
  // of intervals in the array []A to
  // cover the entire target interval
  public static int minimizeSegment(List<Pair> A, Pair X) {
 
    // Sort the array []A in increasing
    // order of starting point
 
    A.Sort((a,b)=>a.first-b.first);
 
    // Insert a pair of INT_MAX to
    // prevent going out of bounds
    A.Add(new Pair(int.MaxValue, int.MinValue));
 
    // Stores start of current interval
    int start = X.first;
 
    // Stores end of current interval
    int end = X.first - 1;
 
    // Stores the count of intervals
    int cnt = 0;
 
    // Iterate over all the intervals
    for (int i = 0; i < A.Count;) {
 
      // If starting point of current
      // index <= start
      if (A[i].first <= start) {
        end = Math.Max(A[i++].second, end);
      } else {
 
        // Update the value of start
        start = end;
 
        // Increment the value
        // of count
        ++cnt;
 
        // If the target interval is
        // already covered or it is
        // not possible to move
        // then break the loop
        if (A[i].first > end || end >= X.second) {
          break;
        }
      }
    }
 
    // If the entire target interval
    // is not covered
    if (end < X.second) {
      return -1;
    }
 
    // Return Answer
    return cnt;
  }
 
  // Driver Code
  public static void Main(String []args) {
    List<Pair> A = new List<Pair>();
    A.Add(new Pair(1, 3));
    A.Add(new Pair(2, 4));
    A.Add(new Pair(2, 10));
    A.Add(new Pair(2, 3));
    A.Add(new Pair(1, 1));
    Pair X = new Pair(1, 10);
    Console.WriteLine(minimizeSegment(A, X));
  }
}
 
// This code is contributed by Rajput-Ji

<script>
        // JavaScript Program to implement
        // the above approach
 
        // Function to find the minimum number
        // of intervals in the array A[] to
        // cover the entire target interval
        function minimizeSegment(A,
            X)
           {
         
            // Sort the array A[] in increasing
            // order of starting point
            A.sort(function (a, b) { return a.first - b.first; })
 
            // Insert a pair of INT_MAX to
            // prevent going out of bounds
            A.push({ first: Number.MAX_VALUE, second: Number.MAX_VALUE });
 
            // Stores start of current interval
            let start = X.first;
 
            // Stores end of current interval
            let end = X.first - 1;
 
            // Stores the count of intervals
            let cnt = 0;
 
            // Iterate over all the intervals
            for (let i = 0; i < A.length;) {
 
                // If starting point of current
                // index <= start
                if (A[i].first <= start) {
                    end = Math.max(A[i++].second, end);
                }
                else {
 
                    // Update the value of start
                    start = end;
 
                    // Increment the value
                    // of count
                    ++cnt;
 
                    // If the target interval is
                    // already covered or it is
                    // not possible to move
                    // then break the loop
                    if (A[i].first > end
                        || end >= X.second) {
                        break;
                    }
                }
            }
 
            // If the entire target interval
            // is not covered
            if (end < X.second) {
                return -1;
            }
 
            // Return Answer
            return cnt;
        }
 
        // Driver Code
        let A = [{ first: 1, second: 3 },
        { first: 2, second: 4 },
        { first: 2, second: 10 },
        { first: 2, second: 3 },
        { first: 1, second: 1 }
        ];
        let X = { first: 1, second: 10 };
        document.write(minimizeSegment(A, X));
 
     // This code is contributed by Potta Lokesh
 
    </script>

2

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