There is a line of scattered people and we need to restore the order.

We know:

• How tall each of them are
• The number of people who were in front of them who are taller.

This information is contained in a set

Person {
    int height;
    int tallerAheadCount;
}

I’ve tried sorting it multiple ways, but no luck.

What i managed to figure out is that the shortest person’s tallerAheadCount should match the original index, but this doesnt work in a for loop with sorted heights.

Sorting by tallerAheadCount, and then by height gives us a relatively close answer, but the higher the tallerAheadCount the more incorrect it seems to get. I can’t figure out a rule to merge the shorter people to lower tallerAheadCount sorted lines. How would you go about this?

CodePudding user response：

Little to go on, but I suppose something like this could be what you're after.

This is probably not the most efficient implementation, and not sure it covers all cases (e.g. duplicates), but it's a start:

import random

# dummy data [(height, taller_ahead_count), ...]
original_line = [
    (10, 0), (12, 0), (3, 2), (8, 2), (9, 2), (5, 4), (1, 6), (4, 5), (2, 7)]

# "scatter" the people
scattered_line = original_line.copy()
random.shuffle(scattered_line)

# restore the original line order based on the taller_ahead_count
descending_height = sorted(scattered_line, key=lambda x: x[0], reverse=True)
restored_line = []
for height, taller_ahead_count in descending_height:
    taller_count = 0
    j = 0
    while taller_count < taller_ahead_count and j < len(restored_line):
        if restored_line[j] > height:
            taller_count  = 1
        j  = 1
    restored_line.insert(j, height)

# verify result
assert [height for height, __ in original_line] == restored_line

Wait a minute... this is not a homework assignment, is it?