Reconstruct a queue by height

Why this matters

A greedy algorithm makes the choice that looks best at each step and never goes back. The earlier lessons in this module used greedy choices on intervals, jumps and coins. This lesson uses a greedy choice on a line of people. The key question is which person to place next, and the answer is what makes the problem easy.

Many real problems look like this. You have a set of clues about where each item belongs, and you must build the full order that fits every clue. Placing items one at a time in the wrong order can break a clue that was already true. This lesson shows how to pick an order for placing items so that a clue, once satisfied, stays satisfied.

The lesson uses one puzzle. You are given a list of people. Each person has a height and a number. The number is how many people in front of them in the line are at least as tall as they are. Your task is to put the people in a line that fits every clue.

The puzzle with a small example

Take three people:

• Person A has height 5 and number 0.
• Person B has height 6 and number 0.
• Person C has height 5 and number 1.

Person A has number 0, so no one at least as tall as A stands in front of A. Person B has number 0, so no one at least as tall as B stands in front of B. Person C has number 1, so exactly one person at least as tall as C (height 5 or more) stands in front of C.

Try the line B, A, C. Is A's clue true? A is first, so nobody is in front. Good. Is B's clue true? B is first, so nobody is in front. Good. Is C's clue true? In front of C are B (height 6) and A (height 5). Both are at least as tall as C, so the count is 2, but C needs 1. The line fails.

Try the line A, C, B. A is first, so A's clue is true. C has A in front, and A is 5, which is at least 5. The count is 1. C's clue is true. B has A and C in front. Neither is taller than B (6), so the count is 0. B's clue is true. This line is valid.

The puzzle always has an answer in the cases used in this lesson. The task is to find an order that fits all the clues.

The idea: place the tallest people first

The idea is to place people in a set order and insert each one into a line that is already being built. The line starts empty. Each new person goes into a position in the line. The position is the number from their clue.

Here is why this works. Suppose you place the tallest people first. When you place a person, everyone already in the line is at least as tall as this person. So the number of people in front of them who are at least as tall is the same as the number of people in front of them in the line at all. The clue tells you the exact position, and you can put the person there.

After that, you place shorter people. A shorter person does not count as "at least as tall" for anyone taller than them. So when you insert a shorter person into the line, the count for every taller person stays the same. The taller person's clue was already satisfied, and it stays satisfied.

This is the step that makes greedy work. Once a person is placed, nothing placed later can change whether their clue is true. The rule is simple: place the tallest people first, and place each one at the position given by their number.

Ties: people of the same height

Two people can have the same height. Then the order of placing them matters.

Take two people, both of height 5. One has number 0 and the other has number 2. Suppose you place the person with number 2 first. The line is empty, and you must put that person at position 2. There are no people in the line, so position 2 does not exist. The placement fails.

Now place the person with number 0 first. The line is empty, and position 0 is the start of the line. The person goes in. Next place the person with number 2. The line has one person, and position 2 is past the end of a line with one person in it. That also fails, unless someone else of height 5 or more is already in the line before this person. The rule for ties is to place the person with the smaller number first. The line then grows by one at each step, so a position within range always exists.

So the rule for the order is:

1. Place people from tallest to shortest.
2. When two people have the same height, place the one with the smaller number first.

Building the solution in C++

The C++ code below follows the rule. It uses a struct, which is a way to group a few named values into one type. The struct has two fields, height and ahead. The field ahead is the number from the clue.

The standard library function std::ranges::sort puts the people in the chosen order. The std::vector function insert places a new person at a given position. Its first argument is an iterator, which is an object that points at a position in a container. The expression queue.begin() + p.ahead points at the position p.ahead steps from the start of the line.

The file is named reconstruct.cpp.

#include <algorithm>
#include <iostream>
#include <vector>
 
struct Person {
    int height;
    int ahead;  // how many people in front of this person are at least this tall
};
 
std::vector<Person> reconstruct(std::vector<Person> people) {
    std::ranges::sort(people, [](const Person& a, const Person& b) {
        if (a.height != b.height) return a.height > b.height;  // tallest first
        return a.ahead < b.ahead;                              // on a tie, fewer ahead first
    });
 
    std::vector<Person> queue;
    queue.reserve(people.size());
    for (const Person& p : people) {
        queue.insert(queue.begin() + p.ahead, p);
    }
    return queue;
}
 
bool is_valid(const std::vector<Person>& queue) {
    for (std::size_t i = 0; i < queue.size(); ++i) {
        int count = 0;
        for (std::size_t j = 0; j < i; ++j) {
            if (queue[j].height >= queue[i].height) ++count;
        }
        if (count != queue[i].ahead) return false;
    }
    return true;
}
 
