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