酒店预订可行性问题变体：寻求首个失败预订索引的亚O(NM)解法

问题描述 #

常规酒店预订可行性问题可在O(NlogN)时间内解决，但针对以下变体，暂时找不到时间复杂度低于O(NM)的解决方案：

酒店经理需为未来M天处理N笔预订，每日可用房间数不同。给定数组rooms[M]（rooms[i]为第i天的可用房间数），以及预订列表bookings[N][3]（bookings[j][0]为第j笔预订所需房间数，bookings[j][1]为起始日，bookings[j][2]为结束日，首尾均包含）。若所有预订均可执行，返回预订总数；若存在预订失败，返回首个失败预订的索引。

输入输出定义 #

输入数据 #

• int[M] rooms：rooms[i]代表第i天的可用房间数
• int[N][3] bookings：bookings[j][0]为第j笔预订所需房间数，bookings[j][1]为起始日，bookings[j][2]为结束日

返回值 #

所有预订可行则返回预订总数，否则返回首个失败预订的索引

示例 #

输入：
rooms：[2, 8, 5, 8]
bookings：

[2, 0, 2]
[1, 1, 2]
[5, 1, 3]
[3, 2, 3]

返回：2

解释：执行预订0后，可用房间变为[0,6,3,8]；执行预订1后变为[0,5,2,8]；执行预订2时，第2天可用房间为2，小于所需的5，因此返回预订索引2。

现有解法 #

O(NM)暴力解法 #

逐个处理预订，对每个预订遍历其覆盖的日期，更新可用房间数，一旦出现负数立即返回当前预订索引：

for(int i = 0 ;i < bookings.length; i ++){
    int roomRequired = bookings[i][0];
    int start = bookings[i][1];
    int end = bookings[i][2];
    for(int j = start; j <= end; j ++){
        rooms[j] -= roomRequired;
        if(rooms[j] < 0 ) return i;
    }
}
return bookings.length;

差分数组快速找失败日期（无法定位首个失败预订） #

通过差分数组统计所有预订的总占用量，快速找到首个无法满足的日期，但无法确定是哪笔预订导致的：

int[] helper = new int[rooms.length + 1];

for(int i = 0 ;i < bookings.length; i ++){
    int roomRequired = bookings[i][0];
    int start = bookings[i][1];
    int end = bookings[i][2];
    helper[start] += roomRequired;
    helper[end + 1] -= roomRequired;
}
int bookingSum = 0;
for(int i = 0; i < rooms.length; i ++){
    bookingSum += helper[i]; 
    if(rooms[i] < bookingSum) return i;
}

优化解法：线段树实现O(N logM)复杂度 #

思路 #

使用线段树维护每个日期的累计预订量与可用房间数的差值（即累计预订量 - rooms[i]），核心操作：

1. 初始化线段树，每个叶子节点的值为-rooms[i]（初始累计预订量为0，所以0 - rooms[i] = -rooms[i]）
2. 逐个处理预订：对当前预订的[start, end]区间执行区间加法（加上该预订所需房间数）
3. 每次更新后，查询线段树的全局最大值：
   • 若最大值 > 0，说明存在某日期的累计预订量超过可用房间数，当前预订即为首个失败的，返回其索引
   • 若最大值 ≤ 0，继续处理下一个预订
4. 所有预订处理完成后，返回预订总数N

线段树的区间更新和全局最大值查询均为O(logM)时间，因此总时间复杂度为O(N logM)，远低于O(NM)。

代码示例（Java） #

class SegmentTree {
    private int[] tree;
    private int[] lazy;
    private int n;

    public SegmentTree(int[] nums) {
        n = nums.length;
        tree = new int[4 * n];
        lazy = new int[4 * n];
        build(0, 0, n - 1, nums);
    }

    private void build(int node, int start, int end, int[] nums) {
        if (start == end) {
            tree[node] = nums[start];
            return;
        }
        int mid = (start + end) / 2;
        build(2 * node + 1, start, mid, nums);
        build(2 * node + 2, mid + 1, end, nums);
        tree[node] = Math.max(tree[2 * node + 1], tree[2 * node + 2]);
    }

    private void pushDown(int node, int start, int end) {
        if (lazy[node] != 0) {
            tree[node] += lazy[node];
            if (start != end) {
                lazy[2 * node + 1] += lazy[node];
                lazy[2 * node + 2] += lazy[node];
            }
            lazy[node] = 0;
        }
    }

    public void updateRange(int l, int r, int val) {
        updateRange(0, 0, n - 1, l, r, val);
    }

    private void updateRange(int node, int start, int end, int l, int r, int val) {
        pushDown(node, start, end);
        if (r < start || end < l) {
            return;
        }
        if (l <= start && end <= r) {
            lazy[node] += val;
            pushDown(node, start, end);
            return;
        }
        int mid = (start + end) / 2;
        updateRange(2 * node + 1, start, mid, l, r, val);
        updateRange(2 * node + 2, mid + 1, end, l, r, val);
        tree[node] = Math.max(tree[2 * node + 1], tree[2 * node + 2]);
    }

    public int getMax() {
        pushDown(0, 0, n - 1);
        return tree[0];
    }
}

public class HotelBooking {
    public static int findFirstFailedBooking(int[] rooms, int[][] bookings) {
        int n = rooms.length;
        // 初始化线段树的数组：每个元素是 -rooms[i]
        int[] initVals = new int[n];
        for (int i = 0; i < n; i++) {
            initVals[i] = -rooms[i];
        }
        SegmentTree st = new SegmentTree(initVals);

        for (int i = 0; i < bookings.length; i++) {
            int cnt = bookings[i][0];
            int start = bookings[i][1];
            int end = bookings[i][2];
            st.updateRange(start, end, cnt);
            if (st.getMax() > 0) {
                return i;
            }
        }
        return bookings.length;
    }

    public static void main(String[] args) {
        int[] rooms = {2, 8, 5, 8};
        int[][] bookings = {
            {2, 0, 2},
            {1, 1, 2},
            {5, 1, 3},
            {3, 2, 3}
        };
        System.out.println(findFirstFailedBooking(rooms, bookings)); // 输出2
    }
}

另一种思路：二分查找+差分数组（O((N+M)logN)） #

如果线段树实现起来麻烦，也可以用二分查找：

1. 二分查找最大的k，使得前k个预订全部可行
2. 验证前k个预订是否可行：用差分数组计算每天的累计预订量，检查是否所有天的累计量≤rooms[i]
3. 若k等于预订总数，返回k；否则返回k

该方法的时间复杂度为O((N+M)logN)，当M远小于N时，效率接近线段树解法。

内容的提问来源于stack exchange，提问作者bad_cookie