Order of People Heights

You are given the following :

You need to return list of actual order of persons’s height

Input : 
Heights: 5 3 2 6 1 4
InFronts: 0 1 2 0 3 2

Output : 
actual order is: 5 3 2 1 6 4 

So, you can see that for the person with height 5, there is no one taller than him who is in front of him, and hence Infronts has 0 for him.

For person with height 3, there is 1 person ( Height : 5 ) in front of him who is taller than him.

You can do similar inference for other people in the list.

Method 1:

Order the people by heights, and then insert to the queue to the position by number of people in front.
For example, 
Height: 6 5 4 3 2 1
Fronts:  0 0 2 1 2 3

Queue: 
6
5 6
5 6 4
5 1 6 4
5 3 1 6 4
5 3 2 1 6 4

Solution 1:

Time: O(n^2)
Space: O(n)

public class Solution {
    public ArrayList<Integer> order(ArrayList<Integer> A, ArrayList<Integer> B) {
        Map<Integer, Integer> map = new TreeMap<>(Collections.reverseOrder());
        for (int i = 0; i < A.size(); i ++) {
            map.put(A.get(i), B.get(i));   
        }
        ArrayList<Integer> result = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            result.add(entry.getValue(), entry.getKey());
        }
        return result;
    }
}