CareerCup

This can be solved using rope data structure.
It's like a binary tree except that each node maintains the number of nodes in the left subtree+1 for itself. Whenever a new number is inserted, if the value is smaller than the node's number it goes to the left otherwise right. When it goes to the right, the value of the node is decreased by the value of the branch node.
Ex Nodes: 6 5 4 3 2 1
values: 0 0 0 2 2 4
1. Make 6 as the root of the tree, its value = 1;
2. Insert 5. Value of 5(0) < value of 6(1) so it goes to the left. New value of 6 = 2, value of 5=1;
3. Insert 4, value of 4 < value of 6 so goes to the left; again goes to the left of 5. New values of 4 = 1, value of 5 = 2, value of 6 = 3
4. Insert 3, goes to the left of 6 but to the right of 5. New values 6 = 4, value of 3 = 1, rest unchanged
5. Insert 2, goes to the left of 6, right of 5 (value of 2 is decreased by value of 5 so its now 0), left of 3. New values of 3 = 2, value of 2 = 1, value of 6 = 5
6. Insert 1, goes to the left of 6, right of 5, right of 3.
Do an in-order traversal of tree. It is imperative to insert the nodes in decreasing order

Though I like the idea of sorting using the comparator as mentioned above by amitb2108 but below is the approach that came to my mind first.
lets say height[] = {3,1,2,4}
pos[] = {0,2,1,0}; //no of persons greater height than him
1. create an array of person struct of size n and fill the data from the above two arrays
struct person
{
int height;
int num;
};
2. Sort the person array with height as the key in decreasing order. o(nlgn)
index 0,1,2,3
person[] = {4,3,2,1}
{0,0,1,2} //person.num
3. Remember the index of array represents the no of persons greater in front of the current index. e.g. person with height 3 has array index 1, so 1 person is in front of him with greater height. But we need to have 0 no of person greater than 3, so swap it with index 0.
person[] = {3,4,2,1} //after swapping 3
//2 has only one person in front but index of 2 is 2 currently there are 2 persons
//swap it with index 1
person[] = {3,2,4,1}
//1 has only 2 persons in front but index of 1 is 3, so currently there are 3 persons
//swap it with index 2
person[] = {3,2,1,4}
the idea is, previous index, has a person with greater height than current index. The previous index person's position is already set. Now if we move this previous index person towards right it doesn't impact the position of this person. e.g. person with height 4, if we move this person towards the right, still the no of persons with greater height will be 0.
Total complexity = o(nlogn)

You can sort the list of persons (person: height,numTallBeforePerson) using the following comparator:

class Comparison implements Comparator<Person>{
    @Override
    public int compare(final Person p1, final Person p2){
        if (p1.numTallBeforePerson == p2.numTallBeforePerson){
            if (p1.height < p2.height) {
                return -1;
            }
            else{
                return 1;
            }
        }
        else if (p1.numTallBeforePerson < p2.numTallBeforePerson) {
            if (p1.height < p2.height)
                return -1;
        }
        else if (p1.numTallBeforePerson > p2.numTallBeforePerson) {
            if (p1.height > p2.height)
                return 1;
        }
        return -1;
    }
}

The idea is that a shorter person standing after a taller one will have larger number of tall people before him than the taller person. Time complexity: O(n log n)

Backtrack.

Let's say the first array is height array and the second is count array. Sort the count array from low to high (say [0,1,1]). Start from the first height 3 (corresponding to count 0), the root node of the backtrack tree is (3), then insert the second height 2, generating one child node (3,2). Then insert the third height 1, generating one child node (3,1,2). If a node does not generate any child node, then it is an dead end. In this case, backtrack to the upper level node to visit its next child node.

This way you can find all possible sequences satisfying the two arrays. And you can confidently know if there is no such sequence at all.

sort the person by the height
if the count is not zero, swap the person on the right who is higher until the count become zero

time: O(n^2)

example 1

235461
020004

sort

123456
402000

swap 1

234516
020000

swap 3

245316
000000

example 2

3 1 2 4
0 2 1 0

sort

1 2 3 4
2 1 0 0

swap 1

2 3 1 4
1 0 0 0

swap 2

3 2 1 4
0 0 0 0

My algorithm: Time -- O (N LOG N) & Space --O(N) .. please let me know your comments... it seems to work for all cases, let me know if I am missing something...

Approach:

(1) Sort the input in descending order of size -- O(N LOG N)
(2) Use a stack based approach -- O(N) : (find below)

Given:

A[] = {1,2,3,4,5}
b[]= {3,1,1,1,0}

Step 1: Sort A (and hence B) --> A[] = {5,4,3,2,1} B= {0,1,1,1,3} // Here, this is still O(N.LOG N)

Step 2: Stack based algorithm (Say have 2 stacks: S1->stack.new, S2->stack.new)

