The Hungarian algorithm. It solves the assignment problem (the optimal way to assign workers to tasks given their completion time of each task). The assignment problem looks hopelessly O(n!), but by some magic, the algorithm can solve it in polynomial time.