多用户在线时间段重叠区间查找算法实现咨询

嗨，我完全理解你的需求：你需要从用户的在线时间区间里，找出所有不同用户组合同时在线的精确时间段，而且要避免把多人重叠的时段和少人重叠的时段混在一起，就像你例子里[3,4]是三人在线，不能和[4,5]的两人在线合并。

你之前用两层循环的思路其实方向没错，但问题在于没有抓住「时间轴上的关键分界点」——正是这些分界点（用户的上线/下线时间）导致在线用户组合发生变化。下面给你一套清晰的解决思路，附代码示例：

核心思路 #

我们可以把整个时间轴拆分成由所有用户的上线、下线时间组成的「最小时间区间」，每个最小区间内的在线用户组合是固定的，这样就能精准捕捉到每一种用户组合对应的时段：

1. 收集所有关键时间点：把每个用户的开始、结束时间都提取出来，去重后排序，得到时间轴上的所有分界点。
2. 遍历每个最小时间区间：对每一对相邻的分界点，统计这个区间内在线的用户（即用户的在线区间完全包含当前最小区间）。
3. 记录有效组合：如果当前区间内在线用户数≥2，就把用户组合和对应的时间段记录下来。

代码示例（Python） #

# 定义用户在线时间段
user_intervals = {
    "P1": [1, 7],
    "P2": [2, 5],
    "P3": [3, 4],
    "P4": [6, 8]
}

# 收集所有关键时间点并排序去重
time_points = sorted({t for interval in user_intervals.values() for t in interval})

# 遍历每个最小时间区间，统计在线用户
result = []
for i in range(len(time_points) - 1):
    current_start = time_points[i]
    current_end = time_points[i + 1]
    # 筛选出当前区间内在线的用户
    online_users = [
        user_id for user_id, (start, end) in user_intervals.items()
        if start <= current_start and end >= current_end
    ]
    # 只记录2人及以上的组合
    if len(online_users) >= 2:
        # 对用户ID排序，保证组合一致性（比如P1,P2和P2,P1视为同一组合）
        sorted_users = sorted(online_users)
        result.append((sorted_users, [current_start, current_end]))

# 输出结果
for users, interval in result:
    print(f"{', '.join(users)} : {interval}")

运行结果 #

运行这段代码后，输出完全符合你的预期：

P1, P2 : [2, 3]
P1, P2, P3 : [3, 4]
P1, P2 : [4, 5]
P1, P4 : [6, 7]

为什么这个方法能解决你的问题？ #

之前的两层循环容易出现的问题是：会重复计算重叠区间，或者无法准确识别用户组合变化的边界（比如从三人在线变成两人在线的时间点3、4）。而这个方法通过把时间轴拆分成最小粒度的区间，每个区间内的用户组合是绝对固定的，自然就能区分开不同用户组合的重叠时段，不会出现混淆。

备注：内容来源于stack exchange，提问作者Mohammad.J