Dado un número entero N que denota el número de ranuras, y una array arr[] que consta de K enteros en el rango [1, N] repreand. Cada elemento de la array está en el rango [1, N] que representa los índices de las ranuras llenas. En cada unidad de tiempo, el índice con la ranura llena llena las ranuras vacías adyacentes. La tarea es encontrar el tiempo mínimo necesario para llenar todos los espacios N.
Ejemplos:
Entrada: N = 6, K = 2, arr[] = {2, 6}
Salida: 2
Explicación:
Inicialmente hay 6 ranuras y los índices de las ranuras llenas son ranuras [] = {0, 2, 0, 0, 0, 6}, donde 0 representa vacío.
Después de 1 unidad de tiempo, slots[] = {1, 2, 3, 0, 5, 6}
Después de 2 unidades de tiempo, slots[] = {1, 2, 3, 4, 5, 6}
Por lo tanto, el mínimo el tiempo requerido es 2.Entrada: N = 5, K = 5, arr[] = {1, 2, 3, 4, 5}
Salida: 1
Enfoque: para resolver el problema dado, la idea es realizar un cruce de orden de nivel en las N ranuras dadas usando una cola . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos time como 0 , y una array auxiliar visited[] para marcar los índices completos en cada iteración.
- Ahora, empuje los índices de las ranuras llenas que se dan en el arreglo arr[] en una cola y márquelos como visitados.
- Ahora, itere hasta que la cola no esté vacía y realice los siguientes pasos:
- Elimine el índice frontal i de la cola y si las ranuras adyacentes (i – 1) e (i + 1) están en el rango [1, N] y no están visitadas, márquelas como visitadas e introdúzcalas en la cola .
- Incrementa el tiempo en 1 .
- Después de completar los pasos anteriores, imprima el valor de (tiempo – 1) como el tiempo mínimo requerido para llenar todos los espacios.
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 return the minimum
// time to fill all the slots
void minTime(vector<int> arr, int N, int K)
{
// Stores visited slots
queue<int> q;
// Checks if a slot is visited or not
vector<bool> vis(N + 1, false);
int time = 0;
// Insert all filled slots
for (int i = 0; i < K; i++) {
q.push(arr[i]);
vis[arr[i]] = true;
}
// Iterate until queue is
// not empty
while (q.size() > 0) {
// Iterate through all slots
// in the queue
for (int i = 0; i < q.size(); i++) {
// Front index
int curr = q.front();
q.pop();
// If previous slot is
// present and not visited
if (curr - 1 >= 1 &&
!vis[curr - 1]) {
vis[curr - 1] = true;
q.push(curr - 1);
}
// If next slot is present
// and not visited
if (curr + 1 <= N &&
!vis[curr + 1]) {
vis[curr + 1] = true;
q.push(curr + 1);
}
}
// Increment the time
// at each level
time++;
}
// Print the answer
cout << (time - 1);
}
// Driver Code
int main()
{
int N = 6;
vector<int> arr = { 2, 6 };
int K = arr.size();
// Function Call
minTime(arr, N, K);
}
Java
// Java program for the above approach
import java.io.*;
import java.util.*;
class GFG {
// Function to return the minimum
// time to fill all the slots
public static void minTime(int arr[],
int N, int K)
{
// Stores visited slots
Queue<Integer> q = new LinkedList<>();
// Checks if a slot is visited or not
boolean vis[] = new boolean[N + 1];
int time = 0;
// Insert all filled slots
for (int i = 0; i < K; i++) {
q.add(arr[i]);
vis[arr[i]] = true;
}
// Iterate until queue is
// not empty
while (q.size() > 0) {
// Iterate through all slots
// in the queue
for (int i = 0; i < q.size(); i++) {
// Front index
int curr = q.poll();
// If previous slot is
// present and not visited
if (curr - 1 >= 1 &&
!vis[curr - 1]) {
vis[curr - 1] = true;
q.add(curr - 1);
}
// If next slot is present
// and not visited
if (curr + 1 <= N &&
!vis[curr + 1]) {
vis[curr + 1] = true;
q.add(curr + 1);
}
}
// Increment the time
// at each level
time++;
}
// Print the answer
System.out.println(time - 1);
}
// Driver Code
public static void main(String[] args)
{
int N = 6;
int arr[] = { 2, 6 };
int K = arr.length;
// Function Call
minTime(arr, N, K);
}
}
Python3
# Python3 program for the above approach # Function to return the minimum # time to fill all the slots def minTime(arr, N, K): # Stores visited slots q = [] # Checks if a slot is visited or not vis = [False] * (N + 1) time = 0 # Insert all filled slots for i in range(K): q.append(arr[i]) vis[arr[i]] = True # Iterate until queue is # not empty while (len(q) > 0): # Iterate through all slots # in the queue for i in range(len(q)): # Front index curr = q[0] q.pop(0) # If previous slot is # present and not visited if (curr - 1 >= 1 and vis[curr - 1] == 0): vis[curr - 1] = True q.append(curr - 1) # If next slot is present # and not visited if (curr + 1 <= N and vis[curr + 1] == 0): vis[curr + 1] = True q.append(curr + 1) # Increment the time # at each level time += 1 # Print the answer print(time - 1) # Driver Code N = 6 arr = [ 2, 6 ] K = len(arr) # Function Call minTime(arr, N, K) # This code is contributed by susmitakundugoaldanga
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to return the minimum
// time to fill all the slots
static void minTime(List<int> arr, int N, int K)
{
// Stores visited slots
Queue<int> q = new Queue<int>();
// Checks if a slot is visited or not
int []vis = new int[N + 1];
Array.Clear(vis, 0, vis.Length);
int time = 0;
// Insert all filled slots
for (int i = 0; i < K; i++)
{
q.Enqueue(arr[i]);
vis[arr[i]] = 1;
}
// Iterate until queue is
// not empty
while (q.Count > 0)
{
// Iterate through all slots
// in the queue
for (int i = 0; i < q.Count; i++)
{
// Front index
int curr = q.Peek();
q.Dequeue();
// If previous slot is
// present and not visited
if (curr - 1 >= 1 &&
vis[curr - 1]==0)
{
vis[curr - 1] = 1;
q.Enqueue(curr - 1);
}
// If next slot is present
// and not visited
if (curr + 1 <= N &&
vis[curr + 1] == 0)
{
vis[curr + 1] = 1;
q.Enqueue(curr + 1);
}
}
// Increment the time
// at each level
time++;
}
// Print the answer
Console.WriteLine(time-1);
}
// Driver Code
public static void Main()
{
int N = 6;
List<int> arr = new List<int>() { 2, 6 };
int K = arr.Count;
// Function Call
minTime(arr, N, K);
}
}
// THIS CODE IS CONTRIBUTED BY SURENDRA_GANGWAR.
Javascript
<script>
// Javascript program for the above approach
// Function to return the minimum
// time to fill all the slots
function minTime(arr, N, K)
{
// Stores visited slots
var q = [];
// Checks if a slot is visited or not
var vis = Array(N + 1).fill(false);
var time = 0;
// Insert all filled slots
for (var i = 0; i < K; i++) {
q.push(arr[i]);
vis[arr[i]] = true;
}
// Iterate until queue is
// not empty
while (q.length > 0) {
// Iterate through all slots
// in the queue
for (var i = 0; i < q.length; i++) {
// Front index
var curr = q[0];
q.pop();
// If previous slot is
// present and not visited
if (curr - 1 >= 1 &&
!vis[curr - 1]) {
vis[curr - 1] = true;
q.push(curr - 1);
}
// If next slot is present
// and not visited
if (curr + 1 <= N &&
!vis[curr + 1]) {
vis[curr + 1] = true;
q.push(curr + 1);
}
}
// Increment the time
// at each level
time++;
}
// Print the answer
document.write(time - 1);
}
// Driver Code
var N = 6;
var arr = [2, 6];
var K = arr.length;
// Function Call
minTime(arr, N, K);
// This code is contributed by noob2000.
</script>
Producción:
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por hemanthswarna1506 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA