Dado un entero R que significa el rango [0, R] y dos arrays start[] y end[] de tamaño N que significan los intervalos inicial y final en el rango [0, R]. La tarea es contar la cantidad de intervalos no superpuestos disponibles que deben insertarse en las arrays de modo que al fusionar los rangos individuales en las arrays start[] y end[] , el intervalo fusionado se convierte en [0, R].
Ejemplos:
Entrada: R = 10, N = 3, start[] = {2, 5, 8}, end[] = {3, 9, 10}
Salida: 2
Explicación:
Los rangos {[2, 3], [5, 10]} están dadas por la array. Para hacer que el intervalo fusionado sea [0, R], los rangos [0, 2] y [3, 5] deben insertarse y fusionarse. Por lo tanto, se deben insertar dos rangos en la array.Entrada: R = 8, N = 2, start[] = {2, 6}, end[] = {3, 7}
Salida: 3
Explicación:
Los rangos {[2, 3], [6, 7]} son dada por la array. Para hacer que el intervalo fusionado sea [0, R], los rangos [0, 2], [3, 6] y [7, 8] deben insertarse y fusionarse. Por lo tanto, se deben insertar tres rangos en la array.
Enfoque: La idea es utilizar la clasificación para resolver el problema.
- Inicialmente, ambas arrays dadas se ordenan para que los intervalos usados se junten.
- Ahora, las arrays se iteran de forma ordenada (es decir), un puntero apuntaría al inicio de inicio y otro apuntaría al inicio de fin .
- Si el elemento de inicio actual es más pequeño, esto significa que se está buscando un nuevo intervalo y si el índice final actual es más pequeño, significa que se está saliendo del intervalo actual.
- En este proceso, se almacena el recuento de los intervalos activos actuales. Si en algún momento el conteo activo actual es 0, entonces hay un intervalo disponible. Por lo tanto, se incrementa la cuenta del intervalo disponible.
- De esta manera, ambas arrays se iteran.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <iostream>
using namespace std;
// The following two functions
// are used to sort the array.
// QuickSort is being implemented in
// the following functions
// Function to find the pivot index
int partition(int arr[], int l, int h)
{
int pivot = arr[l];
int i = l + 1;
int j = h;
while (i <= j) {
while (i <= h
&& arr[i] < pivot) {
i++;
}
while (j > l
&& arr[j] > pivot) {
j--;
}
if (i < j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
else
i++;
}
arr[l] = arr[j];
arr[j] = pivot;
return j;
}
// Function to implement Quick Sort
void sortArray(int arr[], int l, int h)
{
if (l >= h)
return;
// Pivot is pointing to pivot index
// before which every element
// is smaller and after pivot,
// every element is greater
int pivot = partition(arr, l, h);
// Sort the array before pivot element
sortArray(arr, l, pivot - 1);
// Sort the array after pivot element
sortArray(arr, pivot + 1, h);
}
// Function to count the available intervals
// from the given range of numbers
int findMaxIntervals(int start[], int end[],
int n, int R)
{
int ans = 0;
int prev = 0;
int currActive = 0;
int i = 0;
int j = 0;
// If range starts after 0
// then an interval is available
// from 0 to start[0]
if (start[0] > 0)
ans++;
while (i < n && j < n) {
// When a new interval starts
if (start[i] < end[j]) {
// Since index variable i is being
// incremented, the current active
// interval will also get incremented
i++;
currActive++;
}
// When the current interval ends
else if (start[i] > end[j]) {
// Since index variable j is being
// decremented, the currect active
// interval will also get decremented
j++;
currActive--;
}
// When start and end both are same
// there is no change in currActive
else {
i++;
j++;
}
if (currActive == 0) {
ans++;
}
}
// If the end of interval
// is before the range
// so interval is available
// at the end
if (end[n - 1] < R)
ans++;
return ans;
}
// Driver code
int main()
{
int R, N;
R = 10;
N = 3;
int start[N] = { 2, 5, 8 };
int end[N] = { 3, 9, 10 };
// Sort the start array
sortArray(start, 0, N - 1);
// Sort the end array
sortArray(end, 0, N - 1);
// Calling the function
cout << findMaxIntervals(
start, end, N, R);
}
Java
// Java implementation of the above approach
import java.util.*;
class GFG{
// The following two functions
// are used to sort the array.
// QuickSort is being implemented in
// the following functions
// Function to find the pivot index
static int partition(int arr[], int l, int h)
{
int pivot = arr[l];
int i = l + 1;
int j = h;
while (i <= j)
{
while (i <= h && arr[i] < pivot)
{
i++;
}
while (j > l && arr[j] > pivot)
{
j--;
}
if (i < j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
else
i++;
}
arr[l] = arr[j];
arr[j] = pivot;
return j;
}
// Function to implement Quick Sort
static void sortArray(int arr[], int l, int h)
{
if (l >= h)
return;
// Pivot is pointing to pivot index
// before which every element
// is smaller and after pivot,
// every element is greater
int pivot = partition(arr, l, h);
// Sort the array before pivot element
sortArray(arr, l, pivot - 1);
// Sort the array after pivot element
sortArray(arr, pivot + 1, h);
}
// Function to count the available intervals
// from the given range of numbers
static int findMaxIntervals(int start[],
int end[],
int n, int R)
{
int ans = 0;
int prev = 0;
int currActive = 0;
int i = 0;
int j = 0;
// If range starts after 0
// then an interval is available
// from 0 to start[0]
if (start[0] > 0)
ans++;
while (i < n && j < n)
{
// When a new interval starts
if (start[i] < end[j])
{
// Since index variable i is being
// incremented, the current active
// interval will also get incremented
i++;
currActive++;
}
// When the current interval ends
else if (start[i] > end[j])
{
// Since index variable j is being
// decremented, the currect active
// interval will also get decremented
j++;
currActive--;
}
// When start and end both are same
// there is no change in currActive
else
{
i++;
j++;
}
if (currActive == 0)
{
ans++;
}
}
// If the end of interval
// is before the range
// so interval is available
// at the end
if (end[n - 1] < R)
ans++;
return ans;
}
// Driver code
public static void main(String args[])
{
int R, N;
R = 10;
N = 3;
int start[] = new int[]{ 2, 5, 8 };
int end[] = new int[]{ 3, 9, 10 };
// Sort the start array
sortArray(start, 0, N - 1);
// Sort the end array
sortArray(end, 0, N - 1);
// Calling the function
System.out.print(findMaxIntervals(start, end, N, R));
}
}
// This code is contributed by Code_Mech
Python3
# Python3 implementation of the above approach # The following two functions # are used to sort the array. # QuickSort is being implemented in # the following functions # Function to find the pivot index def partition(arr, l, h): pivot = arr[l] i = l + 1 j = h while (i <= j): while (i <= h and arr[i] < pivot): i += 1 while (j > l and arr[j] > pivot): j -= 1 if (i < j): temp = arr[i] arr[i] = arr[j] arr[j] = temp i += 1 j -= 1 else: i += 1 arr[l] = arr[j] arr[j] = pivot return j # Function to implement Quick Sort def sortArray(arr, l, h): if (l >= h): return # Pivot is pointing to pivot index # before which every element # is smaller and after pivot, # every element is greater pivot = partition(arr, l, h) # Sort the array before pivot element sortArray(arr, l, pivot - 1) # Sort the array after pivot element sortArray(arr, pivot + 1, h) # Function to count the available intervals # from the given range of numbers def findMaxIntervals(start, end, n, R): ans = 0 prev = 0 currActive = 0 i = 0 j = 0 # If range starts after 0 # then an interval is available # from 0 to start[0] if (start[0] > 0): ans += 1 while (i < n and j < n): # When a new interval starts if (start[i] < end[j]): # Since index variable i is being # incremented, the current active # interval will also get incremented i += 1 currActive += 1 # When the current interval ends elif (start[i] > end[j]): # Since index variable j is being # decremented, the currect active # interval will also get decremented j += 1 currActive -= 1 # When start and end both are same # there is no change in currActive else: i += 1 j += 1 if (currActive == 0): ans += 1 # If the end of interval # is before the range # so interval is available # at the end if (end[n - 1] < R): ans += 1 return ans # Driver code if __name__ == '__main__': R = 10 N = 3 start = [ 2, 5, 8 ] end = [ 3, 9, 10 ] # Sort the start array sortArray(start, 0, N - 1) # Sort the end array sortArray(end, 0, N - 1) # Calling the function print(findMaxIntervals(start, end, N, R)) # This code is contributed by Surendra_Gangwar
C#
// C# implementation of the above approach
using System;
class GFG{
// The following two functions
// are used to sort the array.
// QuickSort is being implemented in
// the following functions
// Function to find the pivot index
static int partition(int []arr, int l, int h)
{
int pivot = arr[l];
int i = l + 1;
int j = h;
while (i <= j)
{
while (i <= h && arr[i] < pivot)
{
i++;
}
while (j > l && arr[j] > pivot)
{
j--;
}
if (i < j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
else
i++;
}
arr[l] = arr[j];
arr[j] = pivot;
return j;
}
// Function to implement Quick Sort
static void sortArray(int []arr, int l, int h)
{
if (l >= h)
return;
// Pivot is pointing to pivot index
// before which every element
// is smaller and after pivot,
// every element is greater
int pivot = partition(arr, l, h);
// Sort the array before pivot element
sortArray(arr, l, pivot - 1);
// Sort the array after pivot element
sortArray(arr, pivot + 1, h);
}
// Function to count the available intervals
// from the given range of numbers
static int findMaxIntervals(int []start,
int []end,
int n, int R)
{
int ans = 0;
int prev = 0;
int currActive = 0;
int i = 0;
int j = 0;
// If range starts after 0
// then an interval is available
// from 0 to start[0]
if (start[0] > 0)
ans++;
while (i < n && j < n)
{
// When a new interval starts
if (start[i] < end[j])
{
// Since index variable i is being
// incremented, the current active
// interval will also get incremented
i++;
currActive++;
}
// When the current interval ends
else if (start[i] > end[j])
{
// Since index variable j is being
// decremented, the currect active
// interval will also get decremented
j++;
currActive--;
}
// When start and end both are same
// there is no change in currActive
else
{
i++;
j++;
}
if (currActive == 0)
{
ans++;
}
}
// If the end of interval
// is before the range
// so interval is available
// at the end
if (end[n - 1] < R)
ans++;
return ans;
}
// Driver code
public static void Main()
{
int R, N;
R = 10;
N = 3;
int []start = new int[]{ 2, 5, 8 };
int []end = new int[]{ 3, 9, 10 };
// Sort the start array
sortArray(start, 0, N - 1);
// Sort the end array
sortArray(end, 0, N - 1);
// Calling the function
Console.Write(findMaxIntervals(start, end, N, R));
}
}
// This code is contributed by Code_Mech
Javascript
<script>
// Javascript implementation of the above approach
// The following two functions
// are used to sort the array.
// QuickSort is being implemented in
// the following functions
// Function to find the pivot index
function partition(arr, l, h)
{
let pivot = arr[l];
let i = l + 1;
let j = h;
while (i <= j)
{
while (i <= h && arr[i] < pivot)
{
i++;
}
while (j > l && arr[j] > pivot)
{
j--;
}
if (i < j)
{
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
else
i++;
}
arr[l] = arr[j];
arr[j] = pivot;
return j;
}
// Function to implement Quick Sort
function sortArray(arr, l, h)
{
if (l >= h)
return;
// Pivot is pointing to pivot index
// before which every element
// is smaller and after pivot,
// every element is greater
let pivot = partition(arr, l, h);
// Sort the array before pivot element
sortArray(arr, l, pivot - 1);
// Sort the array after pivot element
sortArray(arr, pivot + 1, h);
}
// Function to count the available intervals
// from the given range of numbers
function findMaxIntervals(start,
end, n, R)
{
let ans = 0;
let prev = 0;
let currActive = 0;
let i = 0;
let j = 0;
// If range starts after 0
// then an interval is available
// from 0 to start[0]
if (start[0] > 0)
ans++;
while (i < n && j < n)
{
// When a new interval starts
if (start[i] < end[j])
{
// Since index variable i is being
// incremented, the current active
// interval will also get incremented
i++;
currActive++;
}
// When the current interval ends
else if (start[i] > end[j])
{
// Since index variable j is being
// decremented, the currect active
// interval will also get decremented
j++;
currActive--;
}
// When start and end both are same
// there is no change in currActive
else
{
i++;
j++;
}
if (currActive == 0)
{
ans++;
}
}
// If the end of interval
// is before the range
// so interval is available
// at the end
if (end[n - 1] < R)
ans++;
return ans;
}
// Driver Code
let R, N;
R = 10;
N = 3;
let start = [ 2, 5, 8 ];
let end = [ 3, 9, 10 ];
// Sort the start array
sortArray(start, 0, N - 1);
// Sort the end array
sortArray(end, 0, N - 1);
// Calling the function
document.write(findMaxIntervals(start, end, N, R));
</script>
Producción:
2
Publicación traducida automáticamente
Artículo escrito por Poojaa Baliyan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA