实现最大并行化(数据结构和算法)

Question

我在一次关于极客的采访中看到了这个问题。

您将获得一个数据列表，其中包含以下属性：开始时间、Rest-Api名称/服务名称、结束时间。您需要找到已实现的最大并行性。示例–{1，A，4}，{2，B，3}，{4，C，10}，｛4，D，7}，{2，E，4}}。这里的答案是4，因为在时间t=4时，有4个服务在运行，即分别为A、C、D、E

我的方法是根据开始时间对所有服务进行排序(如果开始时间相等，则根据完成时间进行排序。然后将每个进程与其他进程进行比较(如果有人能提出一个有效的方法来解决这个问题，那就太好了。

Answer 1

如果最大时间是合理的低

(完全未经测试(

std::array<int, MaxTime+1> start;
std::array<int, MaxTime+1> end;
start.fill(0);
end.fill(0);
for(auto & service : services) {
start[service.start]++;
end[service.end]++;
}
int maxtime = -1;
int pos = 0;
int maxsum = 0;
std::inner_product(start.begin(),start.end(),end.begin(),0,
[](int sum, int diff) { sum += diff; if (sum > maxsum) { maxtime = pos } ++pos; }, 
std::minus<int>())

应为O(最大(N，最大时间((

如果时间很高或N很低，那么你可能会更好地使用这种

sort(starttime)
sort(endtime)
par = 0
while(starttime)
par++
while (endtime < next(starttime))
par--
if (par > maxpar)
maxpar = par
time = starttime

O(NlgN(