for index in a: 
	if (s1.isEmpty())
		s1.push(a[index])
		continue
	while(s1.size > b[index])	
		s2.push(s1.pop())
	s1.push(a[index])
	while(! s2.isEmpty()) s1.push(s2.pop())

Given Hight Arrays H[], Queue Arrays Q[], Return Output O[]
1. Sort H in desc order as H'
2.Loop
while N--;
pick Q[N] th element of H' as O[N];
adjuct H' // remove H'[Q[N]] in H'

Isn't the question incorrect: if the heights are 3,2,1 in some height-units, shouldn't the array be 0,1,2 - representing no one in front of 3, 1 guy in front of 2 and 2 guys in front of 1. Or maybe i am missing something that rest everyone is not - pls enlighten

I found that the max element is at the rightmost position(call pos) whose value is zero in the array b, so everytime I insert the max element of the remaining elements, and all the elements on the right of pos in b should decrement by one, because one max element is eliminated on the left, and carry on untill no elements left in a, and here is my code:(O(n^2), I think my algorithm supports duplicate heights)

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>

//time complexity is n^2
void rank( int a[], int b[], int n )
{
	std::vector<int> c( n, -1 );
	std::sort( a, a+n, std::greater<int>() );

	int j;
	for( int i = 0; i < n; ++i )
	{
		j = n - 1;
		for( ; j >= 0; --j ) 
			if( b[j] == 0 && c[j] == -1 ) break;
		for( int k = j + 1; k < n; ++k  ) --b[k];
		c[j] = a[i];
	}

	for( int i = 0; i < n; ++i ) std::cout << c[i] << " ";
	std::cout << std::endl;
}

int main( int argc, char* argv[] )
{
	/*int a[] = { 3, 2, 1 };
	int b[] = { 0, 1, 1 };
	int n = 3;*/

	int a[] = { 7, 4, 5, 9, 8, 1, 4, 3 };
	int b[] = { 0, 0, 2, 2, 2, 4, 2, 2 };
	int n = 8;
	rank( a, b, n );

	return 0;
}

How about next idea.
The last element of second array - let call it array of inversions in following, is always that we have in desc order. For example.
3 2 1. 2
0 1 1 - is element with index 1 in desc order. so it must be placed the in that way:
* * 2
0 1 *
so 1 - is element with 1 index in desc order without 2. it must be placed there
* 1 2
and following
3 1 2

We process array from right to left. element i must be placed with element from first array without already processed element in desc order.

Use an order stastisc tree:
- Insert all the heights into an order statistic tree
- for i from B.length -1 to 0:
- what is the B[i] order statistic value in the order statistic tree
- remove that value from the tree and insert it into the results array at i

Time is nlogn (n queries for order statistics)
Space is n (order statistic tree size)

Another O(n logn) time and O(n) space solution. Please correct me if there are issues.

package heighttallinfront;

import java.util.LinkedList;
import java.util.Collections;
import java.util.Comparator;

public class Main {
	
	/**
	 * Data structure to hold the necessary values
	 */
	private static class PersonData {
		int height, tallPersonsInFront;
		
		public PersonData(int height, int tallPersonsInFront) {
			this.height = height;
			this.tallPersonsInFront = tallPersonsInFront;
		}
		
		public String toString() {
			return "[" + height + ", " + tallPersonsInFront + "]";
		}
	}
	
	/**
	 * O(n) for building the data structure that holds both height and number of taller persons ahead of him
	 * @param heights
	 * @param tallPersonsInFront
	 * @return
	 */
	private static LinkedList<PersonData> buildPersonDataList(int[] heights, int[] tallPersonsInFront) {
		final LinkedList<PersonData> personDataList = new LinkedList<PersonData>();
		for (int i = 0; i < heights.length; i++) {
			personDataList.add(new PersonData(heights[i], tallPersonsInFront[i]));
		}
		return personDataList;
	}
	
	/**
	 * O(n logn) Sorting of Java (merge sort)
	 * @param personDataList
	 */
	private static void sortPersonDataListByHeight(final LinkedList<PersonData> personDataList) {
		Collections.sort(personDataList, new Comparator<PersonData>() {
			@Override
			public int compare(PersonData p1, PersonData p2) {
				// If the heights are the same
				// The one with the less taller persons in front of him should be come before the other
				// Since the person behind should have at least the same number of taller persons in front of him
				if (p1.height == p2.height) {
					return p1.tallPersonsInFront - p2.tallPersonsInFront;
				}
				return p1.height - p2.height;
			}
		});
	}
	
	/**
	 * O(n) since it visits all the nodes from right to left (inserting each element into their "appropriate" places)
	 * The idea is to move each person to the right by the number of taller persons in front of him.
	 * Remember that the list is currently sorted in increasing order so moving each person to the right means you're
	 * moving at the back of a person taller than you.
	 * @param personDataList
	 */
	private static void sortPersonDataListByTallPersonsInFront(final LinkedList<PersonData> personDataList) {
		final int personDataListSize = personDataList.size();
		for (int i = personDataListSize - 1; i >= 0; i--) {
			PersonData p = personDataList.get(i);
			insertNode(personDataList, i, i + p.tallPersonsInFront + 1);
		}
	}
	
