Kero wrote:
> >> May I assume then, that there are only timeslots of full hours?
> >
> > I assumed that from reading of quiz.  It's probably an over
> > simplistic assumption, but I think it will do for this challenge.
> > P.S.  Hans, feel free to jump in here and save me at any time...  :D
>
> Isn't the problem in general NP hard? Meaning you have to make some
> simplifications to keep the input small, or apply some other
> restrictions to get the problem to P.

Well I'll take your word for it on the NP thing because I don't have
the brain cycles to spare at the moment. ;-) It is definitely not
trivial.

> Of course, it is also possible to generate input for which there is no
> solution. Then what? When to loosen bonus targets like regular times for
> a person and when to give up?

See below...

> I think everybody has to figure this out for him/herself.

I'm not clear what you mean by that. I think you might mean every
McDonalds manager has to figure this out him/herself. That's the
interesting thing here - lots and lots of people do this every single
day.

> Moreover, do not restrict the application to people and time, it can be
> anything and time (or even boxes and space if you can restrict the space
> to 1D meaningfully :)

Yes, it is essentially the knapsack problem with time dependence added.

> I can't suppress the feeling that the quiz is meant to pick a "nice"
> solution when there's plenty of solutions available. For which you need
> (a lot of) example input...

Yes and no. I alluded to the fact that people have minimal difficulty
doing this (although as you can imagine it is a common sore spot
between employees and employers) so that seems to suggest that one
approach would be an AI approach. We are looking for one of many
solutions. Ideally we find the optimal solution, but we're happy to
find a "good" solution. Your response has piqued my interest (I
unfortunately don't often find time to do these quizzes, even when I'm
the one who comes up with the idea. ;-). Here's how I plan to do it:

We want to search the solution space for good answers. First we need to
represent things, and my first idea here is a sequence of (day, hour,
person) tuples, where day is a weekday name, hour is something like
1300, and person is the name of a person. The sequence for a whole week
(with a 12-hour business day) is 72 tuples long, not too bad.

Next we need to have a way to know if an answer is good, and how good
the answer is. This is called a utility function in AI. Normally you
award points for things you like and demerit points for things you
don't like. Finding a good utility function is the artistic and most
important part of a search like this.

Now we can represent whole and partial solutions and measure their
utility. Now all we have to do is search. I'm guessing an A* search
will do the trick nicely (it usually does). If not A* then one of its
variants, probably. Or maybe greedy will do the job sufficiently well
for most purposes. All that remains is to choose a good heuristic, this
is the other artistic and important part of the algorithm.

Assuming we can find a reasonable heuristic and utility function, the
computer should be able to find us good solutions. If we can find
sufficiently good heuristic and utility functions, we can say the
solution is optimal - whatever that means. (In other words, if we knew
what optimal was in the real world for this problem, and we could
represent it with utility/heuristic functions, we could find an optimal
solution).

I hope to find the time to code this up, for the proof is in the
pudding. The only real question in my (perhaps over-confident) mind is,
will it fit in memory and time constraints? When you have a problem
where valid solutions abound and you're looking for a "good" solution,
the answer is usually that you can find better and better solutions
given enough time and memory, and hopefully you can find something good
enough given realistic time and memory.

Hans