The Problem

A manager has to recruit a new employee and he can serially interview a finit group of candidates. There is a total order defined on the candidates' fitness to the opening, and there are no two employees with the same skill level. The manager is able to sort the candidates' fitness level after a short interview. After each interview the manager has two alternatives:

• recruit the last interviewed candidate
• continue to the next interview (and give up the chance of recruiting the previous candidate)