language-agnostic - 連続エントリ数の追跡

Question

ユーザーが参加できるコンテストがたくさんあります。常時約 10 のアクティブなコンテストがあります。1 時間ごとに新しいコンテストが発生し、最も古いコンテストが終了します。ユーザーが連続していくつのコンテストに参加したかを追跡したいと考えています。唯一の問題は、ユーザーが順不同でコンテストに参加できることですが、各コンテストが終了する前に参加している限り、クレジットを取得する必要があります。

私はいくつかの可能な解決策に取り組みましたが、それぞれに検出が非常に困難なひどいエッジケースがあるようです. 私は何かを見逃していますか、それともこれはかなり難しい問題ですか?

Answer 1

特定のシーケンス(O(n^2))の最長増加サブシーケンスを使用できます。O(n) および O(n log n) メソッドもあります。

この質問も見てください:シーケンスを形成するその最大のサブセットを見つけてください。

Answer 2

したがって、基本的には、各コンテストが終了するたびにユーザー レコードを更新することで、ユーザーが最後に参加したコンテストを追跡しています。次に、このコンテストが以前に終了したコンテストと一致するかどうかを確認します。一致する場合は、contestStreak カウンターをインクリメントします。そうでない場合は、カウンターを 1 にリセットします。