Possible arrangement of persons waiting to sit in a hall | Java 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
import java . io . * ; import java . util . * ; class Pair { int first , second ; Pair ( int first , int second ) { this . first = first ; this . second = second ; } } class GFG { static void findTheOrder ( int arr [ ] , String s , int N ) { List < Integer > ans = new ArrayList < Integer > ( ) ; List < Pair > A = new ArrayList < Pair > ( ) ; for ( int i = 0 ; i < N ; i ++ ) { Pair p = new Pair ( arr [ i ] , i + 1 ) ; A . add ( p ) ; } Collections . sort ( A , ( p1 , p2 ) -> p1 . first - p2 . first ) ; PriorityQueue < Pair > q = new PriorityQueue < Pair > ( N , ( p1 , p2 ) -> p2 . first - p1 . first ) ; int index = 0 ; for ( int i = 0 ; i < 2 * N ; i ++ ) { if ( s . charAt ( i ) == '0' ) { ans . add ( A . get ( index ) . second ) ; q . add ( A . get ( index ) ) ; index ++ ; } else { ans . add ( q . peek ( ) . second ) ; q . poll ( ) ; } } for ( int i : ans ) { System . out . print ( i + " ▁ " ) ; } } public static void main ( String [ ] args ) { int N = 3 ; int arr [ ] = { 2 , 1 , 3 } ; String s = "001011" ; findTheOrder ( arr , s , N ) ; } }