	/**
	 * Assume O(1) since it's a linked list
	 * @param personDataList
	 * @param a
	 * @param b
	 */
	private static void insertNode(final LinkedList<PersonData> personDataList, int a, int b) {
		PersonData person = personDataList.get(a);
		personDataList.add(b, person);
		personDataList.remove(a);
	}
	
	/**
	 * O(n) to rearrange the two arrays
	 * @param personDataList
	 * @param heights
	 * @param tallPersonsInFront
	 */
	private static void buildArrangedHeightsAndTallPersonsInFront(final LinkedList<PersonData> personDataList, int[] heights, int[] tallPersonsInFront) {
		for (int i = 0; i < heights.length; i++) {
			final PersonData p = personDataList.get(i);
			heights[i] = p.height;
			tallPersonsInFront[i] = p.tallPersonsInFront;
		}
	}
	
	/**
	 * O(n logn) given the operations present in this method
	 * Actual is O(n (logn + 3))
	 * @param heights
	 * @param tallPersonsInFront
	 */
	public static void sortInput(int[] heights, int[] tallPersonsInFront) {
		if (heights == null || tallPersonsInFront == null || heights.length != tallPersonsInFront.length) {
			System.out.println("Invalid input.");
		} else if (heights.length == 0) {
			System.out.println("No person in line.");
		} else if (heights.length == 1) {
			System.out.println("Only one person in line.");
		}
		final LinkedList<PersonData> personDataList = buildPersonDataList(heights, tallPersonsInFront); // O(n)
		sortPersonDataListByHeight(personDataList); // O(n logn)
		sortPersonDataListByTallPersonsInFront(personDataList); // O(n)
		buildArrangedHeightsAndTallPersonsInFront(personDataList, heights, tallPersonsInFront); // O(n)
	}

	public static void main(String[] args) {
		int[] heights = new int[] { 3, 2, 1, 1 };
		int[] tallPersonsInFront = new int[] { 0, 1, 2, 1};
		sortInput(heights, tallPersonsInFront);
		printArray(heights);
		printArray(tallPersonsInFront);

	}
	
	public static void printArray(int[] input) {
		printArray(input, 0, input.length - 1);
	}
	
	public static void printArray(int[] input, int start, int end) {
		for (int i = start; i <= end; i++) {
			System.out.print("+--+");
		}
		System.out.println();
		for (int i = start; i <= end; i++) {
			System.out.print("|" + String.format("%02d", input[i]) + "|");
		}
		System.out.println();
		for (int i = start; i <= end; i++) {
			System.out.print("+--+");
		}
		System.out.println();
	}

}

One solution: Every time, select the smallest number with front[] = 0.
e.g. height[] = {3, 1, 2, 4}, front[] = {0, 2, 1, 0}
1) Find the smallest number from height[] that has 0 in front[], in this case it is 3, then 3 is 1st element in the queue.
2) For rest of the elements i in height[], if it is smaller than 3, then front[i] - 1, otherwise keep front[i] the same.
Go back to 1)

This is pretty much like topological sorting; each time remove the node with indegree == 0.

Observe that in any arrangement of heights, the smallest element can have one and only one spot to go.

eg.
{ 3, 1, 2, 4 }
{1, 2, 2, 0}

1 is the smallest element and needs to have 2 elements ahead of it. All other elements are larger, so it must only be able to go into ar[2]. After placing 1 in ar[2], count 2 empty spaces, skip 2 because it's taken and place 2 into ar[3]. 3 needs 1 empty space and goes into ar[1] and 4 into ar[0].

Fail if there are no available spots. Collisions or cases like

{ 3, 1, 2, 4, 1 }
{1, 2, 2, 0, 2}

are handled elegantly by the space counting.

Unoptimized this is O(n^2).

Here is a python code that runs in O(n logn) time. If you use some sorting algorithm, say radix sort, that runs in O(n) time, then this algorithm will take O(n) time.

import copy
a = [int(i) for i in raw_input().split(' ')]
b = [int(i) for i in raw_input().split(' ')]
n = len(a)

shift = [0 for i in range(n)]
d = [0 for i in range(n)]
queue = [-1 for i in range(n)]

c = copy.deepcopy(a)
c.sort()
for i in range(n):
        temp = c.index(a[i])
        d[temp] = b[i]

for i in range(n):
        queue[d[i]+shift[d[i]]] = c[i]
        shift[d[i]] += 1

print queue

Consider line[] array where people have to be placed.

Assumption : all people have distinct height from 0 to N-1. so sort A and hence B array (along with A) in increasing order.

Now A=[0,1,2,3,4...].

So, now we can ignore A[] and only consider B[] ans array where B[i] is = number of people with greater height in front that person of height i.

Now, in line[], 0th person will be at index B[0] since there are exactly B[0] person > than 0th person. For second largest person if B[1] < B[0] 1 ahead of 0th person in line[]. else after 0th person. Eg

if B=[3,2,....] line = [--10-------] - is space to be taken by others. 0th person took 4th free seat. 1st took 3rd free

if B=[3,3,....] line = [---01------] => 0th person took 4th free seat. 1st took 4th free seat, after 0 took its seat. so 1 basically took 5th seat

notice how 1 after 0 in line.

So basically you have a set of free seats and each person comes and takes whatever is left.

So Algo : put 0th person at index B[0] in line[]. remove B[0] index from line[] from free seat list. next for ith person, traverse whatever free spaces are left in line[] from index 0 and place them there.
pseudo code :

for(i=0;i<N;i++)

{

c=0;

for(j=0;j<N;j++)

{

if(line[j]==free)

c++;

if(c==B[i])   

break;   //after skipping B[i] "free" seats in line, make ith height person settle down.

}

line[j]=B[i];  //settle down

}

Above is O(N*N)

can be reduced to O(N) is we can find out in O(1) which seat index a person will get currently if he has to skip x seats

O(nlogn) : Consider line as a skip linked list. node has value 0 to N-1. for each person , given x seats to skip - find xth node using bin search on skip list. delete that node. update skip list.

O(nlogn) : See line as a balanced BST. nodes have value of index 0 to N-1. each node also has the value 'number of nodes in this tree' in tree rooted at it.

construct N node such balanced BST in O(N) (yes, find out how this can be constructed in O(N) yourself) (or to simplify , make in O(logn))

Sort A hence B in inc order. Take B[i] for ith smallest person. Delete B[i]th "number" (not value) of node from the tree. this nodes value = persons index in line. Also update 'number of nodes in this tree' for all nodes effected by delete - O(logn) per person. total nlogn.

My take on this

1. we need to arrange the numbers based on the index difference given
{3,2,1}->{0,1,1} means
{3} has none taller in front, {2} has 1 taller, {1} has 1 taller
so {3}>{1}>{2} or (3 greater than 1 greater than 2)

2. {5,4,3,2,1}->{0,0,0,0,0} means
{5} has none taller in front, {4} has none taller in front, {3} has none taller in front, ...
so {1}>{2}>{3}>{4}>{5}

3. {5,4,3,2,1}->{0,1,2,3,4} means
{5}>{4}>{3}>{2}>{1}

4. looking at the options above we can easily build an iteration to move the person to the index on the second array, taken the example {3,2,1}->{0,1,1}, steps are
-move {3} to position 0 - nothing to do
-move {2} to position 1 - nothing to do
-move {1} to position 1 - move {1} to position 1, {2} will need to move 1 position down

algorithm is quite simple

public int[] orderTallPerson(int[] heights, int[] tallerThen) {
		for (int i=0; i<tallerThen.length; i++) {
			if (tallerThen[i] != i) {
				int height = heights[i];
				int pos = tallerThen[i];
				for (int j=i; j>pos; j--) {
					//move person height forward to back of queue
					heights[j] = heights[j-1];
					//move taller index to back of the queue
					tallerThen[j] = tallerThen[j-1];
				}
				heights[pos] = height;
			}
		}
		return heights;
	}

Below should be true

int heights[]    = {6,5,4,3,2,1};
		int tallerThen[] = {0,0,0,2,2,4};
		int result[] = {4,5,2,3,1,6};
	
		int heights[]    = { 7, 4, 5, 9, 8, 1, 4, 3 };
		int tallerThen[] = { 0, 0, 2, 2, 2, 4, 2, 2 };
		int result[] = {4,7,3,4,8,9,1,5};

		int heights[]    = { 7, 4, 5, 9, 8, 1, 4, 3 };
		int tallerThen[] = { 0, 1, 1, 0, 1, 5, 4, 6 };
		int result[] = {5,1,9,8,4,3,7,4};
		
		int heights[]    = { 5,4,3,2,1 };
		int tallerThen[] = { 0,0,0,0,0 };
		int result[] = {1,2,3,4,5};

		int heights[]    = { 5,4,3,2,1 };
		int tallerThen[] = { 0,1,2,3,4 };
		int result[] = {5,4,3,2,1};

Variant of tree travel/shortest path/bfs. with number of element in front as level. and on each level shortest first.
or just sort the elements by value and then stable sort on number of elements greater

My solution is in O(2n)

