我们正在为呼叫中心实施密度报告。结果必须以表格形式显示,每天一行,显示当天同时活动的最大通话数。
我们正在构建UI后面的库。合同规定,我们收到当天通话次数和两个整数数组,一个包含每个通话的开始时间,另一个包含每个通话的结束时间,例如:
对于某一天,只接收到两个通话:一个从20到30的通话,另一个从10到20的通话。同时通话的最大数量为1。
另一方面,对于另一天,也收到了两个通话,一个从10到45,另一个从15到40,则同时通话的最大数量为2。
Web服务的合同如下。
返回结果必须是:3。
我已经实现了这个解决方案:
我们正在构建UI后面的库。合同规定,我们收到当天通话次数和两个整数数组,一个包含每个通话的开始时间,另一个包含每个通话的结束时间,例如:
对于某一天,只接收到两个通话:一个从20到30的通话,另一个从10到20的通话。同时通话的最大数量为1。
另一方面,对于另一天,也收到了两个通话,一个从10到45,另一个从15到40,则同时通话的最大数量为2。
Web服务的合同如下。
public static int GetMaxDensity(int N, int[] X, int[] Y)
数据看起来像这样(假设那一天有3个电话)。第一个从10点到25点,第二个从12点到30点,第三个从20点到23点。
N = 3,
X = {10, 12, 20}
Y = {25, 30, 23}
返回结果必须是:3。
我已经实现了这个解决方案:
public static int GetMaxDensity(int N, int[] X, int[] Y)
{
int result = 0;
for (int i = 0; i < N; i++)
{
int count = 0, t = X[i];
for (int j = 0; j < N; j++)
{
if (X[j] <= t && t < Y[j])
count++;
}
result = Math.max(count, result);
}
return result;
}
当呼叫数量少于1000次(周末)时,它的效果非常好。但是在工作日,呼叫数量很大,计算时间很长(> 5分钟)。我知道原因可能是我的解决方案使用了两个嵌套循环,但我对复杂算法没有太多经验,因此我的问题是:
考虑到我只需要同时通话的最大数量(而不是时间或呼叫者),如果有更快的计算方法,那么该怎么做?