Dados N intervalos en la forma [l, r] y un número entero Q . La tarea es encontrar el intervalo que cuando se elimina da como resultado la cobertura del número máximo de puntos (Unión de todos los demás intervalos). Tenga en cuenta que todos los intervalos dados cubren números entre 1 y Q solamente.
Ejemplos:
Entrada: intervalos[][] = {{1, 4}, {4, 5}, {5, 6}, {6, 7}, {3, 5}}, Q = 7
Salida: La cobertura máxima es 7 después eliminando el intervalo en el índice 4
Cuando se elimina el último intervalo, podemos cubrir los puntos dados usando el resto de los intervalos
{1, 2, 3, 4, 5, 6, 7}, que es la máxima cobertura posible.
(La respuesta también será la misma si eliminamos el intervalo {4, 5} o {5, 6})
Entrada: intervalos[][] = {{3, 3}, {2, 2}, {3, 4}} , Q = 4
Salida: La cobertura máxima es 3 después de eliminar el intervalo en el índice 0
Acercarse:
- Primero use una marca de array [] de tamaño n + 1 . Si mark[i] = k , esto significa que exactamente k intervalos tienen el punto i en ellos.
- Mantener conteo, número total de números que están cubiertos por todos los intervalos.
- Ahora tenemos que iterar a través de todos los intervalos y verificar si cada intervalo se elimina, entonces cuántos números se eliminarán del conteo.
- Para verificar el nuevo conteo después de la eliminación de cada intervalo, necesitamos mantener una array count1[] , donde count1[i] indica cuántos números del 1 al i tienen exactamente un intervalo en el que aparecen.
- El nuevo conteo para cualquier intervalo será conteo – (conteo1[r] – conteo1[l-1]) . Dado que solo aquellos números que ocurren exactamente en un intervalo y pertenecen a [l, r] deben excluirse del conteo real.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
#define ll long long int
using namespace std;
// Function To find the required interval
void solve(int interval[][2], int N, int Q)
{
int Mark[Q] = { 0 };
for (int i = 0; i < N; i++) {
int l = interval[i][0] - 1;
int r = interval[i][1] - 1;
for (int j = l; j <= r; j++)
Mark[j]++;
}
// Total Count of covered numbers
int count = 0;
for (int i = 0; i < Q; i++) {
if (Mark[i])
count++;
}
// Array to store numbers that occur
// exactly in one interval till ith interval
int count1[Q] = { 0 };
if (Mark[0] == 1)
count1[0] = 1;
for (int i = 1; i < Q; i++) {
if (Mark[i] == 1)
count1[i] = count1[i - 1] + 1;
else
count1[i] = count1[i - 1];
}
int maxindex;
int maxcoverage = 0;
for (int i = 0; i < N; i++) {
int l = interval[i][0] - 1;
int r = interval[i][1] - 1;
// Calculate New count by removing all numbers
// in range [l, r] occurring exactly once
int elem1;
if (l != 0)
elem1 = count1[r] - count1[l - 1];
else
elem1 = count1[r];
if (count - elem1 >= maxcoverage) {
maxcoverage = count - elem1;
maxindex = i;
}
}
cout << "Maximum Coverage is " << maxcoverage
<< " after removing interval at index "
<< maxindex;
}
// Driver code
int main()
{
int interval[][2] = { { 1, 4 },
{ 4, 5 },
{ 5, 6 },
{ 6, 7 },
{ 3, 5 } };
int N = sizeof(interval) / sizeof(interval[0]);
int Q = 7;
solve(interval, N, Q);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Function To find the required interval
static void solve(int interval[][], int N, int Q)
{
int Mark[] = new int[Q];
for (int i = 0; i < N; i++)
{
int l = interval[i][0] - 1;
int r = interval[i][1] - 1;
for (int j = l; j <= r; j++)
Mark[j]++;
}
// Total Count of covered numbers
int count = 0;
for (int i = 0; i < Q; i++)
{
if (Mark[i] != 0)
count++;
}
// Array to store numbers that occur
// exactly in one interval till ith interval
int count1[] = new int[Q];
if (Mark[0] == 1)
count1[0] = 1;
for (int i = 1; i < Q; i++)
{
if (Mark[i] == 1)
count1[i] = count1[i - 1] + 1;
else
count1[i] = count1[i - 1];
}
int maxindex = 0;
int maxcoverage = 0;
for (int i = 0; i < N; i++)
{
int l = interval[i][0] - 1;
int r = interval[i][1] - 1;
// Calculate New count by removing all numbers
// in range [l, r] occurring exactly once
int elem1;
if (l != 0)
elem1 = count1[r] - count1[l - 1];
else
elem1 = count1[r];
if (count - elem1 >= maxcoverage)
{
maxcoverage = count - elem1;
maxindex = i;
}
}
System.out.println("Maximum Coverage is " + maxcoverage
+ " after removing interval at index "
+ maxindex);
}
// Driver code
public static void main(String[] args)
{
int interval[][] = { { 1, 4 },
{ 4, 5 },
{ 5, 6 },
{ 6, 7 },
{ 3, 5 } };
int N = interval.length;
int Q = 7;
solve(interval, N, Q);
}
}
/* This code contributed by PrinciRaj1992 */
Python3
# Python3 implementation of the approach
# Function To find the required interval
def solve(interval, N, Q):
Mark = [0 for i in range(Q)]
for i in range(N):
l = interval[i][0] - 1
r = interval[i][1] - 1
for j in range(l, r + 1):
Mark[j] += 1
# Total Count of covered numbers
count = 0
for i in range(Q):
if (Mark[i]):
count += 1
# Array to store numbers that occur
# exactly in one interval till ith interval
count1 = [0 for i in range(Q)]
if (Mark[0] == 1):
count1[0] = 1
for i in range(1, Q):
if (Mark[i] == 1):
count1[i] = count1[i - 1] + 1
else:
count1[i] = count1[i - 1]
maxindex = 0
maxcoverage = 0
for i in range(N):
l = interval[i][0] - 1
r = interval[i][1] - 1
# Calculate New count by removing all numbers
# in range [l, r] occurring exactly once
elem1 = 0
if (l != 0):
elem1 = count1[r] - count1[l - 1]
else:
elem1 = count1[r]
if (count - elem1 >= maxcoverage):
maxcoverage = count - elem1
maxindex = i
print("Maximum Coverage is", maxcoverage,
"after removing interval at index", maxindex)
# Driver code
interval = [[ 1, 4 ],
[ 4, 5 ],
[ 5, 6 ],
[ 6, 7 ],
[ 3, 5 ]]
N = len(interval)
Q = 7
solve(interval, N, Q)
# This code is contributed by mohit kumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function To find the required interval
static void solve(int[,] interval, int N, int Q)
{
int[] Mark = new int[Q];
for (int i = 0; i < N; i++)
{
int l = interval[i,0] - 1;
int r = interval[i,1] - 1;
for (int j = l; j <= r; j++)
Mark[j]++;
}
// Total Count of covered numbers
int count = 0;
for (int i = 0; i < Q; i++)
{
if (Mark[i] != 0)
count++;
}
// Array to store numbers that occur
// exactly in one interval till ith interval
int[] count1 = new int[Q];
if (Mark[0] == 1)
count1[0] = 1;
for (int i = 1; i < Q; i++)
{
if (Mark[i] == 1)
count1[i] = count1[i - 1] + 1;
else
count1[i] = count1[i - 1];
}
int maxindex = 0;
int maxcoverage = 0;
for (int i = 0; i < N; i++)
{
int l = interval[i,0] - 1;
int r = interval[i,1] - 1;
// Calculate New count by removing all numbers
// in range [l, r] occurring exactly once
int elem1;
if (l != 0)
elem1 = count1[r] - count1[l - 1];
else
elem1 = count1[r];
if (count - elem1 >= maxcoverage)
{
maxcoverage = count - elem1;
maxindex = i;
}
}
Console.WriteLine("Maximum Coverage is " + maxcoverage
+ " after removing interval at index "
+ maxindex);
}
// Driver code
public static void Main()
{
int[,] interval = { { 1, 4 },
{ 4, 5 },
{ 5, 6 },
{ 6, 7 },
{ 3, 5 } };
int N = interval.Length;
int Q = 7;
solve(interval, N/2, Q);
}
}
/* This code contributed by Code_Mech */
Javascript
<script>
// Javascript implementation of the approach
// Function To find the required interval
function solve(interval, N, Q)
{
var Mark = Array(Q).fill(0);
for (var i = 0; i < N; i++) {
var l = interval[i][0] - 1;
var r = interval[i][1] - 1;
for (var j = l; j <= r; j++)
Mark[j]++;
}
// Total Count of covered numbers
var count = 0;
for (var i = 0; i < Q; i++) {
if (Mark[i])
count++;
}
// Array to store numbers that occur
// exactly in one interval till ith interval
var count1 = Array(Q).fill(0);
if (Mark[0] == 1)
count1[0] = 1;
for (var i = 1; i < Q; i++) {
if (Mark[i] == 1)
count1[i] = count1[i - 1] + 1;
else
count1[i] = count1[i - 1];
}
var maxindex;
var maxcoverage = 0;
for (var i = 0; i < N; i++) {
var l = interval[i][0] - 1;
var r = interval[i][1] - 1;
// Calculate New count by removing all numbers
// in range [l, r] occurring exactly once
var elem1;
if (l != 0)
elem1 = count1[r] - count1[l - 1];
else
elem1 = count1[r];
if (count - elem1 >= maxcoverage) {
maxcoverage = count - elem1;
maxindex = i;
}
}
document.write( "Maximum Coverage is " + maxcoverage
+ " after removing interval at index "
+ maxindex);
}
// Driver code
var interval = [ [ 1, 4 ],
[ 4, 5 ],
[ 5, 6 ],
[ 6, 7 ],
[ 3, 5 ] ];
var N = interval.length;
var Q = 7;
solve(interval, N, Q);
</script>
Producción:
Maximum Coverage is 7 after removing interval at index 4