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