本文记录做酒店业务系统开发时遇到的算法实例：计算酒店产品月租价。

业务算法系列：收录业务系统开发中真实遇到的算法

背景

还是之前做酒店业务期间，我司酒店针对的是月租的场景，因此C端外展的价格是月租价。

月租价定义：从当天入住开始计算，碰到第一个连续30天可开房的区间，则累加30天的价格，否则继续查找。

B端供给侧拉到的ARI酒店商品数据格式是这样的：

ARI: 房价，房量，房态（Availability，Rate，Inventory）针对酒店商品的具体售卖信息，包含价格Rate，库存Inventory，可用性Availability http://docs.huazhu.com/crs/api/distributor/docs/v1/common/contract

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


/**
 * 酒店商品
 */
public class HotelAri {
    /**
     * 日期
     */
    private Date ariDay;
    /**
     * 价格
     */
    private BigDecimal price;
    /**
     * 库存
     */
    private Integer inventory;

}

因此简化后的问题转化为了一个方法：

1

public BigDecimal calculateMonthPrice(List<HotelAri> ariList)

我们这里定义 ariList 数据量为固定的60，并且保证输入的ariList是根据日期连续递增的序列。（无需再排序）

求解

我们画图表达一下题目：

所求应该很清晰了：给定60个连续的库存、价格数据，求其中第一段连续30天有库存的价格和。

粗暴解

首先来段粗暴解法，直接逐个展开每个子区间，判断30连续有库存是否成立。

拿到入参，依次遍历每个ari，每次都往后找一个30天的区间，如果有库存0的ari，则判断下一个ari。代码也很简单：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


public BigDecimal calculateMonthPrice(List<HotelAri> ariList) {
   int n = ariList.size();
   for (int i = 0; i <= n - 30; i++) {
      BigDecimal monthPrice = BigDecimal.ZERO;
      for (int j = i; j < 30 + i; j++) {
         HotelAri currAri = ariList.get(j);
         if (currAri.getInventory() <= 0) {
            // 如果库存为0，跳出当前循环，寻找下一个连续30天的区间
            break;
         }
         monthPrice = monthPrice.add(currAri.getPrice());
         if (j == 29 + i) {
            // 如果连续30天都有库存，返回这30天的价格
            return monthPrice;
         }
      }
   }
   // 如果没有找到连续30天有库存的区间，返回0
   return BigDecimal.ZERO;
}

等同于如下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


public BigDecimal calculateMonthPrice3(List<HotelAri> ariList) {
   int n = ariList.size();
   int monthDays = 30;
   for (int i = 0; i < n; i++) {
      int rangeCnt = 0;
      BigDecimal monthPrice = BigDecimal.ZERO;
      for (int j = i; j < n; j++) {
         rangeCnt++;
         HotelAri currAri = ariList.get(j);
         if (currAri.getInventory() <= 0) {
            break;
         }
         monthPrice = monthPrice.add(currAri.getPrice());
         if (rangeCnt == monthDays) {
            return monthPrice;
         }
      }
   }
   return BigDecimal.ZERO;
}

整体的时间复杂度为O(n^2)，原因是使用了双层嵌套循环。这个效率肯定是可以提升的。

滑动窗口优化解

其实我们在每个子区间判断的时候，碰到30天内无库存的情况，可以直接跳跃到下一个有库存的地方继续，不需要重复的判断。

姑且，我们将子区间叫做滑动窗口，窗口经过每个元素只处理一次。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


public BigDecimal calculateMonthPrice2(List<HotelAri> ariList) {
   int n = ariList.size();
   int monthDays = 30;
   int l = 0, r = l;
   for (; l < n; l++) {
      BigDecimal monthPrice = BigDecimal.ZERO;
      while (r < n && r < l + monthDays) {
         HotelAri currAri = ariList.get(r);
         if (currAri.getInventory() <= 0) {
            l = r + 1;
            r = l;
            break;
         }
         // 此时r有库存
         monthPrice = monthPrice.add(currAri.getPrice());
         if (r - l + 1 == monthDays) {
            return monthPrice;
         }
         r++;
      }
   }
   // 如果没有找到连续30天有库存的区间，返回0
   return BigDecimal.ZERO;
}

public BigDecimal calculateMonthPrice4(List<HotelAri> ariList) {
   int monthDays = 30;
   int validCnt = 0;
   BigDecimal monthPrice = BigDecimal.ZERO;
   for (HotelAri currAri : ariList) {
      if (currAri.getInventory() <= 0) {
         validCnt = 0;
         monthPrice = BigDecimal.ZERO;
         continue;
      }
      validCnt++;
      monthPrice = monthPrice.add(currAri.getPrice());
      if (validCnt == monthDays) {
         return monthPrice;
      }
   }
   return BigDecimal.ZERO;
}

每个元素仅一层循环遍历一次，时间复杂度从O(n^2)提升到了O(n)。

小结

在酒店产品连续30天有库存的第一个段求解价格的和问题中，我们尝试了两种解法：

暴力解；
滑动窗口解；

其中滑动窗口解法的核心也很简单：对于前序判断过的元素不做重复判断（此段不符合条件，下一段肯定也不符合，因此不需要重复判断）。

可以看到业务研发中碰到的例子，算法并不复杂。

另外在入参数据量较小的情况下，两种解法的运行效率并无差异。

解决、记录此类问题，主要价值还是梳理问题、表达思路、培养算法思维（效率意识）。

背景#

求解#

粗暴解#

滑动窗口优化解#

小结#

背景

求解

粗暴解

滑动窗口优化解

小结