From which collection you can quickly remove an element, but the bean is applicable to it. Search?

Question

Java

In general, in my solution to the problem, you need to look for the bin element. search (essentially an upperBound of some x) and remove it so that it is not used in subsequent searches. The problem is that the complexity always grows into a square: with an ArrayList, deletion takes O(n), with a LinkedList, the bin search is O(nlogn), and so on n times.

How to speed up the situation? Perhaps there is a fundamentally different approach? sortedSet does not have a method for upperBound.

Answer 1

TreeSet .
There you can search for the element you need through floor or ceiling. Search and removal, if the creators of the library in java have heard at least something about algorithms and data structures, work for the logarithm.

Answer 2

Write your own balanced tree. Removal and upperBound will be for the logarithm