少なくとも属性があるオブジェクトを検索して使用するためのJavaデータ構造X

Question

データ属性を持つすべてのオブジェクトを効率的に検索できるデータ構造（Java組み込みのコレクションクラスを使用することをお勧めします）を探していますXより大きい。割り当てシステムの一部になります。例えば

、私はいくつかの公共交通機関のバスとその能力を持っているとします

Bus 1: capacity 20 
Bus 2: capacity 12 
Bus 3: capacity 24 

今、私は、次の割り当てをしたいと思い：

Group 1: 16 passengers 
Group 2: 19 passengers 

グループ1は、効率的にバス1を見つける必要があります（バス）1にグループを割り当てることができます。

グループ2は、バス1またはバス3を効率よく見つけ、そのバス1が占有されていることを確認し、そのグループをバス3

ここでどのようなデータ構造が必要ですか？

必要な容量を満たすバスを見つけるには、O（lg N）時間でバイナリ検索を行い、必要な人数に一致する最小容量を見つけ出し、O（N）その番号以上のバス。

最終的な割り当てを行うために、一致するバスを選択するにはどうすればよいですか？（たとえば、グループ2は既に占有されているバス1とバス3のどちらかを選択する必要がありますか？

Answer 1

私はあなたがO（LG N）+ O（N）を使用して達成することができると思う。..

まず、私はそれが占有していますことをマーキングするためのバスタイプにフラグを追加します。 この結果得られたコレクションの容量がソートされている場合は、O（lg N）のグループよりも容量が小さい（たとえばX）バス バスにアクセスできます。

次に、最初の空きバスが見つかるまで、XからO（N）の最大値までコレクションをトラバースできます。

Answer 2

あなたの仕様に基づいて、私は何かを提案します。

@lombok.Data 
@AllArgsConstructor 
public class Group { 
    private Integer id; 
    private Integer size; 
} 

@lombok.Data 
@AllArgsConstructor 
public class Bus { 
    private Integer id; 
    private Integer capacity; 
    private Boolean occupied; 
} 

私は、最初の並べ替えのO（lg N）なしでストリームAPIフィルタを使用してこれをO（N）に取得できると思います。あなたはバスのコレクションを持っていると仮定すると、O（N）で利用可能なバスを見つけるための方法は、私はバランスの取れた、バイナリ検索ツリーを使用することになり、この

public Optional<Bus> getAvailableBus (Group group) { 
    return buses.stream().filter(
      bus -> bus.getCapacity() >= group.getSize() && !bus.isOccupied()).findFirst(); 
} 

Answer 3

ようになります。 「Ceil」は正しいバスを見つけるのに役立ちます。 "Ceil"はO（log N）操作です。このバスを見つけたら、それをツリーから削除します。それはバランスの取れたバイナリツリーなので、再度deleteはO（log N）操作です。ログNの複雑さでこれらの操作を行う左に傾いている赤い黒色ツリーの完全な実装はここにあります： http://algs4.cs.princeton.edu/33balanced/RedBlackBST.java.html