void print(const std::vector<Person>& queue) {
    for (const Person& p : queue) {
        std::cout << '[' << p.height << ',' << p.ahead << "] ";
    }
    std::cout << '\n';
}
 
int main() {
    std::vector<Person> input = {{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}};
    auto answer = reconstruct(input);
    print(answer);
    std::cout << "valid: " << std::boolalpha << is_valid(answer) << '\n';
}

Compile and run it with the commands below. The -Wall flag turns on the common warnings, so the compiler reports suspicious code.

g++ -std=c++20 -Wall -o reconstruct reconstruct.cpp
timeout 10 ./reconstruct; echo "exit $?"

The program prints:

[5,0] [7,0] [5,2] [6,1] [4,4] [7,1] 
valid: true
exit 0

The timeout 10 part stops the program after 10 seconds if it hangs. The echo "exit $?" part prints the exit code. An exit code of 0 means the program finished without an error.

The function is_valid checks the answer against the rule in the puzzle. For each person, it counts the people in front who are at least as tall, and it compares that count with the number in the clue. The check takes time that grows with the square of the number of people, which is fine for a line of this size.

Walking through the example step by step

The table below shows each person in the order they are placed, and the line after each insertion. Each row shows one step of the greedy method.

Look at step 2. The person [7,1] has one person in front who is at least as tall. The line at that moment holds only [7,0], and [7,0] is 7 tall, so the position 1 is correct.

Look at step 3. The person [6,1] has a number of 1. The line holds two people, both 7 tall, so both are taller than 6. Position 1 is between them. Inserting [6,1] there gives one person in front who is at least 6 tall, which matches the clue.

Look at step 6. The person [4,4] is the shortest so far and has four people in front. The line holds five people, and all of them are at least 4 tall. Position 4 is after the fourth person. The clue is satisfied.

Notice that [7,1] was placed at step 2, and step 6 put a shorter person in front of it. That is fine. The shorter person does not count for [7,1], because [7,1] only counts people at least 7 tall.

A second example with equal heights

Take three people, all of height 5, with numbers 0, 1 and 2. Sorted by the tie rule, they come in the order number 0, number 1, number 2. The line grows like this:

• Insert the number 0 person at position 0. The line is one person long.
• Insert the number 1 person at position 1, which is the end of the line. The line is two people long.
• Insert the number 2 person at position 2, which is the end of the line. The line is three people long.

The answer is the people in the same order they were inserted. When every height is the same, the number in each clue is simply the position in the line.

The program in the previous section prints the same result when it runs on this input. To try it, call reconstruct({{5, 0}, {5, 1}, {5, 2}}) from a second file that includes the same code. The output is:

[5,0] [5,1] [5,2] 

A third example with mixed heights

Take three people with heights 2, 1 and 3, and numbers 0, 1 and 0. The tallest person is height 3 with number 0. Sorted from tallest to shortest, the order is [3,0], [2,0], [1,1].

• Insert [3,0] at position 0. The line is [3,0].
• Insert [2,0] at position 0. The line is [2,0] [3,0]. The person [2,0] has no one in front who is at least 2 tall.
• Insert [1,1] at position 1. The line is [2,0] [1,1] [3,0]. The person [1,1] has one person in front who is at least 1 tall, which is [2,0]. Position 1 is correct.

The final line is [2,0] [1,1] [3,0]. Run the program on this input and the output is the same:

[2,0] [1,1] [3,0] 

Common mistakes

Sorting only by the number

A beginner sometimes sorts people by the number in the clue and ignores the height. The number looks like the right key, because it is the position. It is not enough. The number only counts people who are at least as tall, so the heights must decide the order in which people are placed.

This version sorts by the number only:

#include <algorithm>
#include <iostream>
#include <vector>
 
struct Person { int height; int ahead; };
 
int main() {
    std::vector<Person> people = {{7, 0}, {4, 4}, {7, 1}, {5, 0}, {6, 1}, {5, 2}};
    // BUG: sorts by ahead only, so the heights are ignored
    std::ranges::sort(people, {}, &Person::ahead);
    std::vector<Person> queue;
    for (const Person& p : people) queue.insert(queue.begin() + p.ahead, p);
    for (const Person& p : queue) std::cout << '[' << p.height << ',' << p.ahead << "] ";
    std::cout << '\n';
}

The program prints a line that breaks the rule:

[5,0] [6,1] [5,2] [7,1] [4,4] [7,0] 

Check the person [6,1]. The clue says one person in front is at least 6 tall. The only person in front is [5,0], who is 5 tall. The count is 0, so the clue fails. The function is_valid from the program above returns false for this line.

Placing ties in the wrong order

