Dada una array arr[] y dos enteros N y K , la tarea es elegir N subarreglos de tamaño K que no se superpongan de modo que el elemento máximo de todos los subarreglos sea el mínimo.
Nota: Si no es posible elegir N tales subarreglos, devuelva -1.
Ejemplos:
Entrada: arr[] = {1, 10, 3, 10, 2}, N = 3, K = 1
Salida: 3
Explicación:
Los tres subarreglos que no se superponen son:
Subarreglos => {{1}, {2}, {3}}
El máximo de estos subarreglos son => 3
Entrada: arr[] = {7, 7, 7, 7, 12, 7, 7}, N = 2, K = 3
Salida: 12
Explicación:
Los dos no los subarreglos superpuestos son –
Subarreglos => {{7, 7, 7}, {7, 12, 7}}
El elemento máximo de estos subarreglos es => 12
Enfoque: La idea es utilizar una búsqueda binaria . A continuación se muestra la ilustración de la búsqueda binaria:
- Espacio de búsqueda: ya que tenemos que encontrar el elemento máximo de los N subarreglos, que es uno de los elementos del arreglo. Por lo tanto, el espacio de búsqueda será desde el elemento mínimo hasta el elemento máximo de la array.
- Función para búsqueda binaria: La función para búsqueda binaria es encontrar el conteo de arreglos de tamaño K posibles con todos los elementos menores que el número dado que estará en el medio del espacio de búsqueda.
- Espacio de búsqueda izquierdo: la condición cuando el recuento de subarreglos de tamaño K posibles es mayor o igual a N, entonces la respuesta posible puede estar en el espacio de búsqueda izquierdo.
- Espacio de búsqueda correcto: la condición cuando el recuento de subarreglos de tamaño K posibles es menor que N, entonces la respuesta posible de exploración se encuentra en el espacio de búsqueda correcto.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to choose
// N subarrays of size K such that
// the maximum element of
// subarrays is minimum
#include <bits/stdc++.h>
using namespace std;
// Function to choose
// N subarrays of size K such that
// the maximum element of
// subarrays is minimum
int minDays(vector<int>& arr,
int n, int k)
{
int l = arr.size(),
left = 1, right = 1e9;
// Condition to check if it
// is not possible to choose k
// sized N subarrays
if (n * k > l)
return -1;
// Using binary search
while (left < right) {
// calculating mid
int mid = (left + right) / 2,
cnt = 0, product = 0;
// Loop to find the count of the
// K sized subarrays possible with
// elements less than mid
for (int j = 0; j < l; ++j) {
if (arr[j] > mid) {
cnt = 0;
}
else if (++cnt >= k) {
product++;
cnt = 0;
}
}
// Condition to check if the
// answer is in right subarray
if (product < n) {
left = mid + 1;
}
else {
right = mid;
}
}
return left;
}
// Driver Code
int main()
{
vector<int> arr{ 1, 10, 3, 10, 2 };
int n = 3, k = 1;
// Function Call
cout << minDays(arr, n, k) << endl;
return 0;
}
Java
// Java implementation to choose
// N subarrays of size K such that
// the maximum element of
// subarrays is minimum
class GFG{
// Function to choose
// N subarrays of size K such that
// the maximum element of
// subarrays is minimum
static int minDays(int []arr,
int n, int k)
{
int l = arr.length,
left = 1, right = (int) 1e9;
// Condition to check if it
// is not possible to choose k
// sized N subarrays
if (n * k > l)
return -1;
// Using binary search
while (left < right)
{
// calculating mid
int mid = (left + right) / 2,
cnt = 0, product = 0;
// Loop to find the count of the
// K sized subarrays possible with
// elements less than mid
for (int j = 0; j < l; ++j)
{
if (arr[j] > mid)
{
cnt = 0;
}
else if (++cnt >= k)
{
product++;
cnt = 0;
}
}
// Condition to check if the
// answer is in right subarray
if (product < n)
{
left = mid + 1;
}
else
{
right = mid;
}
}
return left;
}
// Driver Code
public static void main(String[] args)
{
int []arr = {1, 10, 3, 10, 2};
int n = 3, k = 1;
// Function Call
System.out.print(minDays(arr, n, k) + "\n");
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 implementation to choose # N subarrays of size K such that # the maximum element of # subarrays is minimum # Function to choose # N subarrays of size K such that # the maximum element of # subarrays is minimum def minDays(arr, n, k): l = len(arr) left = 1 right = 1e9 # Condition to check if it # is not possible to choose k # sized N subarrays if (n * k > l): return -1 # Using binary search while (left < right): # calculating mid mid = (left + right) // 2 cnt = 0 product = 0 # Loop to find the count of the # K sized subarrays possible with # elements less than mid for j in range (l): if (arr[j] > mid): cnt = 0 else: cnt += 1 if (cnt >= k): product += 1 cnt = 0 # Condition to check if the # answer is in right subarray if (product < n): left = mid + 1 else: right = mid return left # Driver Code if __name__ == "__main__": arr = [1, 10, 3, 10, 2] n = 3 k = 1 # Function Call print (int(minDays(arr, n, k))) # This code is contributed by Chitranayal
C#
// C# implementation to choose N
// subarrays of size K such that
// the maximum element of
// subarrays is minimum
using System;
class GFG{
// Function to choose N subarrays
// of size K such that the maximum
// element of subarrays is minimum
static int minDays(int []arr,
int n, int k)
{
int l = arr.Length;
int left = 1, right = (int)1e9;
// Condition to check if it
// is not possible to choose k
// sized N subarrays
if (n * k > l)
return -1;
// Using binary search
while (left < right)
{
// Calculating mid
int mid = (left + right) / 2,
cnt = 0, product = 0;
// Loop to find the count of the
// K sized subarrays possible with
// elements less than mid
for(int j = 0; j < l; ++j)
{
if (arr[j] > mid)
{
cnt = 0;
}
else if (++cnt >= k)
{
product++;
cnt = 0;
}
}
// Condition to check if the
// answer is in right subarray
if (product < n)
{
left = mid + 1;
}
else
{
right = mid;
}
}
return left;
}
// Driver Code
public static void Main(String[] args)
{
int []arr = { 1, 10, 3, 10, 2 };
int n = 3, k = 1;
// Function Call
Console.Write(minDays(arr, n, k) + "\n");
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript implementation to choose
// N subarrays of size K such that
// the maximum element of
// subarrays is minimum
// Function to choose
// N subarrays of size K such that
// the maximum element of
// subarrays is minimum
function minDays(arr, n, k)
{
let l = arr.length,
left = 1, right = 1000000000;
// Condition to check if it
// is not possible to choose k
// sized N subarrays
if (n * k > l)
return -1;
// Using binary search
while (left < right) {
// calculating mid
let mid = parseInt((left + right) / 2),
cnt = 0, product = 0;
// Loop to find the count of the
// K sized subarrays possible with
// elements less than mid
for (let j = 0; j < l; ++j) {
if (arr[j] > mid) {
cnt = 0;
}
else if (++cnt >= k) {
product++;
cnt = 0;
}
}
// Condition to check if the
// answer is in right subarray
if (product < n) {
left = mid + 1;
}
else {
right = mid;
}
}
return left;
}
// Driver Code
let arr = [ 1, 10, 3, 10, 2 ];
let n = 3, k = 1;
// Function Call
document.write(minDays(arr, n, k));
</script>
Producción:
3
Complejidad de tiempo: O(N*logN)
Publicación traducida automáticamente
Artículo escrito por siwaniagrawal y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA