用于查找和使用属性至少为X的对象的Java数据结构

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或总线3，并将该组分配给(比方说)总线1。

组2应该有效地找到总线1或总线3，发现总线1被占用，并将该组分配给总线3。

这里需要什么样的数据结构？

为了找到满足所需容量的匹配公交车，我可以在O(lg N)时间内进行二进制搜索，找到与所需乘客数量匹配的最小容量，然后扫描O(N)时间，找到至少具有该数量的所有较高容量的公交车。

那么我如何在匹配的总线中进行选择以进行最终分配(例如，当组2需要在已被占用的总线1和bus3之间进行选择时)？

Answer 1

我认为你可以用O(lg N)+O(N)来实现。

首先，我会向总线类型添加一个标志，用于标记它已被占用。如果这个结果集合是按容量排序的，那么您可以在O(lg )中以比您的组大的最小容量(例如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;
}

我相信你可以利用Stream API筛选器得到O(N)，而不需要第一次排序的O(lg 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 )运算。找到此总线后，将其从树中删除。因为它是一个平衡的二叉树，所以delete也是一个O(log )操作。左倾红色黑树的完整实现可以在这里找到，它以log N复杂度执行这些操作：http://algs4.cs.princeton.edu/33balanced/RedBlackBST.java.html