M25302: 最大并发量

greedy, http://cs101.openjudge.cn/practice/25302

互联网公司大家一个服务，比如社交app的后台，都会考虑用户连接服务器的并发量，就是同一时刻的最大连接数。

现在给出一些的开始时间和断开时间，问这个过程中，最大的并发量有多少。

如果一个连接在 x 时刻开始，另一个连接在 x 时刻结束，认为 x 时刻并发量是 1，而不是 2.

输入

第一行是 t，t <= 100，代表数据组数。对于每组数据，第一行是 n，1 <= n <= 100，代表有 n 个连接，接下来 n 行，每一行有两个整数 x, y ，0 <= x < y <= 10^9，代表连接的开始时间是 x，断开时间是 y。

输出

对于每组数据输出一行，代表最大并发量。

样例输入

样例输出

1
2

来源：2016fall-cs101

典型的区间合并与并发计数问题，适合用扫描线算法（sweep line）解决。

✅ 题意解读

给你若干个连接的开始和断开时间，问在整个过程中“同一时刻最多有多少个连接是活跃的”。
特别注意：
- 如果一个连接在 x 时刻开始，另一个连接在 x 时刻断开，x 时刻的并发是 1（不是 2）。
- 所以我们认为：“结束先于开始”在同一时刻。

✅ 解决方案解析

🧠 核心思路：扫描线

把每个时间点视为一个“事件”：

开始连接：(x, +1)
结束连接：(y, -1)

然后将所有事件按时间排序处理。

若时间相同，优先处理 -1（断开），避免并发误增。

⏱️ 时间复杂度

每组：排序 O(n log n)，遍历 O(n)

模拟接入（+1）、断开（-1）的动态过程，而最大并发量就是这一过程中能达到的最大的数。

python

def max_concurrent_connections(n, intervals):
    events = []
    for start, end in intervals:
        events.append((start, 1))  # 开始 +1
        events.append((end, -1))   # 结束 -1

    # 按时间排序，时间相同时结束事件在前
    events.sort(key=lambda x: (x[0], x[1]))

    current = 0
    max_concurrent = 0
    for time, delta in events:
        current += delta
        max_concurrent = max(max_concurrent, current)

    return max_concurrent

# 主程序处理多组数据
t = int(input())
for _ in range(t):
    n = int(input())
    intervals = [tuple(map(int, input().split())) for _ in range(n)]
    print(max_concurrent_connections(n, intervals))

✅ 总结

本题是典型的事件排序+前缀和模拟问题；
考察排序规则、扫描线思想；
可作为处理“时间区间统计类问题”的模板。

2022fall-cs101, 卫家燊思路：时刻的数值可以达到1e9，明显挨个遍历是不可以的。注意到n的数据范围特别小，所以问题得解。

注意同一时刻开始、结束的只记开始的。

2022fall-cs101, 周浩钧，光华管理学院。数学证明：若不然，则在中间取到。由连续性，取距该点最近的开始端点，易知并发量不变。因而，总可以找到开始端点合题。

2022fall-cs101, 胡靖苑，生命科学学院。思路：一开始以一段线段为出发点计算重叠，发现根本没办法做下去，卡了很久。后来转换一下思路，用一个端点作为锚点，就能精准地找到每一个重叠了。大概是因为一个重叠区间中一定有一个点会完整经历所有重叠，但是如果换成线段，到底是哪一段线段代表重叠区则很难确定。

2022fall-cs101，张宇辰，元培学院。最主要的思路是，并发算“头”不算“尾”，所以产生最大并发的时间段一定会包括某段进程开始的时刻，于是只要对开始时刻遍历就可以了。

python

# 注意同一时刻开始、结束的只计开始的。
t=int(input())
while t>0:
    t-=1
    n=int(input())
    a=[];b=[]
    for i in range(n):
        x,y=input().split()
        a.append(int(x))
        b.append(int(y))
    ans = 0
    for i in range(n):
        cnt=0
        for j in range(n):
            if a[i]>=a[j] and a[i]<b[j]:
                cnt+=1
        ans = max(ans, cnt)
    print(ans)

2022fall-cs101，陈文瀚，物理学院。一开始自己建了个10^9 大小的数组，直接MLE 了，然后思考到上下车问题，可以只看每站上下车人数来确定目前车上人数。

2022fall-cs101，林婧涵中国语言文学系。用程序模拟接入（+1）、断开（-1）的动态过程，而最大并发量就是这一过程中能达到的最大的数。

python

'''
将开始时间和结束时间一起进行排序，然后逐一进行判断就可以。
比如第一组例子
2
1 2
2 3
可以处理成tmp=[[1,1],[2,-1],[2,1],[3,-1]]，每个元素有两维，第一维表示时间，
第二维表示开始(1)或结束(-1)。这样进行排序后，便可以根据时间顺序，
处理当前连接数，同时更新最大值。
注意：因为要求同一时间既有断开又有开始时，优先考虑断开的，所以同一个时间，
结束的需要排在开始之前，所以结束用-1而开始用1。
排序时间O(nlogn)，按时间顺序处理一次为O(n)，总的为O(nlogn)
'''

t=int(input())
while t:
  t-=1
  n=int(input())
  arr=[]
  for i in range(n):
    b,e=map(int, input().split())
    arr.append([b,1])
    arr.append([e,-1])
  arr=sorted(arr)
  cur=0
  res=0
  for i in range(len(arr)):
    cur+=arr[i][1]
    res=res if res > cur else cur
  print(res)

# by 黄丽明 北京大学

python

# 查达闻
from collections import defaultdict

for t in range(int(input())):
    time = defaultdict(int)

    for i in range(int(input())):
        start, end = map(int, input().split())
        time[start] += 1
        time[end] -= 1

    ans = temp = 0
    for i in sorted(time):
        temp += time[i]
        ans = max(ans, temp)

    print(ans)

2022fall-cs101，陈睿婷，化学与分子工程学院。类似CF1000B: Light it up 题（https://codeforces.com/problemset/problem/1000/B）的思路（先排序，再挨个遍历看每一刻的‘开’‘关’情况）才AC 了。

python

for i in range(int(input())):
    n = int(input())
    times = []
    op = 0
    answer = []
    for ii in range(n):
        a = list(map(int, input().split()))
        times.append([a[0], 1])
        times.append([a[1], -1])
    times.sort()
    for ti in times:
        if ti[1] != -1:
            op += ti[1]
        else:
            answer.append(op)
            op += ti[1]
    print(max(answer))

M25302: 最大并发量 ​

M25302: 最大并发量