java - 将士兵分配到房间的算法问题

Question

所以我有一个搜索问题需要在 Java 中优化。这是说明我试图解决的问题的示例。

一名士兵到达基地并被分配到一个住房单元。每个基地都有一个或多个住房单元。

每个住房单元都有一个或多个房间。每个房间里都有多张床。每个房间都有一个优先级编号(1 为最高优先级)。每个房间的床位数量可以不同。

士兵需要被分配到一个房间。他被分配到可用床位最多的房间。如果有多个房间具有相同的床位，他会去优先级较高的房间。

一旦士兵被分配到一个房间，可用床位的数量当然会更新，并且队列中的下一个士兵将使用相同的过程添加，直到所有士兵都被分配到房间。

我们不必担心士兵无法分配到床位，因为没有可用的床位。另一个进程负责处理此类溢出情况。

我的问题是哪种 Java 数据结构实现最能解决士兵将被分配到哪个房间的问题？

目前我正在使用多维ArrayList，感觉一定有更好的方法。

Answer 1

无论是在设计方面还是在时间复杂度方面，您当然可以比多维 ArrayList 做得更好。

从设计的角度来看，您有三个包含类 - Room , House ，和Base 。 (也是 Soldier ，但出于我们的目的 Soldier 不需要任何额外信息。)

public class Soldier{}

首先，Room相当简单。它必须包含 Soldier并知道还剩下多少个开放房间

public class Room {

    private int totalBeds;
    public final int priority;
    private ArrayList<Soldier> soldiers;

    public Room(int totalBeds, int priority) {
        this.totalBeds = totalBeds;
        this.priority = priority;
        soldiers = new ArrayList<>();
    }

    public boolean add(Solider s) {
        if(soldiers.size() >= totalBeds) {
            return false;
        }
        return soldiers.add(s);
    }

    public int getRemainingBeds() {
        return totalBeds - soldiers.size();
    }

    public boolean isFull() {
        return totalBeds <= soldiers.size();
    }
}

从那里，我们需要一个 House类(class)。这是 Rooms 的优先级队列，并且必须能够根据房间的优先级将士兵添加到房间。

public class House {

    private final String name;
    private PriorityQueue<Room> rooms;

    public House(String name, Room... rooms) {
        this.name = name;
        this.rooms = new PriorityQueue<>(new Comparator<Room>() {
            public int compare(Room a, Room b) {

                //Always prioritize an open room to a full one
                if(a.isFull() && b.isFull()) {
                    return 0;
                } else if (a.isFull()) {
                    return 1;
                } else if (b.isFull()) {
                    return -1;
                } else {
                    //Now try to get the room with the most available rooms
                    int bedDiff = b.getRemainingBeds() - a.getRemainingBeds();
                    if(bedDiff != 0) {
                        return bedDiff;
                    }
                    return a.priority - b.priority;
                }
           }
       });
       for(Room r : rooms) {
           this.rooms.add(r)
       }
    }

    public boolean add(Soldier s) {
        Room r = rooms.poll();
        boolean ok = r.add(s);
        rooms.add(r);
        return ok;
    }

    public String getName() {
        return name;
    }
}

最后，Base类应该使用 Map<String, House>通过名称快速定位房屋

public class Base {

    private Map<String, House> houses;

    public Base(House... houses) {
        houses = new HashMap<>();
        for(House h : houses) {
            houses.put(h.getName(), h);
        }
    }

    public boolean add(String houseName, Soldier s) {
        return houses.get(houseName).add(s);
    }
}

向基地添加士兵的全时间复杂度:

- Finding the correct House: O(1)
- Adding to the House:
    - Poll: O(log(#rooms in house))
    - Add to room: O(1)
    - Add: O(log(#rooms in house))