统计最高在线人数

最近接了个统计需求，需要统计某一段时间内的最高在线人数

本来最高在线人数是前期最好处理，根据长连接建立和中断统计人数，将最高值入库。

但是前期因为某些原因不太好做，那就只能后期来做处理。

数据

我能拿到的数据包含进入和离开时间，统计也按照这两个时间来。

思路

最开始想的是将若干个时间段放在时间轴上，然后用类似取交集的方式计算最高在线人数。

看着很像是用滑动窗口解决，为此还去letcode上找有没有类似的题目。

但是没找到，不得不转变思路。

首先需要一根时间轴，这个用链表实现，将链表的每个节点认为是一个时间点，用index来表示。

那么进入和退出就是在指定的节点上插入数据；

最后再遍历这条链表，根据每个节点不同的状态执行 +1 -1 操作

---

但是上述方法会浪费大量的空间，因为可能存在某个时间点没有进入退出，但是链表上对应的节点依然存在

需要想办法把这些节点给干掉

优化

之所以要提前建立节点，是因为在插入数据的时候没法保证顺序，后面遍历的时候一定要保证链表节点是按照时间顺序排列的。

即便对原始数据进行排序，因为有两个时间的缘故，也没什么用处

尝试把进入和退出拆分到两条链表，再把原始数据按照两个时间分别排序。

然后先遍历进入，再遍历退出。没办法在一个循环里搞定。

再考虑怎么遍历。一条链表的情况下，只需要对每个节点做判断；但是两条链表的话，如何保证是在遍历每一秒，因为此时index不能代表时间点。

可以使用双指针。
第一个指针指向进入链表，以这条链表为准遍历。

遍历开始，每个指针都执行头节点

进入指针步进，同时做+1操作，根据当前节点的时间来判断退出链表是否步进，当进入时间晚于退出时间，则退出指针步进，此时方才做-1操作

进入链表结束时，退出链表肯定没有完，但是后面的数据只会有-1操作，不影响最高人数统计，可以不用处理

实际上的遍历操作就是一个双链表合并排序问题

实现

private static class VisitNode {
    /**
     * 当前秒操作人数
     */
    private int count = 0;
    /**
     * 当前节点代表的时间点，
     */
    private int second = 0;

    private VisitNode next;

    private Long time;
}

private VisitNode count(long second, VisitNode tail, VisitNode head, LiveStat s, long time) {
    if (tail == head) {//创建第一个节点
        head.next = new VisitNode();
        tail = head.next;
        tail.second = ((int) second);
        tail.count = 1;
        tail.time = time;

    } else if (tail.second == second) {//判断是否和当前时间点相同
        tail.count += 1;
    } else {//继续追加节点
        tail.next = new VisitNode();
        tail = tail.next;
        tail.second = ((int) second);
        tail.count = 1;
        tail.time = time;
    }
    return tail;
}



VisitNode enterHead = new VisitNode();
VisitNode quietHead = new VisitNode();
VisitNode enterTail = enterHead, quietTail = quietHead;

List<LiveStat> enterStat; // 数据来源不重要，总之 enterStat 是一个按照 进入时间 排好序的数据
List<LiveStat> quietStat;  // 数据来源不重要，总之 quietStat 是一个按照 退出时间 排好序的数据


// 处理进入操作

for (LiveStat liveStat : enterStat) {
    Long second = liveStat.getStartTime();

    // 取当前秒距离开始统计时间的秒数
    long se = (second - startTime) / 1000;

    enterTail = count(se, enterTail, enterHead, liveStat, liveStat.getStartTime());

}

// 处理退出操作
for (LiveStat liveStat : quietStat) {
    Long second = liveStat.getEndTime();

    // 取当前秒距离开始统计时间的秒数
    long se = (second - startTime) / 1000;
    quietTail = count(se, quietTail, quietHead, liveStat, liveStat.getEndTime());

}

// 双指针，遍历进入退出

int max = 0;
int count = 0;
quietHead = quietHead.next;// 避免把头结点算进来
enterHead = enterHead.next;

while (enterHead != null) {//不用关心quietHead是否遍历完问题
    if (enterHead.second < quietHead.second) {
        logger.info("进入时间={}", DateUtils.getAllTime(enterHead.time));
        count += enterHead.count;
        enterHead = enterHead.next;
    } else if (enterHead.second > quietHead.second) {
        logger.info("退出时间={}", DateUtils.getAllTime(enterHead.time));
        count -= quietHead.count;
        quietHead = quietHead.next;
    } else {//同时有人进出的情况
        logger.info("同时时间={}", DateUtils.getAllTime(enterHead.time));
        count -= quietHead.count;
        count += enterHead.count;

        quietHead = quietHead.next;
        enterHead = enterHead.next;
    }
    if (count >= max) {
        max = count;
    }

}