各会議を区間と捉えます。

区間を頂点とし、重なる \(2\) 個の区間の間に辺を張ったグラフ（= Interval graph）を考えます。 担当者の割り当ては、このグラフの \(2\) 彩色に言い換えられます。

存在判定

\(2\) 彩色可能かの判定を行い、不可能であれば \(0\) を出力する必要があります。

これは、区間が \(3\) つ以上重なっている時間帯があるかを判定すれば十分です。

数え上げ

\(2\) 彩色の数え上げです。

\(1\) つの連結成分の \(2\) 彩色はちょうど \(2\) 通りです。 よって、連結成分数を \(C\) とすると、答えは \(2^C\) です。

連結成分数は、左から区間を見た時に、重なっている区間数が \(0\) 個から \(1\) 個以上になる回数です。

実装

あらかじめ、各時間帯に区間がいくつ重なっているかを求めておきます。 これは、累積和を利用することで \(O(N)\) で求めることができます。（imos 法）

これにより、存在判定も数え上げも \(O(N)\) で求めることができます。

おまけ

\(2\) 人ではなく \(K\) 人としてもこの問題は \(O(N)\) で解くことができます。