The tie rule matters. If people of the same height are placed with the larger number first, the insert can go past the end of the line. The code below is the same as the correct program, except the tie rule is reversed.

std::ranges::sort(people, [](const Person& a, const Person& b) {
    if (a.height != b.height) return a.height > b.height;
    return a.ahead > b.ahead;  // BUG: larger ahead first on a tie
});

Put this bug into the program from the previous section and run it on the same input. The first person placed is [7,1], into an empty line, so the insert at position 1 goes past the end. A normal build of the program stops with a segmentation fault, and the exit code is 139. A segmentation fault means the program touched memory that it does not own.

Build the same program with -D_GLIBCXX_DEBUG. This flag turns on extra checks in the standard library. The check gives a message that names the mistake:

Error: attempt to advance a past-the-end iterator 1 steps, which falls
outside its valid range.

The exit code for this run is 134. The message says that the code moved an iterator past the end of the vector. The fix is the tie rule from earlier: on a tie, place the smaller number first.

Inserting past the end of the line

A clue can be impossible. A person with number 2 cannot be placed in a line that has fewer than two people in front of them. The input {{2, 2}, {1, 0}} has this problem. The person [2,2] needs two people in front, but there are no other people. The insert at position 2 goes past the end of an empty line.

The standard library does not check this for you. The code is undefined behaviour, which means the result is not defined by the language. The program may crash, or it may print a wrong answer. To catch the problem, check the position before inserting:

if (static_cast<std::size_t>(p.ahead) > queue.size()) {
    throw std::invalid_argument("clue asks for more people than are placed so far");
}
queue.insert(queue.begin() + p.ahead, p);

The check uses std::size_t for the comparison, so it has the same type as queue.size(). throw raises an error that stops the program with a message. This check catches an impossible clue at the point where it happens, not later.

Forgetting to check the answer

The method is correct, but a small typo in the sort or the insert can produce a wrong line. The is_valid function is a cheap way to catch that during testing. Run it on the output of every test. If it returns false, the answer does not fit the clues, even if the program did not crash.

Practice

Exercise 1

Place the people [3,0], [3,1] and [1,0] in a line. Show the line after each insert.

Show the answer

Sorted from tallest to shortest, the order is [3,0], [3,1], [1,0]. Insert [3,0] at position 0 to get [3,0]. Insert [3,1] at position 1 to get [3,0] [3,1]. Insert [1,0] at position 0 to get [1,0] [3,0] [3,1]. The program prints [1,0] [3,0] [3,1] for this input, and [3,1] has one person in front who is at least 3 tall, which is [3,0].

Exercise 2

Why must the tallest people be placed first, and not the shortest?

Show the answer

When a tall person is placed, only taller or equal people are already in the line. Their count of people in front is exact, so the insert position is exact. A shorter person placed later does not count for any taller person, so the taller person's clue cannot change. If the shortest people were placed first, a later taller person would sit among them, and the count for the shorter people would change when the taller people arrived. The clue for a shorter person would no longer be fixed when it was placed.

Exercise 3

Two people have height 4. One has number 1 and the other has number 0. In which order do they go into the line, and why?

Show the answer

The person with number 0 goes first. The line must have at least one person in it when the person with number 1 is inserted at position 1. The tie rule places the smaller number first, so the number 0 person is placed first and the number 1 person follows. If the order were reversed, position 1 would not exist in an empty line.

Exercise 4

Change the program so that it prints impossible instead of crashing when a clue asks for more people than are placed so far. Test it with {{2, 2}, {1, 0}}.

Show the answer

Add the check from the mistakes section before the insert, and return an empty vector or print the word when the check fails. For example, reconstruct can return a std::optional<std::vector<Person>> and return std::nullopt on the failing check. The input {{2, 2}, {1, 0}} fails the check at the first insert, because the line is empty and the clue asks for two people in front.

Exercise 5

Is the answer to the puzzle always unique? Explain with one example.

Show the answer

Yes. When a valid line exists, the list of height and number pairs in it is unique. Take {{5, 0}, {5, 1}}. The number 0 person must be first, because nobody can be in front of them, and the number 1 person must have one person in front. The only line is [5,0] [5,1]. Changing the order breaks one of the clues. Greedy placement finds this unique line because each person is placed at a position that is forced by the clue.

Summary

• A clue says how many people in front are at least as tall as this person, and the greedy method uses that number as an insert position.
• Place people from tallest to shortest, because a shorter person placed later does not change a taller person's count.
• On a tie in height, place the person with the smaller number first, so the insert position always exists.
• std::vector::insert with queue.begin() + p.ahead places each person at the clue's position.
• Check the answer with a separate function that counts the clues again, and catch impossible clues before the insert.