如何从时间区间列表中统计单日的最大并发操作数量

核心算法原理 #

采用扫描线算法实现，时间复杂度为O(nlogn)，仅和操作数据量正相关，远高于逐分钟遍历的实现效率，核心逻辑如下：

• 为每个操作的开始时间生成标记为+1的事件，结束时间生成标记为-1的事件
• 将所有事件按时间戳升序排序，如果两个事件时间相同，结束事件要排在开始事件前面，避免将同一时间点结束、开始的操作误算为并行
• 遍历排序后的事件，累加当前并行操作数，遍历过程中记录到的最大值即为单日最大并行操作数

Java 11 + JodaTime 实现示例 #

首先定义操作时间区间实体：

import org.joda.time.DateTime;

// 操作时间区间类，可匹配你从Elasticsearch查询到的结构
class OperationInterval {
    private DateTime startTime;
    private DateTime endTime;

    public DateTime getStartTime() {
        return startTime;
    }

    public DateTime getEndTime() {
        return endTime;
    }
    // 构造方法、其他属性/方法省略
}

计算逻辑实现：

import org.joda.time.DateTime;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class MaxParallelCalculator {
    static class TimeEvent {
        private final long timestamp;
        private final int flag; // +1代表操作开始，-1代表操作结束

        public TimeEvent(long timestamp, int flag) {
            this.timestamp = timestamp;
            this.flag = flag;
        }
    }

    public int calculateMaxParallel(List<OperationInterval> intervalList) {
        List<TimeEvent> eventList = new ArrayList<>();
        for (OperationInterval interval : intervalList) {
            eventList.add(new TimeEvent(interval.getStartTime().getMillis(), 1));
            eventList.add(new TimeEvent(interval.getEndTime().getMillis(), -1));
        }

        // 排序规则：先按时间戳升序，时间相同的情况下结束事件优先
        eventList.sort(Comparator.comparingLong((TimeEvent e) -> e.timestamp)
                .thenComparingInt(e -> e.flag));

        int currentParallel = 0;
        int maxParallel = 0;
        for (TimeEvent event : eventList) {
            currentParallel += event.flag;
            maxParallel = Math.max(maxParallel, currentParallel);
        }
        return maxParallel;
    }
}

边界调整说明 #

• 如果业务规则中结束时间为闭区间（比如结束时间为10:00的操作，10:00整仍算运行中），可以给结束事件的时间戳加1毫秒后再排序，即可适配规则
• 若存在跨天的操作，提前裁剪超出单日统计范围的区间即可，不影响算法逻辑
• 原生支持毫秒级时间精度，不需要手动按分钟/秒聚合，万级操作量也可毫秒级完成计算

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