Dada una array arr[] que consta de N rangos de la forma {L, R} , la tarea es encontrar el número máximo de rangos de modo que cada rango pueda representarse de manera única por cualquier número entero de ese rango.
Ejemplos:
Entrada: arr[] = {{1, 2}, {2, 3}, {3, 4}}
Salida: 3
Explicación:
El número de rangos se puede maximizar mediante las siguientes representaciones:
- El rango {1, 2} se puede representar con 1.
- El rango {2, 3} se puede representar con 2.
- El rango {3, 4} se puede representar con 3.
Por lo tanto, el recuento de rangos maximizado es 3.
Entrada: arr[] = {{1, 4}, {4, 4}, {2, 2}, {3, 4}, {1, 1}}
Salida: 4
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es ordenar los rangos e iterar desde el valor mínimo de L hasta el valor máximo de R para asignar con avidez un número entero para un rango particular y llevar un conteo de los posibles números enteros asignados. Después de completar los pasos anteriores, imprima el conteo obtenido como resultado.
Complejidad temporal: O(M * N), donde M es el elemento máximo entre los rangos dados .
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede optimizar utilizando el enfoque codicioso , la idea es asignar el valor único mínimo de cada rango seleccionando los rangos dados en orden creciente. Siga los pasos para resolver el problema:
- Ordene la array dada de rangos en orden ascendente .
- Inicialice un vector , digamos prev como arr[] que almacena los valores previamente asignados a los rangos dados.
- Inicialice una variable, digamos contar como 1 para almacenar la cantidad máxima de rangos donde cada rango puede representarse de manera única por un número entero del rango.
- Recorra la array dada arr[] sobre el rango [1, N – 1] y realice los siguientes pasos:
- Inicialice un vector, digamos actual[] como arr[i] que almacena los valores asignados al rango actual.
- Si el valor de max(current[i][1], prev[i][1]) – max(current[i][0], prev[i][0] – 1) es positivo, actualice el valor de anterior como {1 + max(actual[i][0], anterior[i][0] – 1), max(actual[i][1], anterior[i][1])} e incrementa el valor de cuenta por 1 .
- De lo contrario, verifique el siguiente rango.
- Después de completar los pasos anteriores, imprima el valor de conteo como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the maximum number
// of ranges where each range can be
// uniquely represented by an integer
int maxRanges(vector<vector<int> > arr,
int N)
{
// Sort the ranges in ascending order
sort(arr.begin(), arr.end());
// Stores the count of ranges
int count = 1;
// Stores previously assigned range
vector<int> prev = arr[0];
// Traverse the vector arr[]
for (int i = 1; i < N; i++) {
vector<int> last = arr[i - 1];
vector<int> current = arr[i];
// Skip the similar ranges
// of size 1
if (last[0] == current[0]
&& last[1] == current[1]
&& current[1] == current[0])
continue;
// Find the range of integer
// available to be assigned
int start = max(prev[0], current[0] - 1);
int end = max(prev[1], current[1]);
// Check if an integer is
// available to be assigned
if (end - start > 0) {
// Update the previously
// assigned range
prev[0] = 1 + start;
prev[1] = end;
// Update the count of range
count++;
}
}
// Return the maximum count of
// ranges
return count;
}
// Driver Code
int main()
{
vector<vector<int> > range = {
{ 1, 4 }, { 4, 4 },
{ 2, 2 }, { 3, 4 },
{ 1, 1 }
};
int N = range.size();
cout << maxRanges(range, N);
return 0;
}
Java
// java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
public class GFG {
// Function to find the maximum number
// of ranges where each range can be
// uniquely represented by an integer
static int maxRanges(Integer arr[][], int N)
{
// Sort the ranges in ascending order
Arrays.sort(arr, (a, b) -> {
if (a[0].equals(b[0]))
return Integer.compare(a[1], b[1]);
return Integer.compare(a[0], b[0]);
});
// Stores the count of ranges
int count = 1;
// Stores previously assigned range
Integer prev[] = arr[0];
// Traverse the vector arr[]
for (int i = 1; i < N; i++) {
Integer last[] = arr[i - 1];
Integer current[] = arr[i];
// Skip the similar ranges
// of size 1
if (last[0] == current[0]
&& last[1] == current[1]
&& current[1] == current[0])
continue;
// Find the range of integer
// available to be assigned
int start = Math.max(prev[0], current[0] - 1);
int end = Math.max(prev[1], current[1]);
// Check if an integer is
// available to be assigned
if (end - start > 0) {
// Update the previously
// assigned range
prev[0] = 1 + start;
prev[1] = end;
// Update the count of range
count++;
}
}
// Return the maximum count of
// ranges
return count;
}
// Driver Code
public static void main(String[] args)
{
Integer range[][] = {
{ 1, 4 }, { 4, 4 }, { 2, 2 }, { 3, 4 }, { 1, 1 }
};
int N = range.length;
System.out.print(maxRanges(range, N));
}
}
// This code is contributed by Kingash.
Python3
# Python 3 program for the above approach # Function to find the maximum number # of ranges where each range can be # uniquely represented by an integer def maxRanges(arr, N): # Sort the ranges in ascending order arr.sort() # Stores the count of ranges count = 1 # Stores previously assigned range prev = arr[0] # Traverse the vector arr[] for i in range(1, N): last = arr[i - 1] current = arr[i] # Skip the similar ranges # of size 1 if (last[0] == current[0] and last[1] == current[1] and current[1] == current[0]): continue # Find the range of integer # available to be assigned start = max(prev[0], current[0] - 1) end = max(prev[1], current[1]) # Check if an integer is # available to be assigned if (end - start > 0): # Update the previously # assigned range prev[0] = 1 + start prev[1] = end # Update the count of range count += 1 # Return the maximum count of # ranges return count # Driver Code if __name__ == "__main__": arr = [ [1, 4], [4, 4], [2, 2], [3, 4], [1, 1]] N = len(arr) print(maxRanges(arr, N)) # This code is contributed by ukasp.
Javascript
<script>
// Javascript program for the above approach
// Function to find the maximum number
// of ranges where each range can be
// uniquely represented by an integer
function maxRanges(arr, N) {
// Sort the ranges in ascending order
arr.sort((a, b) => {
return b[0] - a[0]
})
// Stores the count of ranges
let count = 1;
// Stores previously assigned range
let prev = arr[0];
// Traverse the vector arr[]
for (let i = 1; i < N; i++) {
let last = arr[i - 1];
let current = arr[i];
// Skip the similar ranges
// of size 1
if (last[0] == current[0]
&& last[1] == current[1]
&& current[1] == current[0]) {
continue;
}
// Find the range of integer
// available to be assigned
let start = Math.max(prev[0], current[0] - 1);
let end = Math.max(prev[1], current[1]);
// Check if an integer is
// available to be assigned
if ((end - start) > 0) {
// Update the previously
// assigned range
prev[0] = 1 + start;
prev[1] = end;
// Update the count of range
count++;
}
}
// Return the maximum count of
// ranges
return count;
}
// Driver Code
let range = [
[1, 4], [4, 4],
[2, 2], [3, 4],
[1, 1]];
let N = range.length;
document.write(maxRanges(range, N));
// This code is contributed by _Saurabh_jaiswal
</script>
Producción:
4
Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por rupesh_rao y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA