Rearrange the positions by height.

• The basic idea is that we will find every person’s correct position one by one and place the person in that position.
• We will first sort the given array according to the persons’ height, and if two persons have the same height, we will sort them according to their second attribute value.
• After sorting, if we are iterating in ascending order, it is sure that all future persons will have height either equal to or more than the current person’s height.
• We will place the persons in the correct position by keeping the above point in mind.
• For example, if the list is [ 4,2 ] [ 2,0 ], [ 5,1] , [10,0]] . After sorting list, it’s- [ [2,0] , [ 4,2 ] [ 5,1 ], [ 10,0] ].
• Now person having a height of 2,  will be placed in the first position.
• For the second person with a height of ‘4’, if we place it at the second position, no person will have a height more than ‘4’ in front of it as 2 < 4. So we will skip the second position, which the future persons will occupy with a height of more than ‘4’.
• If we place it at the third position, then there will be only one person with a height of more than ‘4’ in front of it. So we will skip this position too.
• So we will place this person in the fourth position.
• Place all the persons as the above method.

Algorithm:

• Maintain a 2-D array 'ANS' (initialized all values to -1) to store the rearranged elements.
• Sort the elements according to the height of persons. In case of same height sort according to second attribute value.
• Take a variable ‘ COUNT ’ that will store the second attribute value of every person.
• Iterate for every person - i : 0 to N-1
  • Update 'COUNT' as the ATTRIBUTES[ i ][ 1 ].
  • Run a loop j : 0 to N-1 to find the correct position in the 'ANS' array.
    • If COUNT = 0 i.e we got required number of persons in front with height more than height of ‘i-th’ person and ANS [ j ][ 0] = -1 i.e current position is empty.
      • Place the ‘ i- th ‘ person at this ‘ j ‘ position.
    • Else
      • If ANS [ j ][ 0 ] = -1 or ANS [ j ][ 0 ] > ATTRIBUTES [ i ] [ 0 ] - Decrement ‘COUNT’.
• Return 'ANS'.

• In the first approach, we found the position for every person taking O( N ) time. We can reduce this time using a Binary index tree  ‘BIT’  of size ‘ N + 1 ’and binary search.
• The binary index tree works on the concept of the parent-child relationship. BIT [ p ] is parent of BIT [ c ] if p = c - ( c & - c ).
• BIT[ c ] will store the number of empty positions between index p and c.
• Now we will sort the ‘ ATTRIBUTES ‘ array the way we did in the first approach.
• Now for every ‘i-th ‘ person with ATTRIBUTES value ATTRIBUTES[ i ][ 0 ] and ATTRIBUTES[ i ][ 1], we will find an index by using binary search such that total count of empty space in front of this index position = ATTRIBUTES [ i ][ 1 ].
• For any index ‘ j ‘, this total count of empty spaces can be calculated by adding BIT[ j + 1 ] and all its parents.
• We can place the ‘ i-th ‘ person at this index.
• After placing a person at position ‘ index ‘, we need to decrement the count of empty positions by ‘1’ from ‘ index + 1 ‘  to ‘ N ‘.
• For this update, we will decrement BIT[ index + 1 ] and all its child elements by 1.

Parent of element in BIT at index ‘ i ‘ can be found at ( i + ( i & - i ) .) index

Child of the element in BIT at index ‘ i ‘ can be found at ( i - ( i & -i ) ) index.

Algorithm

• Initialize an array ‘ BIT ‘ of size ‘ N + 1 ‘ with all initial values ‘ 0 ‘.
• We will define a function “UPDATE”  that will take two parameters, ‘ index ‘ and ‘val’ and UPDATE BIT[ index ] and all its child as BIT[ index ] + val.
• We will define another function, “FIND_SUM” that will take a single variable, ‘ index ‘, and find the sum of BIT[ index ] and all its parents.
• Maintain a 2-D array 'ANS' (initialized all values to -1) to store the rearranged elements.
• Sort the person’s ATTRIBUTES.
• Run a loop i : 0 to N-1 for every person
  • Find an index by binary search such that FIND_SUM( index ) = ATTRIBUTES[ i ][ 1 ].
    • Put ans [ index ] = ATTRIBUTES[ i ].
  • Update ‘ BIT ‘ from index +1  to N by value ‘ -1. ‘
• Return 'ANS'.