DSA Factory
Free Greedy lessonsGreedy · Stage 4 · Mastery · Step 2

Rebuild the line

Rebuild a queue from people described by their height and how many taller-or-equal people stand in front of them, by placing the tallest first and inserting each person at their count. About 22 minutes.

Taller people do not see shorter ones

Each person is described by [height, ahead]: their height, and how many people in front of them are at least as tall. The line is scrambled and you must rebuild it.

Notice that shorter people never affect a taller person's count. So the tallest people can be placed first, and later, shorter people can be slotted in without disturbing anyone already placed.

Count ahead: ignores everyone shorter.
Tallest first: so later people never change earlier counts.

Insert at the count

Sort by height from tallest to shortest. For equal heights, put the smaller count first.

Now take people in that order and insert each at the position equal to their count. At that moment, everyone already in the line is at least as tall, so exactly that many are ahead of them. Later, shorter people go in without changing anyone's count, so the final line is correct.

Insert at index: equal to the count ahead.
Ties by smaller count first, so each lands in the right order.
In code
line = []
line.insert(2, "Asha")   # 2 before her
People sorted tallest first: heights 6, 6, 5, 5, 4 with counts 0, 1, 0, 1, 1.
6
0
6
1
5
2
5
3
4
4
i

Insert 6 with count 0 at the front: line is 6.

Move 1 of 5
Quick check

Why insert the tallest people first?

  1. AShorter people never change a taller person's count
  2. BIt makes the sort faster
  3. CAny order works equally well
Show the answer

Shorter people never change a taller person's count. A person's count only includes people at least as tall.

Your problem

Rebuild the line

You are given people, where people[i] = [height, ahead]: the height of person i, and the number of people in front of them in the line who are at least as tall. Rebuild the line and return it as a list of [height, ahead] pairs in order from front to back. A valid line exists and is unique.

Example
people = [[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]] → [[5, 0], [7, 0], [5, 2], [6, 1], [4, 4], [7, 1]]

1 ≤ people.length ≤ 2,000 · 1 ≤ height ≤ 100,000 · a valid line exists

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.
Sign up free to solve