-4
$\begingroup$

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.)

$\endgroup$
8
  • 2
    $\begingroup$ Welcome to Puzzling SE! Please could you add the text of the puzzle? Link-only posts aren't encouraged here. $\endgroup$ May 2 '15 at 13:37
  • $\begingroup$ @randal'thor can i copy content from other website? not sure $\endgroup$ May 2 '15 at 13:39
  • $\begingroup$ I think it's fine to copy content as long as you also include the link (but this does not constitute legal advice) :-) $\endgroup$ May 2 '15 at 13:45
  • 2
    $\begingroup$ Isn't that a programming challenge rather than a logic puzzle though? $\endgroup$
    – Alconja
    May 2 '15 at 13:51
  • 1
    $\begingroup$ I agree that, as it stands, this would be more appropriate on codegolf.SE... but I think it's worth recasting this into a regular puzzle format - namely, remove all of the extra context that is relevant to coding the solution, and express the problem more directly. If @VishakhaSehgal is OK with it, I'm happy to do it. $\endgroup$
    – Glen O
    May 2 '15 at 13:53
1
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.