Dada una array 2D A[][] de tamaño N x 2 donde:
- Cada elemento se encuentra entre [1, N].
- A[i][0] significa que debe haber como máximo A[i][0] elementos estrictamente menores que i+1 y como máximo A[i][1] elementos estrictamente mayores que i+1.
La tarea es encontrar el máximo número de elementos que pueden unirse cumpliendo la condición anterior.
Ejemplos:
Entrada: N = 3, A[][] = {{1, 2}, {2, 1}, {1, 1]}
Salida: 2
Explicación: Si 1, 2, 3 se juntan, entonces hay 0 (como máximo 1) elemento menor que 1 y 2 (como máximo 2) son mayores.
1 (como máximo 2) elemento menor que 2 y 1 (como máximo 1) mayor que 2.
Para 3 hay 2 elementos menores que 3 pero según la condición puede haber como máximo 1 elemento menor que 3.
Por lo tanto, no puede incluir 3. Por lo tanto, se pueden seleccionar un máximo de 2 elementos juntos.Entrada: N = 5, A[][] = {{2, 3}, {4, 2}, {3, 1}, {3, 1}, {1, 1}};
Salida: 4
Enfoque ingenuo : la idea se basa en el concepto de que se puede mantener un mínimo de 1 elemento en un conjunto y, como máximo, todos los elementos se pueden mantener juntos, es decir, N
- Inicialmente, para el valor de K donde 1 <= K <= N , compruebe si se pueden agrupar K elementos respetando las condiciones.
- Seleccione K elementos de N elementos y verifique la siguiente condición para todos los K de 1 a N.
- Compruebe para cada candidato i de 1 a N :
- Si C candidatos ya pertenecen al conjunto de K elementos, entonces para que el i-ésimo elemento pertenezca a un conjunto de K números, i debe tener exactamente C elementos más pequeños y KC-1 elementos mayores que i .
- De esta forma, cuente los candidatos válidos y verifique si es posible mantener los K elementos juntos en un conjunto.
- Compruebe para cada candidato i de 1 a N :
- Al final, la máxima K es la respuesta.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el mejor enfoque es resolver usando la búsqueda binaria .
- En lugar de verificar todos los valores posibles de K , use la búsqueda binaria allí.
- Como si fuera posible mantener juntos K elementos, esto significa que también es posible mantener juntos cualquier valor más bajo de K elementos.
- Por lo tanto, verifique los valores más altos y si no es posible mantener K elementos juntos, significa que los valores más altos de K no se pueden agrupar.
- Cuando tanto el valor más bajo como el más alto se convierten en esa es la respuesta.
A continuación se muestra la implementación del enfoque mencionado anteriormente:
C++14
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if it is possible
// to keep k elements together
bool isPossible(vector<vector<int> >& a,
int n, int k)
{
// Initially the set is empty, so
// candidates present is 0
int candidatePresent = 0;
// Loop through all the candidates
for (int i = 0; i < n; i++) {
// For i to be a part of the set
// i's condition must allow to keep
// Atleast candidatePresent number of
// Elements smaller than i
// And k-candidatePresent-1
// Number of elements larger than i
// If so then add i
// To the set of k numbers
if (a[i][0] >= candidatePresent
&& a[i][1] >= k - candidatePresent
- 1)
candidatePresent++;
}
// If possible to keep at least k
// elements together return true
if (candidatePresent >= k)
return true;
// Else return false
return false;
}
int maxElementsinSet(vector<vector<int> >& a,
int n)
{
int left = 1, right = n;
int ans = 1;
while (left <= right) {
int mid = (left + right) / 2;
// If it is possible to keep mid
// elements together them mid
// is a possible answer and also
// check for higher values of mid
if (isPossible(a, n, mid)) {
ans = mid;
left = mid + 1;
}
// Else check for lower values of mid
else
right = mid - 1;
}
return ans;
}
// Driver Code
int main()
{
int N = 5;
vector<vector<int> > A = {
{ 2, 3 }, { 4, 2 }, { 3, 1 }, { 3, 1 }, { 1, 1 }
};
cout << maxElementsinSet(A, N);
return 0;
}
Java
// Java code to implement the approach
import java.util.*;
public class GFG {
// Function to check if it is possible
// to keep k elements together
static boolean isPossible(int a[][], int n, int k)
{
// Initially the set is empty, so
// candidates present is 0
int candidatePresent = 0;
// Loop through all the candidates
for (int i = 0; i < n; i++) {
// For i to be a part of the set
// i's condition must allow to keep
// Atleast candidatePresent number of
// Elements smaller than i
// And k-candidatePresent-1
// Number of elements larger than i
// If so then add i
// To the set of k numbers
if (a[i][0] >= candidatePresent
&& a[i][1] >= k - candidatePresent - 1)
candidatePresent++;
}
// If possible to keep at least k
// elements together return true
if (candidatePresent >= k)
return true;
// Else return false
return false;
}
static int maxElementsinSet(int a[][], int n)
{
int left = 1, right = n;
int ans = 1;
while (left <= right) {
int mid = (left + right) / 2;
// If it is possible to keep mid
// elements together them mid
// is a possible answer and also
// check for higher values of mid
if (isPossible(a, n, mid) == true) {
ans = mid;
left = mid + 1;
}
// Else check for lower values of mid
else
right = mid - 1;
}
return ans;
}
// Driver Code
public static void main(String arg[])
{
int N = 5;
int A[][] = {
{ 2, 3 }, { 4, 2 }, { 3, 1 }, { 3, 1 }, { 1, 1 }
};
System.out.println(maxElementsinSet(A, N));
}
}
// This code is contributed by Samim Hossain Mondal.
Python
# Python code to implement the approach # Function to check if it is possible # to keep k elements together def isPossible(a, n, k): # Initially the set is empty, so # candidates present is 0 candidatePresent = 0 # Loop through all the candidates for i in range(n): # For i to be a part of the set # i's condition must allow to keep # Atleast candidatePresent number of # Elements smaller than i # And k-candidatePresent-1 # Number of elements larger than i # If so then add i # To the set of k numbers if (a[i][0] >= candidatePresent and a[i][1] >= k - candidatePresent - 1): candidatePresent += 1 # If possible to keep at least k # elements together return true if (candidatePresent >= k): return 1 # Else return false return 0 def maxElementsinSet(a, n): left = 1 right = n ans = 1 while (left <= right): mid = (left + right) / 2 # If it is possible to keep mid # elements together them mid # is a possible answer and also # check for higher values of mid if (isPossible(a, n, mid)): ans = mid left = mid + 1 # Else check for lower values of mid else: right = mid - 1 print(ans) # Driver Code if __name__ == "__main__": N = 5; A = [[ 2, 3 ], [ 4, 2 ], [ 3, 1 ], [ 3, 1 ], [ 1, 1 ]] maxElementsinSet(A, N) # This code is contributed by hrithikgarg03188.
C#
// C# code to implement the approach
using System;
public class GFG {
// Function to check if it is possible
// to keep k elements together
static bool isPossible(int[, ] a, int n, int k)
{
// Initially the set is empty, so
// candidates present is 0
int candidatePresent = 0;
// Loop through all the candidates
for (int i = 0; i < n; i++) {
// For i to be a part of the set
// i's condition must allow to keep
// Atleast candidatePresent number of
// Elements smaller than i
// And k-candidatePresent-1
// Number of elements larger than i
// If so then add i
// To the set of k numbers
if (a[i, 0] >= candidatePresent
&& a[i, 1] >= k - candidatePresent - 1)
candidatePresent++;
}
// If possible to keep at least k
// elements together return true
if (candidatePresent >= k)
return true;
// Else return false
return false;
}
static int maxElementsinSet(int[, ] a, int n)
{
int left = 1, right = n;
int ans = 1;
while (left <= right) {
int mid = (left + right) / 2;
// If it is possible to keep mid
// elements together them mid
// is a possible answer and also
// check for higher values of mid
if (isPossible(a, n, mid) == true) {
ans = mid;
left = mid + 1;
}
// Else check for lower values of mid
else
right = mid - 1;
}
return ans;
}
// Driver Code
public static void Main(String[] arg)
{
int N = 5;
int[, ] A = {
{ 2, 3 }, { 4, 2 }, { 3, 1 }, { 3, 1 }, { 1, 1 }
};
Console.WriteLine(maxElementsinSet(A, N));
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript code to implement the approach
// Function to check if it is possible
// to keep k elements together
const isPossible = (a, n, k) => {
// Initially the set is empty, so
// candidates present is 0
let candidatePresent = 0;
// Loop through all the candidates
for (let i = 0; i < n; i++) {
// For i to be a part of the set
// i's condition must allow to keep
// Atleast candidatePresent number of
// Elements smaller than i
// And k-candidatePresent-1
// Number of elements larger than i
// If so then add i
// To the set of k numbers
if (a[i][0] >= candidatePresent
&& a[i][1] >= k - candidatePresent
- 1)
candidatePresent++;
}
// If possible to keep at least k
// elements together return true
if (candidatePresent >= k)
return true;
// Else return false
return false;
}
const maxElementsinSet = (a, n) => {
let left = 1, right = n;
let ans = 1;
while (left <= right) {
let mid = parseInt((left + right) / 2);
// If it is possible to keep mid
// elements together them mid
// is a possible answer and also
// check for higher values of mid
if (isPossible(a, n, mid)) {
ans = mid;
left = mid + 1;
}
// Else check for lower values of mid
else
right = mid - 1;
}
return ans;
}
// Driver Code
let N = 5;
let A = [
[2, 3], [4, 2], [3, 1], [3, 1], [1, 1]
];
document.write(maxElementsinSet(A, N));
// This code is contributed by rakeshsahni
</script>
Producción
4
Complejidad de tiempo: O(N*logN)
Espacio auxiliar: O(1)