Why this problem has such a simple solution? How would you avoid looking for more complex solutions first? There's a problem whose solution startles me because at first sigh, I wouldn't imagine that it could be solved so easily. The problem is:
There are n tasks, each task t_i has a weight w_i and a length l_i. Find an order of tasks t_1, ... t_j, ..., t_n that minimizes the total cost of completion, where the cost of completion of each task is c_j * w_j, where c_j is the time it has passed since you started working on the first task until you finished the jth task.
If we analyze the problem a bit, we can see that the task that we choose to complete first will impact the cost of all the remaining tasks. For example, say you only have 2 tasks:
task_1 with w_1 = 1 and l_1 = 5 and
task_2 with w_2 = 4 and l_2 = 2
If we started first task_1, its cost would be 5 * 1 = 5 while if we started first task_2, its cost would be 2 * 4 = 8. But, the cost of completing task_2 after task_1 is (5+2) * 4 = 28. This shows clearly that the order of completion of one task affects the cost of completion of all the remaining tasks.
Considering how each task we decide to complete next impacts the cost of all the remaining tasks, it startles me that the best order is simply the order we get by sorting the tasks by their ratio w_i/l_i.
Which part of the problem hints that the solution doesn't require to check all the possible orders?
The problem is taken from Algorithms Illuminated 3 by Tim Roughgarden.
In this case: It is obvious that you start with some task immediately, start a second task as soon as the first task is finished, then start a third task immediately after this etc.
It is obviously that you can swap the order of two consecutive tasks without affecting any other task. In an optimal solution, swapping the order of two consecutive tasks cannot improve the solution.
Now you look for a criterion when swapping two tasks would improve the solution. For an optimal solution, that criterion must fail for any two consecutive tasks. And lucky enough there is a simple criterion.
So any problem where tasks must be performed consecutively, and where swapping two tasks doesn't affect all the other tasks, you can solve if you can determine which order of the two tasks is better.
This doesn't work for the travelling salesman problem for example, because swapping two cities affects other cities as well.