public int follow(int startNumber, Map<Integer, Pair<Boolean, Integer>> pairMap) {
        Pair<Boolean, Integer> currentPair = pairMap.get(startNumber);
        if (currentPair == null) {
            return 0;
        } else {
            if (currentPair.getFirst()) {
                return currentPair.getSecond();
            } else {
                currentPair.setFirst(true);
                int result = follow(startNumber + 1, pairMap) + 1;
                currentPair.setSecond(result);
                return result;
            }
        }
    }

    public void q1() {
        int[] ints = {7,6,5,4,2,3,1};
        // first integer , in the pair first is vis9ted, second is the score
        Map<Integer, Pair<Boolean, Integer>> pairMap = new HashMap<Integer, Pair<Boolean, Integer>>();
        for (Integer i : ints) {
            pairMap.put(i, new Pair<Boolean, Integer>(false, 1));
        }

        int[] results = new int[ints.length];
        for (int i = 0; i < ints.length; i++) {
            int result = follow(ints[i], pairMap);
            results[i] = result;
            System.out.println(ints[i] +":"+result);
        }

    }

class person {  
    int h;
    int r;
    public person(int h1, int r1) {
        h = h1;
        r = r1;
    }
    
    public int getH() { return h;}
    public int getR() { return r;}
 }


public static void arrangHeight(int height[], int rank[]) {
    
    ArrayList <person> p = new ArrayList <person> ();
    int i;
    int n = height.length;
    for(i = 0; i < n; i++) {
        person p1 = new person(height[i], rank[i]);
        p.add(p1);
    }
    
    Collections.sort(p, new comparator() {
        public int compare(person p1, person p2) {
            return p2.getH - p1.getH;
        }
    });
    
  //  height[] = {3,1,2,4} 
  //  pos[] = {0,2,1,0}
  // op -> [4, 3, 2, 1]
  // op    [0, 0, 1, 2]
  
  ArrayList <Integer> out = new ArrayList<Integer>();
  out.add(p.get(0).getH());
  for (i = 1; i < n; i++) {
      person p1 = p.get(i);
      int pos = p1.getR();
      out.add(pos, p1.getH());
  }
  System.out.println(out);
}

O(n^2)
1. sort persons by height and num greater before
2. find place for each person (from short to high)

class Person{
    public int Height;
    public int Greater;
    public static bool operator > (Person p1, Person p2){
        return p1.Height > p2.Height || p1.Height == p2.Height && p1.Greater > p2.Greater;
    }
    public static bool operator < (Person p1, Person p2){
        return p1.Height < p2.Height || p1.Height == p2.Height && p1.Greater < p2.Greater;
    }
    public static bool operator == (Person p1, Person p2){
        return p1.Height == p2.Height && p1.Greater == p2.Greater;
    }
}
int[] HeightSort(int[] heights, int[] greaters){
    if(heights == null || greaters == null || heights.Length != greaters.Length){
        return null;
    }
    int len = heights.Length;
    Person[] ps = new Person[len];
    for(int i = 0; i < len; ++i){
        ps[i] = new Person{Height = heights[i], Greater = greaters[i]};
    }
    QuickSort(ps);
    int[] ret = new int[len];
    for(int i = 0; i < len; ++i){ret[i] = -1;}
    for(int i = 0; i < len; ++i){
        int j = 0;
        for(int idx = 0; idx < len; ++idx){
            if(j == ps[i].Greater){
                break;
            }
            if(ret[idx] == -1){
                ++j;
            }
        }
        if(idx == len){
            return null;
        }
        ret[idx] = ps[i].Height;
    }
    return ret;
}

O(n^2)
1. sort persons by height and num greater before
2. find place for each person (from short to high)

class Person{
    public int Height;
    public int Greater;
    public static bool operator > (Person p1, Person p2){
        return p1.Height > p2.Height || p1.Height == p2.Height && p1.Greater > p2.Greater;
    }
    public static bool operator < (Person p1, Person p2){
        return p1.Height < p2.Height || p1.Height == p2.Height && p1.Greater < p2.Greater;
    }
    public static bool operator == (Person p1, Person p2){
        return p1.Height == p2.Height && p1.Greater == p2.Greater;
    }
}
int[] HeightSort(int[] heights, int[] greaters){
    if(heights == null || greaters == null || heights.Length != greaters.Length){
        return null;
    }
    int len = heights.Length;
    Person[] ps = new Person[len];
    for(int i = 0; i < len; ++i){
        ps[i] = new Person{Height = heights[i], Greater = greaters[i]};
    }
    QuickSort(ps);
    int[] ret = new int[len];
    for(int i = 0; i < len; ++i){ret[i] = -1;}
    for(int i = 0; i < len; ++i){
        int j = 0;
        for(int idx = 0; idx < len; ++idx){
            if(j == ps[i].Greater){
                break;
            }
            if(ret[idx] == -1){
                ++j;
            }
        }
        if(idx == len){
            return null;
        }
        ret[idx] = ps[i].Height;
    }
    return ret;
}

I think an elegant solution to this problem would be to sort the array of heights and also put array B in that order O(nlogn)

Make another array of size n as our position array.
Then get the element of the smallest height and see how many people are in front of him and place him into the index of that our position array.

