Posible disposición de personas esperando para sentarse en un salón

Dado un entero N , una string binaria S y una array W[] . S denota la secuencia de N * 2 personas que ingresan al pasillo, donde 0 denota un niño y 1 denota una niña. W[] denota el ancho de los asientos en cada fila, donde cada fila consta de exactamente 2 asientos. La tarea es encontrar una posible disposición de las personas que ingresan a la sala de modo que se cumplan las siguientes condiciones:

• Un niño elige una fila en la que ambos asientos están vacíos. Entre todas esas filas, elige la que tiene el ancho mínimo.
• Una niña elige una fila en la que un asiento está ocupado por un niño. Entre todas esas filas, elige la que tiene el ancho máximo.

Ejemplos:

Entrada: N = 3, W[] = {2, 1, 3}, S = “001011”
Salida: 2 1 1 3 3 2
Explicación: 
Las personas ingresan al pasillo de la siguiente manera:
Persona 1: La primera persona es un niño , y todos los asientos están vacantes en este momento. Entonces, puede seleccionar cualquier fila y tomar asiento. Entre todas las filas, la que tiene el ancho mínimo de asiento es la 2ª. Entonces, la primera persona se sienta en un asiento en la segunda fila.
Persona 2: la segunda persona también es un niño, y ahora hay 2 asientos vacantes con el ancho de los asientos 2 y 3. Entonces, toma el asiento en la fila 1 ya que tiene un ancho mínimo de asientos.
Persona 3:La tercera es una niña, y puede sentarse en una fila en la que un asiento ya está ocupado, es decir, la fila 1 y la fila 2. Entre estas filas, la niña elige sentarse en la fila con el ancho máximo, por lo que se sienta en la fila 1.
Persona 4: el cuarto es un niño, y solo puede sentarse en la fila 3, ya que solo la tercera fila está vacante ahora.
Persona 5: La quinta es una niña, y puede sentarse en la fila 2 o en la fila 3, que tienen uno de los asientos ocupados. Así que elige la fila 3 porque tiene un asiento con más ancho que el de la fila 2.
Persona 6: Finalmente llega una niña y solo puede sentarse en la fila 2. 

Entrada: N = 3, W[] = {1, 3, 2}, S = “010011”
Salida: 1 1 3 2 2 3

Enfoque ingenuo: el enfoque más simple es tomar una array de pares de tamaño N y marcarlos como ocupados en la entrada de cada niño al autobús si ambos valores de pares están marcados como vacíos y tienen el ancho mínimo. Del mismo modo, marque ocupado en la entrada de niña solo cuando se marque un solo valor ocupado y con el ancho máximo. 

Tiempo Complejidad: O(N ² )
Espacio Auxiliar: O(N)

Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar una cola de prioridad . Siga los pasos a continuación para resolver el problema:

• Ordene la array dada arr[] del ancho de los asientos en orden ascendente.
• Cree una cola de prioridad y mantenga una variable de índice para realizar un seguimiento de la cantidad de filas ocupadas por un niño en arr[] .
• Cree un vector ans[] para almacenar el resultado.
• Itere a través de cada carácter de la string s y si s[i] es 0 , luego inserte el índice de arr[ind] en el vector y presione arr[ind] en la cola.
• De lo contrario, extraiga el elemento superior de la cola y luego presione el índice de este elemento en el vector.
• Después de los pasos anteriores. imprime el valor almacenado en ans[] .

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to find the arrangement
// of seating
void findTheOrder(int arr[], string s,
                  int N)
{
    // Stores the row in which the
    // ith person sits
    vector<int> ans;
 
    // Stores the width of seats along
    // with their index or row number
    pair<int, int> A[N];
 
    for (int i = 0; i < N; i++)
        A[i] = { arr[i], i + 1 };
 
    // Sort the array
    sort(A, A + N);
 
    // Store the seats and row for
    // boy's seat
    priority_queue<pair<int, int> > q;
 
    // Stores the index of row upto
    // which boys have taken seat
    int index = 0;
 
    // Iterate the string
    for (int i = 0; i < 2 * N; i++) {
        if (s[i] == '0') {
 
            // Push the row number at
            // index in vector and heap
            ans.push_back(A[index].second);
            q.push(A[index]);
 
            // Increment the index to let
            // the next boy in the next
            // minimum width vacant row
            index++;
        }
 
        // Otherwise
        else {
 
            // If girl then take top of
            // element of the max heap
            ans.push_back(q.top().second);
 
            // Pop from queue
            q.pop();
        }
    }
 
    // Print the values
    for (auto i : ans) {
        cout << i << " ";
    }
}
 
