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

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(max(N，MaxTime))

如果时间是高的或者N是低的，那么这样的事情你可能会更好

sort(starttime)
sort(endtime)

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

O(NlgN)