实际需求中使用区间合并算法

雨翔河

首页列表关于

实际需求中使用区间合并算法

2020-06-14 06:31

一直以来都觉得算法源于生活，这次有个核心计费算法，有个同事用正常的思维逻辑写的，写的蛮不错的。但是代码审核的时候我们几个初次看都没太看懂，因为计费逻辑稍微复杂些，代码长度就比较长，于是引发了我想用另一种更加直观的方式来做，于是乎想到了将需求拆分使用区间合并来做。

具体的需求是这样的：

某个物品进入某个安置点，当它达到N小时还没有人取的时候就要进行收费，其中收费规则会有以下几种：

1. 特殊必须收费时间段：T5-T6,T7-T8。。。必须收取手续费

2. 特殊免费时间段：T1-T2 , T3-T4。。。不需要收取手续费

3. 总的收费时间段，从进入安置点到用户取出这个总的时间。

4. 节假日免费时间段：周日，端午节。。。不收取手续费

5. 如果用户在这期间是会员那么就不需要收费。

而如果要改造的话，实现方案就是：

一、 把不收费的时间段计算出来。

二、 把必须收费的时间段计算出来。

三、 合并一和二的这些时间段，得到真实的收费时长和收费区间，减去免费保管时间的N小时区间。

四、 拿到单位收费金额和最大封顶金额。

五、 把真实收费区间的总时间金额*单位收费金额。

六、 封装数据，返回结果。

这样设计有个好处，可以把所有收费和不收费的时间段都得到，数据可以很清晰的输出，假设出现问题也可以很快速的定位出来。

上面拆分出来了之后有一个很明显且很重要的东西就是第三点，区间合并。

以前在大二的时候数据结构考试做过简单的区间合并，其实算得上是投机取巧，比如我只要知道这些区间的最大值和最小值，我搞一个数组把区间的这些数据全部扔到这个数组里面去，然后就可以立马得出合并后的区间。

这种方式虽然简单高效，但是有一个弊端，就是需要保证区间足够的小，如果区间特别大的话，效率会极其的低下。

就像我们今天讲的这个时间区间段合并，假设我们的精确度只考虑到小时，那么完全可以用这种方式，即使是一百年也才不足90W小时。

这里我们的精确度要达到分钟或者秒级甚至是毫秒级，就意味着用大数组的方式进行区间合并计算不现实，CPU根本扛不住，因为这个计算方法的QPS会非常的高。

所以对于时间类别的区间段合并，就需要用到另外一种区间合并，先对区间列表的左区间进行区间列表排序，排序好了之后进行顺序两两对比，这样就可以得到最终的合并区间段。

核心代码如下：

```
import org.apache.commons.lang3.tuple.Pair;

/**
     * 区间合并算法
     * 将所有区间进行合并
     *
     * @param list list
     * @return List
     */
    private static List<Pair<Date, Date>> mergeDate(List<Pair<Date, Date>> list) {
        List<Pair<Date, Date>> sortFreeList = list.stream().sorted(Comparator.comparingLong(p -> p.getLeft().getTime())).collect(Collectors.toList());

List<Pair<Date, Date>> tempList = new ArrayList<>();

long leftTemp = sortFreeList.get(0).getLeft().getTime();
        long rightTemp = sortFreeList.get(0).getRight().getTime();
        for (int i = 1; i < sortFreeList.size(); i++) {
            Pair<Date, Date> pair2 = sortFreeList.get(i);
            long a = leftTemp;
            long b = rightTemp;
            long c = pair2.getLeft().getTime();
            long d = pair2.getRight().getTime();
            if (c <= b) {
                // 区间2和区间1重合了
                leftTemp = a;
                rightTemp = b > d ? b : d;
            } else {
                // 区间1和区间2没有重合
                Date left = new Date(a);
                Date right = new Date(b);
                Pair<Date, Date> pair = Pair.of(left, right);
                tempList.add(pair);
                leftTemp = c;
                rightTemp = d;
            }
        }
        Date left = new Date(leftTemp);
        Date right = new Date(rightTemp);
        Pair<Date, Date> pair = Pair.of(left, right);
        tempList.add(pair);
        return tempList;
    }
```

这样就可以做到区间合并，在量大且数据较为分散，相距较远的这种情况下，这种方式有天然的优势。

这个总的计费工具类（不限于区间合并算法这个功能），我测试了下，跑了10W个随机的生产数据请求过来，我的个人普通电脑单机单线程20s可以执行完，也就是说QPS单机单线程可以达到5000左右，多节点服务器环境+多线程就更不用考虑性能问题了。

类型：工作标签：区间合并,算法