给定用户登录登出时间区间，求解最大并发峰值与对应总时长的乘积

问题定义 #

给定两组数组logins（用户登录时间）和logouts（对应用户的登出时间），每个用户的在线区间为闭区间[logins[i], logouts[i]]（包含两端时间点）。我们需要：

1. 找出所有时间点中的最大并发数（同时在线的用户数）；
2. 计算所有并发数等于该最大值的时间区间的总长度；
3. 返回两者的乘积（最大并发数 × 总时长）。

要求算法时间复杂度为O(nlogn)，以处理大规模数据。

核心思路 #

把用户的登录、登出转换为时间事件，通过排序事件并遍历统计并发数变化，同时记录最大并发状态的时长。关键在于将离散闭区间转换为连续半开区间，避免时间点重叠的统计误差。

具体步骤 #

1. 事件转换
   对每个用户的在线区间[a, b]，转换为两个事件：

   • 登录事件：(a, +1)（用户上线，并发数+1）
   • 登出事件：(b+1, -1)（用户在b时间点结束在线，下线事件放在b+1，对应连续区间[a, b+1)，时长正好是b-a+1）

2. 事件排序
   按以下规则排序事件：

   • 优先按时间点升序排列；
   • 时间点相同时，登录事件（+1）排在登出事件（-1）之前，确保同一时间点的上线先统计，避免漏算该时间点的并发。

3. 遍历统计
   初始化变量跟踪当前并发数、最大并发数、上一个事件时间、最大并发对应的总时长，然后遍历排序后的事件：

   • 若当前时间与上一个时间存在间隔，且当前并发数等于最大并发数，累加这段间隔的时长；
   • 更新当前并发数；
   • 若新的并发数超过之前的最大值，更新最大并发数并重置总时长；
   • 更新上一个事件时间。

代码实现（Python） #

def calculate_max_concurrent_product(logins, logouts):
    events = []
    for login, logout in zip(logins, logouts):
        events.append((login, 1))
        events.append((logout + 1, -1))
    
    # 排序：时间升序，同时间下登录事件优先
    events.sort(key=lambda x: (x[0], -x[1]))
    
    current_concurrent = 0
    max_concurrent = 0
    prev_time = None
    total_max_duration = 0
    
    for curr_time, delta in events:
        if prev_time is not None and curr_time > prev_time:
            if current_concurrent == max_concurrent:
                total_max_duration += curr_time - prev_time
        
        current_concurrent += delta
        
        if current_concurrent > max_concurrent:
            max_concurrent = current_concurrent
            total_max_duration = 0
        
        prev_time = curr_time
    
    return max_concurrent * total_max_duration

# 测试示例1
print(calculate_max_concurrent_product([1,5,5], [5,10,5]))  # 输出3
# 测试示例2
print(calculate_max_concurrent_product([4,10], [8,20]))     # 输出16

复杂度分析 #

• 事件收集：O(n)，每个用户生成2个事件；
• 事件排序：O(nlogn)，排序2n个元素的时间复杂度为O(2n log 2n)，等价于O(nlogn)；
• 遍历事件：O(n)，遍历2n个事件。
  总时间复杂度为O(nlogn)，满足要求。

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