java - 酒店预订 可能的预订

Question

我已经实现了一个简短的算法来判断是否可以进行所有酒店预订。问题与 this 非常相似，但我已尝试实现自己的逻辑。

(很抱歉这么长的解释)

在我的算法中

1. int K=可用房间数
2. ArrayList<Integer> arrive=客人到达时间
3. ArrayList<Integer> depart = 客人离开时间
4. int arriving_guest = 下一位客人
5. ArrayList<ArrayList<Integer>>安排 = 房间分配

例如

• 到达 = [1,3,5]
• 出发 = [2,6,8] 和
• K=1

现在，在我们开始迭代 ArrayList<ArrayList<Integer>> arrange 之前将是 [[2]]因为最初所有房间都可用并且int arriving_guest = 1当第一位客人入住时，它将指向下一位客人

现在进行第一次迭代，客人的到达时间为 3，离开时间为 6

• 检查第一个房间是否可用
• 由于第一位客人的出发时间是 2，所以他的房间可以分给第二位客人，所以 arrange将变为 [[2,6]]
• 增量arriving_guest指向下一位客人

现在进行第二次迭代，客人的到达时间为 5，离开时间为 8

• 检查第一个房间是否可用
• 由于第 2 位客人的出发时间是 6 点，所以他的房间不能给第 3 位客人，所以应该为第 3 位客人分配一个新房间，arrange将变为 [[2,6],[8]]
• 增量arriving_guest指向下一位客人

算法结束

需要的房间 = arrange.size() = 2

可用房间 = K = 1

所以它会返回false以上的值(value)

如果我将我的算法应用于以下测试用例，它会失败

• 到达 : [ 14, 29, 0, 35, 34, 15, 17, 7, 28, 13, 40, 28, 11, 40 ]
• 出发 : [ 51, 77, 37, 63, 76, 25, 57, 23, 40, 32, 63, 41, 21, 68 ]
• K : 9

我的算法是

private static boolean bookingsPossible(ArrayList<Integer> arrive, ArrayList<Integer> depart, int K) {
        // TODO Auto-generated method stub
        int arriving_guest = 1;
        ArrayList<ArrayList<Integer>> arrange = new ArrayList<ArrayList<Integer>>();
        arrange.add(new ArrayList<Integer>(){{
            add(depart.get(0));
        }});
        for(int i=0;i<depart.size();i++)
        {
            int temp = 0;
            System.out.println("i is "+i);
            while(temp <= i)
            {
                System.out.println("arriving guest "+arriving_guest);
                if(arriving_guest < arrive.size() && arriving_guest < depart.size())
                {
                    System.out.println("i is in if "+i);
                    if(temp <= (arrange.size() -1))
                    {
                    System.out.println("Temp is "+temp);
                    int vacatetime = arrange.get(temp).get(arrange.get(temp).size() - 1);
                    System.out.println("Vacate Time "+vacatetime+" Arrival Time "+arrive.get(arriving_guest));
                    if(vacatetime <= arrive.get(arriving_guest))
                    {
                        arrange.get(temp).add(depart.get(arriving_guest));
                        arriving_guest++;
                        System.out.println("Arrangement made "+arrange.toString());
                        break;
                    }
                    }
                    else
                    {
                        System.out.println("Adding room");
                        ArrayList<Integer> p = new ArrayList<Integer>();
                        p.add(depart.get(arriving_guest));
                        arrange.add(p);
                        System.out.println("Arrangement made "+arrange.toString());
                        arriving_guest++; break;
                    }

                }
                else
                {
                    break;
                }
                temp++;
            }
        }
        System.out.println("Rooms needed "+arrange.size());
        System.out.println("Final Arrangement made "+arrange.toString());
        return arrange.size() <= K ? true : false;
    }

Answer 1

如果我们将问题概括为以下内容:给定区间 (a_i, b_i)，找到最大数量的线段交叉点。

算法如下:

1. 制作另一个对数组:(a_i, false) 或 (b_i, true)，其中第一个 一个值表示该值，第二个是 boolean 标志，如果它是开始或 一个片段的结尾。
2. 按第一个坐标排序，在平局的情况下确保最后一对排在第一位。
3. 遍历结果数组并保留本地房间数。如果是段的开头，则增加房间数，如果是结尾，则减少。

算法实现如下:

public class HotelBooking {

    private static class Pair implements Comparable<Pair>{
        final int x;
        final boolean isEnd;

        public Pair(int x, boolean isEnd) {
            this.x = x;
            this.isEnd = isEnd;
        }

        @Override
        public int compareTo(Pair o) {
            int cmp = this.x - o.x;
            //in case of tie be sure that end pair comes first
            return cmp == 0 ? isEnd ? -1 : 1 : cmp;
        }
    }

    public boolean hotel(ArrayList<Integer> arrive, ArrayList<Integer> depart, int K) {
        if(arrive.size() == 0 || K == 0) return false; //base case
        else if(arrive.size() == 1 && K > 1) return false; //base case
        else {
            int n = depart.size();
            List<Pair> intervals = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                intervals.add(new Pair(arrive.get(i), false));
                intervals.add(new Pair(depart.get(i), true));
            }
            Collections.sort(intervals);
            int count = 0; //
            int maxRooms = 0;
            for (int i = 0; i < intervals.size(); i++) {
                Pair pair = intervals.get(i);
                count += pair.isEnd ? -1 : 1;
                maxRooms = Math.max(maxRooms, count);
            }

            return maxRooms > K ? false : true;
        }
    }
}