8 Dec 2015
A problem that must be solved with a greedy algorithm is usually a very difficult one.
For this problem, it turns out that we can devise a greedy algorithm to solve it. However, a greedy algorithm only solves a specific situation, where we know the number of criminals in the house at the beginning.
However, we can use a binary search to find the minimum number of criminals in the house at the beginning.
There are many axioms to prove:
Axiom: If the starting number of criminals is X yields a valid result, then Y > X always yields a valid result.
Because adding more people can't possibly make the situation invalid. It's just more people in the house at the end.
Axiom: If we have E0, then we will assign the criminal X who will exit the earliest (with no EX in between).
We can prove that by proving it is always worse to exit later. For example:
E0 … L1 … L2 — we can choose either L1 or L2. it doesn't matter E0 … E0 … L1 … L2 — we can choose either L1 or L2. It doesn't matter. Because we can always swap the 2 E0. E0 … L1 … E0 … L2 — we have to choose L1
The best thing to do is choosing L1.
Axiom: If we have E0, and every leave has an enter, then we assign a new person to E0.
We can prove that it doesn't matter…
E0 … E2 … L2 — we have to assign a new person E0 … L0 … E2 … L2 — we can either assign a new person or assign 2.
We do the same thing for L0. It might be a bit tricky.
And that's it.