Editorial for Facebook Hacker Cup '15 Round 3 P2 - Lunch Scheduling
Submitting an official solution before solving the problem yourself is a bannable offence.
Right off the bat, it's simplest to handle a special case separately: if , then the answer is simply . Going forward, let's assume that this is not the case.
For every meeting , there are at most two potentially optimal "next" meetings to attend – one for each person. Of all of the meetings that James can attend that start after starts and start earlier than milliseconds after ends, let be the one that ends the latest, if any. We can define similarly for Wilson. If somebody attends meeting , the only two meetings we need to consider attending next are and . We can naively precompute and for every meeting in time, where is the total number of meetings ().
Let and be the two meetings that are optimal to start with for James and Wilson respectively, if any. That is, the meetings for each of them that end as late as possible, but start earlier than time . If neither nor are defined (no meetings start earlier than time ), then it's impossible to avoid having lunch.
Otherwise the answer we're looking for is then the minimum of these (unless both are , in which case lunch also cannot be avoided):
- , if is defined
- , if is defined
We can define recursively as follows:
- if is undefined (that is, if we refer to or but such a meeting doesn't exist)
- if ends after (no more meetings after are needed to avoid lunch), and is one of Wilson's meetings
- if ends after , and is one of James's meetings
- if ends after , and neither of the above 2 cases holds
- (we've run out of James's meetings, so Wilson must attend a meeting)
- if (either person can take the next meeting)
There are only states to compute, and each one can be computed in time. So the total time complexity of this solution is .
Comments