0

Rearrange the positions by height.

Difficulty: MEDIUM
Avg. time to solve
25 min
Success Rate
75%

Problem Statement
Suggest Edit

You are given a 'N' x 2 matrices ‘ATTRIBUTES’ of some people standing in some random order where ‘ATTRIBUTES[ i ][ 0 ]’ denotes the height of the ‘ i-th ‘ person and ‘ATTRIBUTES[ i ][ 1 ]’ denotes the number of people that are in front of the ‘ i-th’ person having a height equal to or more than the height of the i-th person, i.e. ‘ATTRIBUTES[ i ][ 0 ]’ .

You need to rearrange the list such that every person is in its correct position, i.e., exactly ATTRIBUTES[ i ][ 1 ] number of people should be in front of ‘ i-th’ person with height more than ATTRIBUTES[ i ][ 0 ].

For Example
If the given list is [ [ 4,2] , [ 6, 1 ] , [ 10,0] [ 1,1] ]
The correct order should be [ [ 10,0] ,[1,1]  [ 6, 1 ] , [ 4,2] ]

A person with a height of ‘10’ has ‘0’ persons in front with a height more than ‘10’. So this person should be in the first place.
A person with a height of ‘1’ has ‘1’ person with a height of more than 1, so it is placed after [10,0].
A person with a height of ‘6’ has ‘1’ person in front with a height more than ‘ 6 ’.So this should be at the third position as 10> 6.
A person with a height of ‘ 4 ’ has ‘2’ persons in front with a height more than ‘ 4 ‘.So this should be at the last position as 10 > 4 and 6>4.
Input Format
The first line contains ‘T’, denoting the number of test cases to be performed.

The first line of each test case contains ‘N’, indicating the number of persons.

The following 'N' lines represent the 'N' x 2 matrix where each row denotes the two attributes value.
Output Format
For each test case, return the rearranged 'N' x 2 matrices having all the persons at their correct position.
Note:
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints
1 <= T <= 10
1 <= N <= 10^3
1 <= attributes[ i ][ 0 ] <= 10^5
1 <= attributes[ i ][ 1 ]  <= N

Time Limit: 1 sec
Sample Input 1
2
4
24 1
13 2
12 1
25 0   
2
8 0
4 0
Sample Output 1
25 0
12 1
24 1
13 2
4 0
8 0
Explanation Of Sample Input 1
Test Case 1: The correct order of this case is [ [ 25,0] [ 12,1 ], [ 24,1 ], [ 13,2 ] ].
A person with a height ‘25’ has 0 number of people in front with more height, So it is placed at the first position.
A person with a height of 12 has exactly 1 person in front with more height. As 25 > 12 So it is placed at the second position.
A person with a height of 24 also has only 1 person in front with greater height. As 25 > 24 and 12 < 24. 
The last person has a height of ‘13’, which is less than 24 and 25. Therefore this person has 2 people in front with more height.

Test Case 2: There are two people, and no one has persons in front with more height.Therefore correct positions will be [ [ 4,0 ], [ 8,0 ] ].
Sample Input 2
2
1
7 0
3
16 1
21 0
11 2
Sample Output 2
7 0
21 0
16 1
11 2
Reset Code
Full screen
copy-code
Console