Keep taking the next smallest element with x people in front of him. Start from the beginning of the array and count x non filled spaces in the array and place it there.

This is because the non filled spaces in the array will have height greater than that of our element while the filled spaces will have height less than our element so we can ignore those elements.

So our overall complexity is O(nlogn)

I have a very simple O(nlogn) solution I'm finding difficult to explain

Calculate a prefix big enough so that it's bigger than every other number
prefix = pow(10, ciel(log10(n)) + 1))

now create an array where each cell's value is
height + prefix * number_heigher_infront

Now, sort the new array ascending and remove from each number (prefix * number_heigher_infront)

Voila!

My solution in C++. The list of (Heights, Count of people in front) is sorted based on the height. Then each person is added - in order - at the position given by the count of people in front of him. We maintain a "jump" table at each step in order to jump over position occupied by a smaller person. The algorithm time complexity is O(n log n). Reviews are welcome :

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

struct Person {
    int height;
    int count;
    bool operator<(const Person other) const {
        return (height < other.height);
    }
};

vector<int> arrange(vector<int> Heights, vector<int> Counts) {
    vector<int> arranged(Heights.size(), -1);
    vector<int> jump(Heights.size(), -1);
    vector<Person> Persons;
    for (int i = 0; i < Heights.size(); ++i) {
        Persons.push_back((Person){Heights[i], Counts[i]});
    }
    sort(Persons.begin(), Persons.end());
    int pos;
    for (vector<Person>::iterator it = Persons.begin(); it != Persons.end(); ++it) {
        pos = (jump[it->count] == -1) ? it->count : jump[it->count];
        arranged[pos] = it->height;
        jump[it->count] = (jump[pos + 1] == -1) ? pos + 1 : jump[pos + 1];
    }
    return arranged;
}

int main(int argc, char** argv) {
    vector<int> Heights;
    Heights.push_back(3);
    Heights.push_back(2);
    Heights.push_back(1);
    vector<int> Counts;
    Counts.push_back(0);
    Counts.push_back(1);
    Counts.push_back(1);
    vector<int> arranged = arrange(Heights, Counts);
    for (vector<int>::iterator it = arranged.begin(); it != arranged.end(); ++it) {
        cout << *it << endl;
    }
    return 0;
}

I solved it by recursive form.
These are persudo code.

vector<int> answer;
	sort(A.begin(), A.end())
	void sol( list<int> A, list<int> B) {
		if( A.empty() == true ) return;
		int cnt = count_number_of_0(B);
		answer.push_back(A[A.length()-cnt]);
		A.erease(A.length()-cnt);
		B.pop_front;
		for( x in B ) if(x>0) x--;
		
	}

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...

I'm using LinkedList for the this. Sort the tallCount[] in ascending order and accordingly re-position the items in heights[]. This is capable of handling the duplicate elements also.

public class FindHeightOrder {

	public int[] findOrder(final int[] heights, final int[] tallCount) {
		if (heights == null || heights.length == 0 || tallCount == null
				|| tallCount.length == 0 || tallCount.length != heights.length) {
			return null;
		}
		LinkedList list = new LinkedList();
		list.insertAtStart(heights[0]);
		for (int i = 1; i < heights.length; i++) {
			if (tallCount[i] == 0) {
				Link temp = list.getHead();
				while (temp != null && temp.getData() <= heights[i]) {
					temp = temp.getLink();
				}
				if (temp != null) {
					if (temp.getData() <= heights[i]) {
						list.insertAfterElement(temp.getData(), heights[i]);
					} else {
						list.insertAtStart(heights[i]);
					}
				} else {
					list.insertAtEnd(heights[i]);
				}
			} else {
				Link temp = list.getHead();
				int pos = tallCount[i];
				while (temp != null
						&& (temp.getData() <= heights[i] || pos-- > 0)) {
					temp = temp.getLink();
				}
				if (temp != null) {
					if (temp.getData() <= heights[i]) {
						list.insertAfterElement(temp.getData(), heights[i]);
					} else {
						list.insertBeforeElement(temp.getData(), heights[i]);
					}
				} else {
					list.insertAtEnd(heights[i]);
				}
			}
		}
		Link fin = list.getHead();
		int i = 0;
		while (fin != null) {
			heights[i++] = fin.getData();
			fin = fin.getLink();
		}
		return heights;
	}

	public class Link {

		private int data;
		private Link link;

		public Link(int data) {
			this.data = data;
		}

		public int getData() {
			return data;
		}

		public void setData(int data) {
			this.data = data;
		}

		public Link getLink() {
			return link;
		}

		public void setLink(Link link) {
			this.link = link;
		}

		@Override
		public String toString() {
			return this.data + " -> "
					+ (this.link != null ? this.link : "null");
		}

	}

	public class LinkedList {

		private Link head;

		public Link getHead() {
			return head;
		}

		public void insertAtStart(int data) {
			if (head == null) {
				head = new Link(data);
				head.setLink(null);
			} else {
				Link link = new Link(data);
				link.setLink(head);
				head = link;
			}
		}

