Seria bom saber de que tipo de dados estamos falando. Quantos usuários existem? Quantos estarão online em média? Como é a proporção de "usuários vistos" em comparação com todos os usuários (esparsos vs. densos)?

Modificação do seu algoritmo Não estoure o primeiro, mas escolha um elemento aleatório do conjunto de usuários online. Isso deve melhorar o balanceamento e pode ajudar na complexidade amortizada, dependendo da proporção desses dois conjuntos!

Algoritmo alternativo (mais estruturado; pior caso ainda ruim; deve ser bom se esparso visto )

• Mantenha visto como uma árvore balanceada (inserção O(log n))
• Mantenha online como uma árvore equilibrada.
• Enquanto não foram escolhidos usuários suficientes:
  • Pesquisar a primeira lacuna em visto (por exemplo, [0,1,3,7] -> 2; O(log n) de acordo com o link SO)
  • Pesquisar o primeiro usuário>=valor da lacuna (O(log n))
  • Se o usuário
  • -> escolha
  • Outro
  • -> adicionar valor de intervalo escolhido temporariamente (para este momento; decisão do modelo com que frequência atualizar online ) para visto OU limite a pesquisa de alguma forma para> valor de intervalo escolhido (O(log n))

Dependendo dos dados, isso deve funcionar muito bem se os dados forem enormes e vistos é escasso!