A - Meeting Division Editorial by evima
Regard each meeting as an interval.
Consider the graph (interval graph) whose vertices are the intervals, with an edge drawn between two intervals that overlap. Assigning the person in charge can be restated as a \(2\)-coloring of this graph.
Determining Existence
We need to determine whether a \(2\)-coloring is possible, and output \(0\) if it is not.
It suffices to determine whether there is a time period where three or more intervals overlap.
Proof
First, if there is a time period where three or more intervals overlap, clearly those three meetings cannot be handled by two people.
Conversely, suppose there is no time period where three or more intervals overlap. Considering the intervals in increasing order of their left endpoint, at the moment a new interval starts, there is at most one interval that has already started but not yet ended. We may use a color different from that interval to paint the new interval, so a $2$-coloring is always possible.
Counting
We count \(2\)-colorings.
There are exactly two ways to \(2\)-color a single connected component. Thus, if the number of connected components is \(C\), the answer is \(2^C\).
The number of connected components equals the number of times, when looking at the intervals from the left, the number of overlapping intervals changes from \(0\) to \(1\) or more.
Implementation
In advance, find how many intervals overlap during each time period. This can be found in \(O(N)\) by using cumulative sums (the “imos method”).
With this, both the existence determination and the counting can be done in \(O(N)\).
Bonus
Even with \(K\) people instead of \(2\), this problem can be solved in \(O(N)\).
posted:
last update: