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