		public void insertAtEnd(int data) {
			if (head != null) {
				Link temp = head;
				while (temp != null && temp.getLink() != null) {
					temp = temp.getLink();
				}
				temp.setLink(new Link(data));
			} else {
				head = new Link(data);
			}
		}

		public void insertAfterElement(int after, int data) {
			if (head != null) {
				Link temp = head;
				while (temp != null) {
					if (temp.getData() == after) {
						Link link = new Link(data);
						link.setLink(temp.getLink());
						temp.setLink(link);
						break;
					} else {
						temp = temp.getLink();
					}
				}
			}
		}

		public void insertBeforeElement(int before, int data) {
			if (head != null) {
				Link current = head;
				Link previous = null;
				Link ins = new Link(data);
				while (current != null) {
					if (current.getData() == before) {
						ins.setLink(current);
						break;
					} else {
						previous = current;
						current = current.getLink();
						if (current != null && current.getData() == before) {
							previous.setLink(ins);
							ins.setLink(current);
							break;
						}
					}
				}
			}
		}

		@Override
		public String toString() {
			return "LinkedList [head=" + this.head + "]";
		}

	}

}

1) sort the (height, #number of greater values in front) pair by using height as a key
This can be done by using std::map
let this map be map1
2) have an empty sorted list1 with the #number of greater and the height as lexical key
for (auto &pair: map1) {
list1.insert(pair.second, pair.first);
}
3) list1 is the result.

If B = [0, 0, 0, ..., 0, 0], then the output should be a sorted list. From there, we can think of each element of B as a derangement of that sorted order. Going from right to left (highest to lowest) over B, every element of b is, by definition, the number of greater numbers that come before the element in the same position in the result list R. So we take the B[i]-th greatest element from A (that is, A[B[i]], where A is sorted) and place it in R[i], then *remove it from A*.

Here's the program:

def reorder(a, b):
    a.sort()
    r = []
    for i in b[::-1]:
        r.append(a[-i])
        del a[-i]
    return r

def main():
    a = [3, 2, 1]
    b = [0, 1, 1]
    print reorder(a, b)

if __name__ == "__main__":
    main()

a1>a2>..>an. sorted. O(nlogn)
b1,..,bn.

b[n] --> value at the end = a[b[n+1]].

Here is my simple solution.
Requires sorting then traversing the list of persons once.

1) Sort persons by multiple indexes : First index is height, second index is their B value (how many taller people are standing in front of them)

2) Traverse that sorted list in reversed order. If a person's B value is b > 0 ,
shift the person's position in the list b steps to the right (i.e. towards the taller people's direction).

Python code:

def sort_people(A, B):
    sorted_persons = sorted(zip(A, B))
    for idx, person in reversed(list(enumerate(sorted_persons))):
        if person[1] > 0:
            sorted_persons.pop(idx)
            sorted_persons.insert(idx + person[1], person)

    return zip(*sorted_persons)[0]


print sort_people([3, 2, 1], [0, 1, 1])

list pop() and insert() are O(n), so this solution is probably O(n²)

public List<Integer> solve(int[][] heights) {
        Arrays.sort(heights, (a, b) -> {
            if (a[0] == b[0]) return a[1] - b[1];
            return b[0] - a[0];
        });
        List<Integer> result = new ArrayList<>(heights.length);
        for (int[] height : heights) {
            result.add(height[1], height[0]);
        }

        return result;
    }

The question is not clear to me. It will be great if someone can help me out

a

dfdsf

dfsdf

vector<int> arrange(vector<int> &A, vector<int> &B, int n)
{
    // code here
    vector<int> res(n, -1);
    sort(A.begin(), A.end(), greater<int>());
    
    for(int i=0; i<n; i++){
        for(int j=n-1; j>=0; j--){
            if(B[j]==0 && res[j]==-1){
                res[j] = A[i];
                break;
            }
            else
                B[j]--;
        }
    }
    return res;
}

vector<int> arrange(vector<int> &A, vector<int> &B, int n)
{
    // code here
    vector<int> res(n, -1);
    sort(A.begin(), A.end(), greater<int>());
    
    for(int i=0; i<n; i++){
        for(int j=n-1; j>=0; j--){
            if(B[j]==0 && res[j]==-1){
                res[j] = A[i];
                break;
            }
            else
                B[j]--;
        }
    }
    return res;
}

This is my code and this code can be used in any amount of integers in an array