// Driver Code
int main()
{
    // Given N
    int N = 3;
 
    // Given arr[]
    int arr[] = { 2, 1, 3 };
 
    // Given string
    string s = "001011";
 
    // Function Call
    findTheOrder(arr, s, N);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
import java.util.*;
 
class Pair
{
    int first, second;
     
    Pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
 
class GFG{
 
// Function to find the arrangement
// of seating
static void findTheOrder(int arr[], String s,
                         int N)
{
     
    // Stores the row in which the
    // ith person sits
    List<Integer> ans = new ArrayList<Integer>();
 
    // Stores the width of seats along
    // with their index or row number
    List<Pair> A = new ArrayList<Pair>();
 
    for(int i = 0; i < N; i++)
    {
        Pair p = new Pair(arr[i], i + 1);
        A.add(p);
    }
 
    // Sort the array
    Collections.sort(A, (p1, p2) -> p1.first -
                                    p2.first);
 
    // Store the seats and row for
    // boy's seat
    PriorityQueue<Pair> q = new PriorityQueue<Pair>(
        N, (p1, p2) -> p2.first - p1.first);
 
    // Stores the index of row upto
    // which boys have taken seat
    int index = 0;
 
    // Iterate the string
    for(int i = 0; i < 2 * N; i++)
    {
        if (s.charAt(i) == '0')
        {
             
            // Push the row number at
            // index in vector and heap
            ans.add(A.get(index).second);
            q.add(A.get(index));
 
            // Increment the index to let
            // the next boy in the next
            // minimum width vacant row
            index++;
        }
 
        // Otherwise
        else
        {
             
            // If girl then take top of
            // element of the max heap
            ans.add(q.peek().second);
 
            // Pop from queue
            q.poll();
        }
    }
 
    // Print the values
    for(int i : ans)
    {
        System.out.print(i + " ");
    }
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given N
    int N = 3;
 
    // Given arr[]
    int arr[] = { 2, 1, 3 };
 
    // Given string
    String s = "001011";
 
    // Function Call
    findTheOrder(arr, s, N);
}
}
 
// This code is contributed by jithin

# Python3 program for the above approach
 
# Function to find the arrangement
# of seating
def findTheOrder(arr, s, N):
     
    # Stores the row in which the
    # ith person sits
    ans = []
 
    # Stores the width of seats along
    # with their index or row number
    A = [[] for i in range(N)]
 
    for i in range(N):
        A[i] = [arr[i], i + 1]
 
    # Sort the array
    A = sorted(A)
 
    # Store the seats and row for
    # boy's seat
    q = []
 
    # Stores the index of row upto
    # which boys have taken seat
    index = 0
 
    # Iterate the string
    for i in range(2 * N):
        if (s[i] == '0'):
 
            # Push the row number at
            # index in vector and heap
            ans.append(A[index][1])
            q.append(A[index])
 
            # Increment the index to let
            # the next boy in the next
            # minimum width vacant row
            index += 1
 
        # Otherwise
        else:
 
            # If girl then take top of
            # element of the max heap
            ans.append(q[-1][1])
 
            # Pop from queue
            del q[-1]
             
        q = sorted(q)
 
    # Print the values
    for i in ans:
        print(i, end = " ")
 
# Driver Code
if __name__ == '__main__':
     
    # Given N
    N = 3
 
    # Given arr[]
    arr = [ 2, 1, 3 ]
 
    # Given string
    s = "001011"
 
    # Function Call
    findTheOrder(arr, s, N)
 
# This code is contributed by mohit kumar 29

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
     
    // Function to find the arrangement
    // of seating
    static void findTheOrder(int[] arr, string s, int N)
    {
       
        // Stores the row in which the
        // ith person sits
        List<int> ans = new List<int>();
      
        // Stores the width of seats along
        // with their index or row number
        Tuple<int, int>[] A = new Tuple<int,int>[N];
      
        for (int i = 0; i < N; i++)
            A[i] = new Tuple<int,int>(arr[i], i + 1);
      
        // Sort the array
        Array.Sort(A);
      
        // Store the seats and row for
        // boy's seat
        List<Tuple<int, int>> q = new List<Tuple<int,int>>();
      
        // Stores the index of row upto
        // which boys have taken seat
        int index = 0;
      
        // Iterate the string
        for (int i = 0; i < 2 * N; i++)
        {
            if (s[i] == '0')
            {
      
                // Push the row number at
                // index in vector and heap
                ans.Add(A[index].Item2);
                q.Add(A[index]);
                q.Sort();
                q.Reverse();
      
                // Increment the index to let
                // the next boy in the next
                // minimum width vacant row
                index++;
            }
      
            // Otherwise
            else
            {
      
                // If girl then take top of
                // element of the max heap
                ans.Add(q[0].Item2);
      
                // Pop from queue
                q.RemoveAt(0);
            }
        }
      
        // Print the values
        foreach(int i in ans)
        {
            Console.Write(i + " ");
        }
    }
 
  // Driver code
  static void Main()
  {
    // Given N
    int N = 3;
  
    // Given arr[]
    int[] arr = { 2, 1, 3 };
  
    // Given string
    string s = "001011";
  
    // Function Call
    findTheOrder(arr, s, N);
  }
}
 
// This code is contributed by divyesh072019.

<script>
// Javascript program for the above approach
 
// Function to find the arrangement
// of seating
function findTheOrder(arr, s, N)
{
 
    // Stores the row in which the
    // ith person sits
    let ans = [];
  
    // Stores the width of seats along
    // with their index or row number
    let A = [];
  
    for(let i = 0; i < N; i++)
    {
        let p = [arr[i], i + 1];
        A.push(p);
    }
  
    // Sort the array
    A.sort(function(p1, p2){return p1[0]-p2[0];});
  
    // Store the seats and row for
    // boy's seat
    let q = [];
  
    // Stores the index of row upto
    // which boys have taken seat
    let index = 0;
  
    // Iterate the string
    for(let i = 0; i < 2 * N; i++)
    {
        if (s[i] == '0')
        {
              
            // Push the row number at
            // index in vector and heap
            ans.push(A[index][1]);
            q.push(A[index]);
  
            // Increment the index to let
            // the next boy in the next
            // minimum width vacant row
            index++;
        }
  
        // Otherwise
        else
        {
              
            // If girl then take top of
            // element of the max heap
            ans.push(q[0][1]);
  
            // Pop from queue
            q.shift();
        }
        q.sort(function(a,b){return b[0]-a[0];});
    }
  
    // Print the values
    for(let i=0;i< ans.length;i++)
    {
        document.write(ans[i] + " ");
    }
}
 
// Driver Code
// Given N
let N = 3;
 
// Given arr[]
let arr = [ 2, 1, 3 ];
 
// Given string
let s = "001011";
 
// Function Call
findTheOrder(arr, s, N);
 
// This code is contributed by patel2127
</script>

2 1 1 3 3 2

Complejidad de tiempo: O(N * log N)
Espacio auxiliar: O(N)