Correctness of algorithm?

help
,
1

Hi i have following problem
You are given two array, first array contain integer which represent heights of persons and second array contain how many persons in front of him are standing who are greater than him in term of height and forming a queue. Ex

A: 3 2 1

B: 0 1 1

It means in front of person of height 3 there is no person standing, person of height 2 there is one person in front of him who has greater height then he, similar to person of height 1. Your task to arrange them
Ouput should be.
3 1 2

My approach
1.Sort persons according to their frequency(no. of taller person).
2.Now fix the position of each person in appropriate position.
for example:

3 1 2 4

0 2 1 0

after sorting

3 4 2 1

0 0 1 2

now we see that first and second person are at right place so we move third person to it’s right position that is 2nd(base index 1) as he has only one taller before him.

3 2 4 1

0 1 0 2

now for 4th person we just place it at 3rd position

3 2 1 4

0 1 2 0

final answer.

I think it has O(n^2) complexity.Can we do better, and what about correctness of this algorithm?

2

solution:
create a binary tree using following steps:
consider second array the one with no of peoples having more height as a priority for the first array…
now move one by one in array 1 and insert elements like this
1.if priority is greater move to right or less move to left
2.if priority is same move to right if height is greater else move left
3.balance the tree
O(nlogn) …
inorder is the answer…