時間帯重複チェックの計算量と前提条件

お題：時間帯重複チェック（応用編） - No Programming, No Life に関して、解法は２種類に大別できるようです。

解法の分類

離散時刻方式

「時間帯（何時何分から何時何分まで）に含まれる時刻（何時何分）の最小単位が1分」であることに注目した方式です。とりあえず、このように名づけてみました。

典型的な実装は下記のようになります。

  1. 与えられた時間帯のひとつひとつを1分ごとの時刻に分解する → O(N)
  2. 重複する時刻を抽出する → O(N)
  3. 連続する抽出時刻をまとめて時間帯に再構成する → O(N)

この方式のメリットは、計算量のオーダをO(N)に抑えられる点です。

[代表例]

時刻全順序方式

一方、純粋に時刻の大小関係（前後関係）のみに基づいてアルゴリズムを構築することもできます。

典型的な実装では下記のようになります。

  1. 与えられた時間帯を開始時刻で整列する → O(NlogN)
  2. 整列済の時間帯が重なる部分をシーケンシャルに抜き出す → O(N)

この方式のメリットは、時刻指定を細かくしても問題をきたさない点が挙げられます。例えば、時刻の最小単位を「何分」ではなく「何秒」まで指定することになった状況を考えてみましょう。前述の離散時刻方式では、60倍の離散時刻が生じますが、この方式ではなんら不都合は生じません。

その一方で、デメリットもあります。どんなに最良の実装を頑張っても、計算量はO(NlogN)になってしまう点です。

[代表例]

キーポイント

分類のキーポイントが、2011-03-31 - コードの恵みにて簡潔明快に述べられています。

フラグ方式は bucket sort のように限定条件に気づいている

この「限定条件」をもう少しまわりくどく説明したのが、上記の分類に相当すると思います。
私のつたない日本語では、これ以上、明快な説明をできませんので、答案：時間帯重複チェック(応用編) - 一番良いアルゴリズムを頼む · GitHubにコードで示します。

ポイントは、

  1. 通常のソートを用いれば計算量がO(NlogN)になる；bucket ソートを用いればO(N)になる
  2. 通常のソートを用いる場合は、時刻の離散性を用いていない（例えば、時刻がInt でなく Double でも動く）