在元组列表中获取最大并发性的有效方法是什么? [英] What is an efficient way to get the max concurrency in a list of tuples?

问题描述

我一直试图以有效的方式解决此问题.问题是:

I have been trying to solve this problem in an efficient way. The problem is:

问题陈述

给出格式为 [(start1，end1)，(start2，end2)，(start3，end3)....(startn，endn)] 的元组列表是正整数.每个元组都代表一个时间窗口，例如: [(1，3)，(73，80)...] .找到发生最大并发的时间(整数)，并获取发生最大并发的元组.

Given a list of tuples in the form [(start1, end1), (start2, end2), (start3, end3)....(startn, endn)] where start and end are positive integers. Each tuple is to represent a time window, for example: [(1, 3), (73, 80)...]. Find the time (integer) where max concurrency occurs and get the tuples where max concurrency occurs.

约束:

1. start 和 end 是时间的整数，介于0到n之间
2. 在所有情况下 start <结束
3. 开始包括在内，但 end 是排他的
4. 对于最大并发发生的时间(整数)，如果有多种情况我们只能得到一个

1. start and end are integers of time and are between 0 to n
2. For all cases start < end
3. start is inclusive but end is exclusive
4. For the time (integer) where maximum concurrency occurs, we can get only one if there are multiple cases

例如，下面的计划在时间2将具有max_concurrency，并且元组分别是(0,3)，(2,3)，(1，200).

For example the schedule below will have max_concurrency at time 2 and the tuples are (0,3), (2,3), (1, 200) that have it.

schedule = [
            (0, 3),
            (3, 5),
            (2, 3),
            (6, 8),
            (10, 12),
            (73, 92),
            (1, 200),
            ]

我的代码

用于最大并发发生的时间.如果我错了，请纠正我，但我认为这是在 O(n ^ 2)时间内运行的.

For time at where maximum concurrency occurs. Correct me if I'm wrong but I think this runs in O(n^2) time.

from collections import defaultdict

schedule_dict = defaultdict(lambda: 0)

for start, end in schedule:
    for time in range(start, end):
            schedule_dict[time] += 1

max_concurrency = max(schedule_dict, key=schedule_dict.get)
print(f"Time where max concurrency happens is : {max_concurrency}")

输出

Time where max concurrency happens is : 2  

对于发生最大并发性的会话，我认为这是在 O(n)时间时间内运行的.

For the sessions where maximum concurrency occurs, I think this runs in O(n) time.

我的代码

for start, end in schedule:
    if start <= max_concurrency < end:
        print(f"{(start, end)}")

输出

(0, 3)
(2, 3)
(1, 200)

最后一个问题

有什么更有效的方法来减少时间和空间的复杂性?

What is a more efficient way to do this to reduce time and space complexity?

推荐答案

在任意时刻T上重叠的间隔数是间隔开始时间小于或等于T的数量，减去间隔结束时间小于或等于T的数量等于T.

The number of intervals overlapping any time instant T is the number of interval start times less than or equal to T, minus the number of interval end times less than or equal to T.

1. 将开始时间和结束时间放在单独的列表中，并对它们进行排序.
2. 将深度计数器初始化为0
3. 按顺序浏览列表(如合并排序)，为每个开始时间加1，然后为每个结束时间减1
4. 记住计数器达到最大值时-这是最大重叠时间.

这是python中的实现:

Here's an implementation in python:

schedule = [
  (0, 3),  (3, 5), (2, 3), (6, 8),
  (10, 12), (73, 92), (1, 200),
  ]

starts = [x[0] for x in schedule]
ends = [x[1] for x in schedule]

starts.sort()
ends.sort()

endpos = 0
depth = 0
maxdepth = 0
maxdepthtime = -1

for time in starts:
    depth+=1
    while endpos < len(ends) and ends[endpos]<= time:
        depth -= 1
        endpos += 1
    if depth > maxdepth:
        maxdepth = depth
        maxdepthtime = time

overlappers = [x for x in schedule
    if (x[0] <= maxdepthtime and x[1] > maxdepthtime)]

print ("Max overlap at time: ", maxdepthtime, " depth ", maxdepth)
print ("Intervals: ", overlappers)

这篇关于在元组列表中获取最大并发性的有效方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！