Suppose you are given the following :
- A positive number N
- Heights : A list of heights of N persons standing in a queue
- InFront: A list of numbers corresponding to each person (P) that gives the number of persons who are taller than P and standing in front of P
Write an algorithm to reconstruct the queue.
Solution :
It is clear that we can try to simulate the manual approach of position allocation once the smallest element has been placed. So we would first like to sort the heights array. But we also don’t want to loose the corresponding order of InFront values. So we use map data structure with heights as key and corresponding InFront as value.
We can start arranging peoples from smaller to higher heights. As we can see people with smallest height (index i) will come at index InFront[i] ( considering 0 based indexing) because all the people infront of it will have larger heights . Same we can do for all. So by observation we can say that, person with ith smallest height will be arranged at (i+1)th empty location starting from first. People already placed are not taller that the current person. And people placed after are taller than the current. So we have to find a place such that the number of empty positions in the front
is equal to the InFront value of this person.
Example :
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 Empty locations are : – – – – – – [1] for 1(3) it will be at 4th empty location – – – 1 – – [2] for 2(2), at 3rd empty location , because there are 2 persons with height>2 in front of 2. – – 2 1 – – [3] for 3(1) at 2nd empty location – 3 2 1 – – [4] for 4(2) at 3rd empty location – 3 2 1 – 4 [5] 5(0) at 1st empty location 5 3 2 1 – 4 [6] 6(0) at 1st empty location 5 3 2 1 6 4