public class class2 {
public static void main(String args[]){
int arr1[]={3,5,1,6,7};
int arr2[]={0,1,1,2,3};
for(int i=0;i<arr1.length;i++){
for(int j=i+1;j<arr1.length;j++){
if(arr1[i]<arr1[j]){
int n=0;
n=arr1[i];
arr1[i]=arr1[j];
arr1[j]=n;
}
}
}

int arr3[]=new int[arr1.length];
int k=1;
while(k<=arr3.length){

arr3[arr3.length-k]=arr1[arr2[arr3.length-k]];
arr1[arr2[arr3.length-k]]=0;
for(int i=0;i<arr1.length;i++){
if(arr1[i]==0){
for(int j=i;j<arr1.length-1;j++){
arr1[j]=arr1[j+1];
}
arr1[arr1.length-k]=0;
break;
}
}
k++;
}
for(int s=0;s<arr3.length;s++){
System.out.println(arr3[s]);
}
}
}

all persons height are unique how about persons with the same height.

I get a O(N^3) algorithm. The idea is just search all possible arrangements, upon number of taller violation, backtrack.

public class PersonNode {
  int height;
  int numTaller;
  public SearchNode(int h, int n) {
    this.height = h;
    this.numTaller = n;
  }
}

public List<PersonNode> arrangePerson(List<PersonNode> unarranged) {
  List<PersonNode> result = new ArrayList();
  if(doArrange(result, unarranged)) {
    return result;
  } else {
    return null;
  }
}

private boolean doArrange(List<PersonNode> arranged, List<PersonNode> unarranged) {
  if(unarranged.isEmpty()) {
    return true;
  }

  if(!checkOrderViolation(arranged)) {
      return false;
  }

  for(PersonNode p: arranged) {
    List<PersonNode> attemptArranged = Arrays.copy(arranged);
    attempArranged.append(p);
    
    List<PersonNode> attemptUnarranged = Arrays.copy(unarranged);
    attemptUnarranged.remove(p);

    if(doArrange(attempArranged, attemptUnarranged)) {
      arranged = attempArranged;
      unarranged = attemptUnarranged;
      return true;
    }
  }

  return false;
}

// O(n^2)
private boolean checkOrderViolation(List<PersonNode> persons) {
  for(int i = 0; i < persons.size(); i++) {
    PersonNode p = persons.get(i);
    int height = p.height;
    int numActuallTaller = 0;
    for(int j = 0; j < i; j ++) {
      if(persons.get(j).height > height) numActuallTaller++;
    }
    if (numActuallTaller != p.numTaller) return false;
  }
  return true;
}

int main (int arc, char * argv[])
{
int arrHeight[] = {3,2,1};
int arrKeyGiven[] = {0, 1, 1};

int i, j, temp = 0, length = 0;

length = 3;//4;


/** LOGIC FOR RESETING THE POSITION ACCORING TO THE KEY GIVEN
if Current position < keyPostion then
: do one swap with teh previous one :)
else
: do one swap with the next one :)
**/

for (i = 0; i < length; i++)
{
if ( arrKeyGiven[i] < i)
{
temp = arrHeight[i];
arrHeight[i] = arrHeight[i-1];
arrHeight[i-1] = temp;
}
}
printf("REPOSITIONED ARRAY IS \n");
for (i = 0; i < length; i ++)
printf("%d\t", arrHeight[i]);

return 0;

}

THIS IS THE MODIFIED LOGIC:----- WORKS WELLL :) please have one try by assigning some logically correct values to arrHeight, and arrKeyGiven and see the result...if any issues plz revert to jitu059@gmail.com
U need to edit, arrHeight/arrKeyGiven and length to test more problems
#################################
int main (int arc, char * argv[])
{
int arrHeight[] = {3,1,2};
int arrKeyGiven[] = {0, 2, 1};

int i, j, temp = 0, length = 0;

length = 3;//4;


/** LOGIC FOR RESETING THE POSITION ACCORING TO THE KEY GIVEN
if keyPosition < Current Position then
: do one swap with teh previous one :)
else if keyPosition > Current Position then
: do one swap with the next one :)
else : DO NOTHING......current position is desired one :)
**/

for (i = 0; i < length; i++)
{
if ( arrKeyGiven[i] < i)
{ printf("Swaping in process\n");
temp = arrHeight[i];
arrHeight[i] = arrHeight[i-1];
arrHeight[i-1] = temp;
}
else if( arrKeyGiven[i] > i)
{
temp = arrHeight[i];
arrHeight[i] = arrHeight[i+1];
arrHeight[i+1] = temp;
}
}
printf("REPOSITIONED ARRAY IS \n");
for (i = 0; i < length; i ++)
printf("%d\t", arrHeight[i]);

return 0;

}

C++

int* ArrangePeople(int height[], int front[], int n)
{
	for(int i = 0; i < n; i++)
	{
		int temp = height[i];
		for(int j = i; j > front[i]; j--)
		{
			height[j] = height[j-1];
		}
		height[front[i]] = temp;
	}
	for(int i = 0; i < n; i++)
		cout<<height[i]<<" ";
	return height;
}

int heights[5] ={5,4,3,2,1};
int rank[5] ={0, 1, 0, 1, 2};
ArrangePeople(heights, rank, 5);
output: 3 2 1 5 4