class Interval {
    LocalDateTime start, end;
    public Interval(LocalDateTime start, LocalDateTime end) {
        this.start = start;
        this.end = end;
    }
}

class Event {
    LocalDateTime time;
    int delta; // +1 表示开始，-1 表示结束

    public Event(LocalDateTime time, int delta) {
        this.time = time;
        this.delta = delta;
    }
}

public class MaxConcurrencyCounter {

    public int getMaxConcurrent(List<Interval> intervals) {
        List<Event> events = new ArrayList<>();

        // 拆解为时间点事件
        for (Interval interval : intervals) {
            events.add(new Event(interval.start, +1));
            events.add(new Event(interval.end, -1));
        }

        // 排序：时间升序，相同时间点先处理 +1
        events.sort((a, b) -> {
            if (!a.time.equals(b.time)) {
                return a.time.compareTo(b.time);
            } else {
                return b.delta - a.delta; // +1 比 -1 先处理
            }
        });

        // 扫描 + 统计最大值
        int current = 0;
        int max = 0;
        for (Event e : events) {
            current += e.delta;
            max = Math.max(max, current);
        }

        return max;
    }
}

SQL 解法思路（适用于 MySQL/PostgreSQL）

虽然 SQL 没有“扫描线”，但我们可以用“事件拆解 + 累计”来模拟！

步骤如下

把每条记录的 start_time 变成一个 “+1” 的事件
把每条记录的 end_time 变成一个 “-1” 的事件
UNION 合并起来
用 窗口函数 对这些事件点进行按时间排序累计

SQL 实现示例

-- 假设有表 events(id, start_time, end_time)
-- 1. 合并时间事件
WITH points AS (
  SELECT start_time AS event_time, 1 AS delta FROM events
  UNION ALL
  SELECT end_time AS event_time, -1 AS delta FROM events
),

-- 2. 扫描累计当前并发
concurrent_count AS (
  SELECT 
    event_time,
    SUM(delta) OVER (ORDER BY event_time) AS concurrent
  FROM points
)

-- 3. 找最大并发时刻
SELECT MAX(concurrent) AS max_concurrent
FROM concurrent_count;

复杂度分析

步骤	时间复杂度	说明
拆解为时间点	O(N)	每条记录拆两条事件
排序	O(N log N)	主要耗时在这一步
扫描	O(N)	一次线性扫描累计当前并发数

所以整体复杂度：O(N log N)，可以应对 5000 万条数据！

小结一下

方法	适用场景	优点
扫描线算法（Java）	面试、高性能服务、日志分析	逻辑清晰，性能强
SQL + 窗口函数	数据仓库、BI 分析	数据不出库，直接查询

工程里的关键补充点

事件边界与闭区间问题

时间区间是左闭右开还是双闭，要先定义清楚
同一时间点的 start/end 顺序会影响统计结果

数据规模与内存

5000 万条记录拆成 1 亿事件，内存要评估
超大规模要考虑分片或外部排序

SQL 方案的风险点

窗口函数在大表上可能很慢，要有索引支持
事件表建议先落地成临时表，避免重复计算

精度与桶化

业务只关注“秒级”，可以先做时间桶化
桶化后再做扫描，能显著降低事件数量