There are 16 seminars with the following durations in minutes:
60,45,30,45,45,30,30,45,60,60,45,30,30,60,30,30
They need to be divided into groups. Each group must have 2 subgroups. The first group must be exactly 3 hours, and the second between 4 and 5 hours inclusive.
I know there are multiple solutions, but what method can be used to find a solution with any set of seminars?
(Adapted from http://top-interview-puzzles.blogspot.in/2015/05/thoughworks-screening-puzzle.html.)
There are different approaches to this kind of problem.
1) Brute Forcing
You simply try all the combinations and see what fits.
This is easy to implement, but it requires many many operations, ergo such an algorithm is impossible to do perform by hand and very slow even for a computer.
In particular, there are $N!$ permutations to verify, anyway you can slightly optimize it not repeating identical sequences (I mean, there are 4 "60" in your set, if you swap them nothing changes!).
2) Greedy
The main idea is "long seminars are cumbersome, try to position them until you have room!"
So, in the blocks of 3 hours we start placing the "60", then the "45", finally the "30". In this particular case it works, but doesn't if you want to generalize the problem.
Computationally, this algorithm is extremely efficient ($O(N)=Nlog(N)$ because you have to sort the data), but it's not granted to work.
3) Recursion
Basically a recursive algorithm explores all the possible sequences starting from a seminar, adding another, then another, and so on...
Differently from brute forcing, when it finds a wrong sequence, it easily excludes similar wrong sequences from being tested, strongly reducing the number of required operations.
This algorithm is fast, average difficulty to implement, but incredibly memory (RAM) leeching. This is granted to work if there exists at least a valid sequence.
There may be other interesting algorithm to discuss, but this is not the right place I guess.
