一般的Hotel Booking Possible Problem可以用O（NlogN）来计算，但是我遇到了Hotel Booking Possible Problem的一个变体，我不能用O（NM）来计算。

**问题：**一位酒店经理正尝试管理接下来M天的酒店预订，其中有N个预订。由于某种原因，每天的可用房间数是不同的。您得到一个rooms[M]数组，其中rooms[i]表示第i天的可用房间数，预订列表包含所需房间数、开始时间和结束时间（包括）。如果所有预订都是可能的，算法将返回预订数。如果预订失败，算法将返回第一个失败的预订的索引。
给定数据：

• 内部[M]个房间 *
• 房间[i]第i天有空房
• int[N][3]个预订 *
• 预订[j][0]需要预订的房间j
• 预订[j][1]开始日期
• 预订[j][2]结束日
  **返回：**预订数（如果可能）或先失败的预订索引
  **示例：**房间：二八五八

预订：
二0二
1 1 2
五一三
3 2 3
返回：2
请说明：预订[0]需要2个房间，从第0天开始，到第2天结束（含）。预订[0]后，可用房间数变为[0 6 3 8]。同样，预订[1]后，可用房间数变为[0 5 2 8]。对于预订[2]，房间数不足，因为房间数[2]比预订[2]所需的房间数少2个，该值为5。因此，我们返回失败预订的索引2。
这是一个非常简单的O（NM）算法。

for(int i = 0 ;i < bookings.length; i ++){
   int roomRequired = bookings[i][0];
   int start = booking[i][1];
   int end = booking[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 = booking[i][1];
   int end = booking[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（MN），因为第一天失败不一定是由第一次失败的预订。