問題は次のように読み替えられます。

「\(N\) 人のユーザがいて、\(i\) 番目のユーザは時刻 \(L_i\) にログインし、時刻 \(R_i\) にログアウトしました。\(1\) 人以上がログインしていた時刻の区間を求めてください」

以下では読み替えた後の問題について考えます。

この問題に答えるには、ログイン人数が \(0\) から \(1\) 以上になった時刻と \(1\) 以上から \(0\) になった時刻が求まれば十分です。

\(L_i\) 及び \(R_i\) をまとめてソートし、ログイン・ログアウトの処理によるログイン人数の変化を実際に時刻順にシミュレーションすることでこの問題を解くことができます。同じ時刻にログインとログアウトが同時に起こる際には、ログインを先に処理する必要があることに注意してください。計算量は \(O(N\log N)\) です。

実装例(C++)

この問題はimos法を用いて \(O(N+\max R_i)\) で解くこともできます。

実装例(C)