language-agnostic - 跟踪一行中的条目数

Question

我有一堆用户可以参加的比赛。任何时候都有大约 10 个活跃的比赛。每小时都会举行一场新的比赛，而最古老的比赛结束。我想跟踪用户连续参加了多少场比赛。唯一的问题是用户可以无序参加比赛，但只要他们在每场比赛结束前参加比赛，他们仍然应该获得积分。

我已经研究了一些可能的解决方案，但每一个似乎都有非常难以检测的可怕边缘情况。我错过了什么还是这只是一个非常困难的问题？

Answer 1

所以基本上我通过在每次比赛结束时更新用户记录来跟踪用户参加的最后一场比赛。然后我检查这个比赛是否与之前结束的比赛相匹配。如果是这样，我会增加他们的 CompetitionStreak 计数器。如果没有，我将计数器重置为 1。这似乎是最好的方法，我不敢相信我以前没有意识到这一点。

Answer 2

您可以使用给定序列的最长递增子序列(O(n^2))。还有 O(n) 和 O(n log n) 方法。

你也可以看看这个问题：Find the maximum subset of it which form a sequence。